Minimum　attribute　reduction　(MAR)　problem　in　the　context　of　rough　set　theory　is　an　NP-hard　nonlinearly　constrained　combinatorial　(binary)　optimization　problem.　In　this　paper,　a　new　combinatorial　artificial　bee　colony　(ABC)　algorithm　is　presented　for　solving　the　MAR　problem.　Mutation　operation　based　search　schemes　are　introduced　for　employed　bees,　onlooker　bees　and　scout　bees.　Two　different　metrics　related　to　attribute　subsets　are　used　to　generate　candidate　neighboring　food　source　s.　Different　local　search　strategies　between　an　employed　bee　and　its　recruited　on　looker　bees　allow　for　a　more　diversified　neighboring　search　around　a　current　food　source.　Moreover,　the　information　of　the　so-far　best　solution　is　exploited　in　various　ways　by　employed　bees,　onlookers　and　scouts,　respectively.　Performance　comparisons　with　existing　best　performing　meta-heuristic　approaches　for　the　MAR　problem　were　carried　out　on　a　number　of　UCI　data　sets.　In　addition,　a　standard　statistical　t-test　is　used　for　evaluation　purpose.　The　experimental　results　show　that　our　combinatorial　ABC　approach　compares　favorably　with　all　the　other　approaches　in　terms　of　solution　quality.　The　proposed　combinatorial　ABC　algorithm　is　thus　efficient　and　well　suited　for　solving　the　MAR　problem.　©,　2015,　Chinese　Institute　of　Electronics.　All　right　reserved.