[Zurück]

J. Puchinger, G. Raidl, M. Gruber:
"Cooperating memetic and branch-and-cut algorithms for solving the multidimensional knapsack problem.";
Vortrag: MIC2005 (The 6th Metaheuristics International Conference), Wien; 22.08.2005 - 26.08.2005; in: "Proceedings of MIC2005, the 6th Metaheuristics International Conference", (2005).

Recent work in combinatorial optimization indicates the high potential of combining metaheuristics with integer linear programming (ILP) techniques. We study a hybrid system in which a memetic algorithm (MA) and a general purpose ILP solver based on branch-and-cut (B&C) are executed in parallel and continuously exchange information in a bidirectional, asynchronous way. As target problem, we consider the multidimensional knapsack problem (MKP). The memetic algorithm uses a direct binary encoding of candidate solutions and repair and local improvement strategies that are steered by pseudo-utility ratios. As B&C framework we use the commercial ILP-solver CPLEX. The information exchanged between the two heterogenous algorithms are so-far best primal solutions and promising dual variable values of solutions to certain linear programming relaxations. These dual variable values are used in the MA to update the pseudo-utility ratios of local improvement and repair. We will see that this combination of a metaheuristic and an exact optimization method is able to benefit from synergy: Experimental results document that within the same limited total time, the cooperative system yields better heuristic solutions than each algorithm alone. In particular, the cooperative system also competes well with today's best algorithms for the MKP, needing substantially shorter total running times.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC05936453

http://publik.tuwien.ac.at/files/pub-inf_3337.pdf