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 4 down vote favorite

I have formulated an integer linear program (ILP). The constraint matrix for the ILP is totally unimodular.

Should I solve it as an LP without the integral constraints, or should I keep the integral constraints and let the optimization-toolbox's (MOSEK) mixed integer solver handle this special case?

share|improve this question

1 Answer

up vote 4 down vote accepted

It won't matter to any worthwhile mixed-integer linear programming (MILP, also known as MIP) solver if you keep or omit the integral constraints, as long as your constraint matrix is truly totally unimodular.

To be on the safe side, keep the integral constraints and call your MILP solver. Any solver utilizing a branch-and-bound or branch-and-cut framework should start by solving the linear programming (LP) relaxation of your ILP, in which case, it will omit the integral constraints. Since your constraint matrix is totally unimodular, an optimal solution of the LP relaxation should be satisfy the integral constraint because the polytope those constraints define consists of vertices with integer coordinates. Since the solution to the relaxation satisfies the integral constraints, the MILP solver will stop and return the solution obtained from the LP relaxation with little to no additional overhead beyond calling the LP solver (which is what you would have done if you just solved the LP relaxation).

share|improve this answer
1  
Let me just add to this correct account that keeping the integer constraints makes it more likely that a correct result will be obtained even with finite precision arithmetic. (This will be the case unless the solver encounters a very ill-conditioned matrix while solving the first LP.) – Arnold Neumaier Jun 13 '12 at 14:55

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.