zbMATH — the first resource for mathematics

Variable neighborhood search and local branching. (English) Zbl 1086.90042
Summary: We develop a variable neighborhood search (VNS) heuristic for solving mixed-integer programs (MIPs). It uses CPLEX, the general-purpose MIP solver, as a black-box. Neighborhoods around the incumbent solution are defined by adding constraints to the original problem, as suggested in the recent local branching (LB) method of M. Fischetti and A. Lodi [Math. Program. 98, No. 1–3(B), 23–47 (2003; Zbl 1060.90056)]. Both LB and VNS use the same tools: CPLEX and the same definition of the neighborhoods around the incumbent. However, our VNS is simpler and more systematic in neighborhood exploration. Consequently, within the same time limit, we were able to improve 14 times the best known solution from the set of 29 hard problem instances used to test LB.

90C09 Boolean programming
Full Text: DOI
[1] Reeves C, editor, Modern heuristics. Boston, Dordrecht, London: Kluwer Academic Publishers, 1993.
[2] Glover F, Kochenberger G, editors. Handbook of Metaheuristics. Boston, Dordrecht, London: Kluwer Academic Press, 2003. · Zbl 1058.90002
[3] Lokkentagen, A.; Glover, F., Solving 0-1 mixed integer programming problems using tabu search, European journal of operational research, 106, 624-658, (1998) · Zbl 0991.90091
[4] Fischetti, M.; Lodi, A., Local branching, Mathematical programming series B, 98, 23-47, (2003) · Zbl 1060.90056
[5] CPLEX: ILOG CPLEX 7.1 User’s manual and reference manual, 2001.
[6] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and operations research, 24, 1097-1100, (1997) · Zbl 0889.90119
[7] Hansen, P.; Mladenović, N., Variable neighborhood search: principles and applications, European journal of operational research, 130, 449-467, (2001) · Zbl 0981.90063
[8] Hansen, P.; Mladenović, N., Variable neighborhood search, (), 145-184 · Zbl 1102.90371
[9] Hansen, P.; Mladenović, N., Developments of variable neighborhood search, (), 415-440 · Zbl 1017.90130
[10] Glover, F.; Laguna, M., General purpose heuristics for integer programming: part I, Journal of heuristics, 2, 343-358, (1997) · Zbl 0887.90123
[11] Glover, F.; Laguna, M., General purpose heuristics for integer programming: part II, Journal of heuristics, 3, 161-179, (1997) · Zbl 0898.90094
[12] Fischetti M, Polo C, Scantamburlo M. A Local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem. Networks 2004;61-72. · Zbl 1055.90054
[13] Balas, E.; Schmieta, S.; Wallace, C., Pivot and shift—a mixed integer programming heuristic, Discrete optimization, 1, 3-12, (2004) · Zbl 1087.90052
[14] Balas, E.; Martin, C.H., Pivot and complement—a heuristic for 0-1 programming, Management science, 26, 86-96, (1980) · Zbl 0442.90060
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.