Abstract
A standard approach to solve 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, we define 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 us to solve MILPs more efficiently: on the average,
it performs one hundred times less choice points and requires three times
less cpu time.
Full paper (postscript)