Variations in the efficiency of a mathematical programming solver according to the order of the constraints in the model
Abstract: It is well-known
that the efficiency of mixed integer linear mathematical programming depends on
the model (formulation) used. With the same mathematical programming solver, a
given problem can be solved in a brief calculation time using one model but requires
a long calculation time using another. In this paper a new, unexpected feature
to be taken into account is presented: the order of the constraints in the
model can change the calculation time of the solver considerably. For a test
problem, the Response Time Variability Problem (RTVP), it is shown that the
ILOG CPLEX 9.0 optimizer returns a ratio of 17.47 between the maximum and the
minimum calculations time necessary to solve optimally 20 instances of the
RTVP, according to the order of the constraints in the model. It is shown that
the efficiency of the mixed integer linear mathematical programming depends not
only on the model (formulation) used, but also on how the information is
introduced into the solver.
Keywords: mixed integer linear
mathematical programming, response time variability problem, combinatorial
optimization
Author: Rafael Pastor
Journal Code: jptindustrigg080010
