It looks like you need to work with an integer linear program (ILP), at least in the formulation you describe. Both NMinimize and LinearProgramming support integer variables, and of course they can be restricted to binary with a constraint such as 0<=x<=1.
