|
Technical Report: DCC-2007-08
An evolutionary solver for mixed integer programming
João P. Pedroso
DCC-FC, Universidade do Porto
R. do Campo Alegre 1021/1055 , 4169-007 Porto, Portugal
Phone: +351 220402919 , Fax: 351 22 402 950
E-mail: jpp@fc.up.pt
October 2007
Abstract
In this paper we introduce an evolutionary algorithm for the solution of mixed integer
programs. The strategy is based on the separation of the set of variables into the integer
subset and the continuous subset. The main idea is that if the integer variables are
fixed by the evolutionary system, the continuous ones can be determined in function
of them by a linear program, which simultaneously provides an evaluation of those
variables. We extend this idea to the case were some of the integer variables are fixed
by the evolutionary system and the remaining ones, as well as the continuous ones, are
determined in function of them. Branch-and-bound and a specialised version of the
relax-and-fixed heuristic are used to solve the mixed-integer subproblems.
When a particular assignment of the integer variables set by the evolutionary system
leads to a feasible solution, its evaluation is determined directly by the objective function.
If the variables correspond to an infeasible solution, the evaluation is measured by the
number of variables that could not be fixed, due to infeasibility in the subproblem;
solutions with more variables fixed are preferred.
We report results obtained for some standard benchmark instances, and compare
them with those obtained by time limited branch-and-bound. For a set of difficult
instances, the evolutionary algorithm could almost always improve the solution obtained
by branch-and-bound on the same amount of CPU time.
|