Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 2 down vote favorite

I am implementing a machine learning algorithm for which I need to solve an integer linear program. To get the solution in polynomial time, the authors of the algorithm have dropped the integral constraints and instead solve the corresponding linear program.

I am not too aware of the theory of optimization, so using the Mosek optimization tool-kit as a black-box to solve the LP. Now obviously I have to add back the integral constraints once the solution of LP is obtained. Any ideas how to go about it? I am sure Mosek and other popular LP solvers would have an option for the same but can't seem to find it in their documentation or elsewhere.

Thanks.

share|improve this question
After you "add back the integral constraints" the solution will most likely become a no solution (called infeasible). Please explain what you are trying to do, and why you are not using a mixed-integer solver. – Ali Jun 4 '12 at 19:14
I am trying to minimize an linear objective function for which variables are integers. I had read that, if only some of the unknown variables are required to be integers, then the problem is called a mixed integer programming problem. In the problem I have at hand, all unknown variables are required to be integers. – stressed_geek Jun 4 '12 at 19:21

3 Answers

up vote 2 down vote accepted

A lot of linear programming (LP) software packages will also solve mixed-integer linear programs (MILPs) with varying degrees of effectiveness.

One way to "add back the integral constraints" is to warm-start an MILP solver with the solution from the LP relaxation of the integer linear program (ILP) that the authors of the machine learning algorithm use. However, Ali is right that it would be more efficient to solve the original ILP. Certain algorithms (such as branch-and-bound) will solve the LP relaxation in the process of computing an optimal solution.

Furthermore, any MILP solver worth using will implement MILP solution algorithms, such as branch-and-bound and branch-and-cut, with much more sophisticated algorithmic heuristics and variants than most people could code themselves. Even in problems with special structure, researchers often modify and tweak existing solvers rather than write their own.

If you're at a university, I highly suggest using CPLEX or Gurobi, both of which are top-of-the-line MILP solvers that have free academic licenses. In some cases, these solvers will solve MILP instances significantly faster than their competition. That said, if your problem is small enough, speed may not really matter.

share|improve this answer
up vote 3 down vote

If you delete the integer constraints and then tamper with the soultion to get an integral approximation, you are just reinventing the wheel of mixed integer linear programming (MILP). This is a highly nontrivial matter and you are unlikely to come up with anything better than most MILP solvers already implement - unless you first do a lot of research.

Note that the term ''mixed integer'' also covers the case where the number of continuous variables is zero. Because of that there is hardly any special software for the pure integer case.

share|improve this answer
And is there any specialized approach for the (pure) binary integer programming problem? I am thinking of function bintprog in the Matlab optimization toolbox. Maybe this is more or less a complete search. – Hans Werner Jun 5 '12 at 11:20
Pure binary integer programming is a special case where special methods are available. Nevertheless, a general-purpose MILP solver will typically solve these problems well, too, but perhaps not quite as fast as a special purpose binary LP solver. I have no experience with bintprog, though. - All MILP solvers try to do a complete search, unless the options specify something else (e.g., a time limit). – Arnold Neumaier Jun 5 '12 at 14:28
up vote 2 down vote

As a first attempt, try to solve your problem with the Mosek optimization toolkit you are using but do not remove the integral constraints.

According to the Mosek website, their solver can handle mixed-integer problems.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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