I have to solve a large binary programming task. Should I avoid branch and bound?

Question

I have to minimize a linear function with respect to variables u which take values [0,1]

The number of variables can exceed 10,000

There are thousands of linear inequality constraints

I need a solution which is good but does not have to be optimal.

Are there any heuristic approaches for doing this ?

For example I could allow 0 <= u <= 1 and then use an LP solver. I then iterate by pushing the values of u to 0 or 1 depending on their optimal value from the LP solver.

I am not sure how to do this but if this has been looked at then I would like to know.

I am using CPLEX.

Answer 1

10,000 variables is a lot for an integer programming problem, but everything depends on the details of your particular problem. With the information provided, there's really no way for us to tell you in advance how easy or hard it might be to solve this problem.

My advice would be to try CPLEX's integer programming solver on this problem with its default settings and observe how it behaves. You might be pleasently surprised by a quick solution that is proven optimal. If not, you might still be able to get a solution with a good bound on the objective value gap between it and optimal.

If CPLEX runs for many hours without finding an integer solution then watch out- you've got a problem where even finding an integer solution is extremely hard. If CPLEX runs for a long time and searches many nodes in the branch and bound tree without noticeably reducing the gap between the best known solution and the bound, then the problem might just be too difficult to solve to optimality.