zbMATH — the first resource for mathematics

A dual heuristic for mixed integer programming. (English) Zbl 1408.90200
Summary: In linear programming based branch-and-bound algorithms, many heuristics have been developed to improve primal solutions, but on the dual side we rely solely on cutting planes to improve dual bounds. We design a dual heuristic which incorporates relaxation algorithms within a branch-and-bound framework to improve dual bounds. We study the effect of solving various relaxations with dual heuristics by conducting a series of computational tests on the multi-dimensional knapsack problem.

90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI
[1] Beasley, J., OR—library: distributing test problems by electronic mail, J. Oper. Res. Soc., 41, 11, 1069-1072, (1990)
[2] Carvajal, R.; Ahmed, S.; Nemhauser, G.; Furman, K.; Goel, V.; Shao, Y., Using diversification, communication and parallelism to solve mixed-integer linear programs, Oper. Res. Lett., 42, 2, 186-189, (2014)
[3] Chu, P.; Beasley, J., A genetic algorithm for the multidimensional knapsack problem, J. Heuristics, 4, 1, 63-86, (1998)
[4] Danna, E.; Rothberg, E.; Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 1, 71-90, (2005)
[5] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program., 104, 1, 91-104, (2005)
[6] Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 1, 23-47, (2003)
[7] Freville, A.; Plateau, G., Hard 0-1 multiknapsack test problems for size reduction methods, Investig. Oper., 1, 251-270, (1990)
[8] Martello, S.; Toth, P., Knapsack problems: algorithms and computer implementations, (1990), John Wiley & Sons, Inc.
[9] Lodi, A., Mixed integer programming computation, (2010), Springer
[10] Osorio, M.; Glover, F.; Hammer, P., Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Ann. Oper. Res., 117, 1, 71-93, (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.