2
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ Is there perhaps a way to approximate your problem with some simplification that has less variables? $\endgroup$ – Daniel Eberts Apr 20 '14 at 9:05
  • $\begingroup$ Oh and if CPLEX doesn't cut it in terms of speed, try Gurobi. I once had to solve quadratic problems and found the latter to be significantly faster than CPLEX. $\endgroup$ – Daniel Eberts Apr 20 '14 at 9:08
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.