Cooperation of LP solvers for solving MILPs
Christine Solnon · 2002
A standard approach to solving mixed integer linear programs is to perform a global branch and bound search through all possible combinations. Due to the hardness of the problem, this search must be closely controlled by a constraint solver which uses constraints to prune the search space in an a priori way. In this paper, one defines a new domain reduction solver which uses in a cooperative way a set of linear programming solvers. The idea is to compute the actual range of values of the integer variables with respect to the continuous relaxation of the problem, and then narrow these domains to the closest integer interval. This narrowing is iteratively performed until a fixed point is reached where all domains are bound by integer values which belong to the continuous relaxation of the problem. This fixed point corresponds to a new partial consistency, which is stronger than the continuous relaxation and allows one to solve MILPs more efficiently.