Abstract
We introduce DISTANCE INDUCED NEIGHBOURHOOD SEARCH (DINS), aMIP improvement heuristic that tries to find improved MIP feasible solutions from a givenMIP feasible solution. DINS is based on a variation of local search that is embedded in an exact MIP solver, namely a branch-and-bound or a branch-and-cut MIP solver. The key idea is to use a distancemetric between the linear programming relaxation optimal solution and the currentMIP feasible solution to define search neighbourhoods at different nodes of the search tree generated by the exact solver. DINS considers each defined search neighbourhood as a new MIP problem and explores it by an exact MIP solver with a certain node limit. On a set of standard benchmark problems, DINS outperforms the MIP improvement heuristics Local Branching due to Fischetti and Lodi and Relaxation Induced Neighbourhood Search due to Danna, Rothberg, and Pape, as well as the generic commercial MIP solver Cplex.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G.: Octane: a new heuristic for pure 0-1 programs. Operations Research 49(2), 207–225 (2001)
Balas, E., Martin, C.H.: Pivot and complement – a heuristic for 0-1 programming. Management Science 26(1), 86–96 (1980)
Balas, E., Martin, C.H.: Pivot and shift – a heuristic for mixed integer programming. Technical report, GSIA, Carnegie Mellon University (1986)
Balas, E., Schmieta, S., Wallace, C.: Pivot and shift – a mixed integer programming heuristic. Discrete Optimization 1, 3–12 (2004)
Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhhods to improve mip solutions. Mathematical Programming 102, 71–90 (2005)
DEIS. Library of instances, http://www.or.deis.unibo.it/research_pages/ORinstances/
Faaland, B.H., Hillier, F.S.: Interior path methods for heuristic integer programming procedures. Operations Research 27(6), 1069–1087 (1979)
Fischetti, M., Glover, F., Lodi, A.: The feasibilty pump. To be appeared on Mathematical Programming
Fischetti, M., Lodi, A.: Local branching. Mathematical Programming B 98, 23–49 (2003)
Ghosh, S.: Description of all the used benchmark instances in this paper, http://www.cs.ualberta.ca/~shubhash/dins/benchmarks.ps
Ghosh, S.: Implementation of DINS, http://www.cs.ualberta.ca/~shubhash/codes.html
Hillier, F.S.: Efficient heuristic procedures for integer linear programming with an interior. Operations Research 17(4), 600–637 (1969)
Ibaraki, T., Ohashi, T., Mine, H.: A heuristic algorithm for mixed-integer programming problems. Math. Program. Study. 2, 115–136 (1974)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Løkketangen, A., Jörnsten, K., Storøy, S.: Tabu search within a pivot and complement framework. International Transactions in Operational Research 1(3), 305–317 (1994)
Løkketangen, A., Woodruff, D.L.: Integrating pivot based search with branch and bound for binary mip’s. Control and Cybernetics (Special issue on Tabu Search) 29(3), 741–760 (2001)
Martin, A., Achterberg, T., Koch, T.: Miplib (2003), http://miplib.zib.de
Nediak, M., Eckstein, J.: Pivot, cut, and dive: A heuristic for mixed 0-1 integer programming. RUTCOR Research Report, RRR 53-2001 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Ghosh, S. (2007). DINS, a MIP Improvement Heuristic. In: Fischetti, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2007. Lecture Notes in Computer Science, vol 4513. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72792-7_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-72792-7_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72791-0
Online ISBN: 978-3-540-72792-7
eBook Packages: Computer ScienceComputer Science (R0)