





Technical Report: DCC200708An evolutionary solver for mixed integer programmingJoão P. PedrosoDCCFC, Universidade do PortoR. do Campo Alegre 1021/1055 , 4169007 Porto, Portugal Phone: +351 220402919 , Fax: 351 22 402 950 Email: jpp@fc.up.pt AbstractIn 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. Branchandbound and a specialised version of the relaxandfixed heuristic are used to solve the mixedinteger 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 branchandbound. For a set of difficult instances, the evolutionary algorithm could almost always improve the solution obtained by branchandbound on the same amount of CPU time. 

