New variable neighbourhood search based 0-1 MIP heuristics
DOI:
https://doi.org/10.2298/YJOR140219014HKeywords:
0-1 mixed Integer Programming, matheuristics, variable neighbourhood search, pseudo-cuts, convergenceAbstract
In recent years many so-called matheuristics have been proposed for solving Mixed Integer Programming (MIP) problems. Though most of them are very efficient, they do not all theoretically converge to an optimal solution. In this paper we suggest two matheuristics, based on the variable neighbourhood decomposition search (VNDS), and we prove their convergence. Our approach is computationally competitive with the current state-of-the-art heuristics, and on a standard benchmark of 59 0-1 MIP instances, our best heuristic achieves similar solution quality to that of a recently published VNDS heuristic for 0-1 MIPs within a shorter execution time.References
Ahuja, R.K., Ergun, Ö., Orlin, J.B., and Punnen, A.P., “A Survey of Very Large-Scale Neighborhood Search Techniques”, Discrete Applied Mathematics, 123(1-3) (2002) 75–102.
Ashford, R., “Mixed Integer Programming: A Historical Perspective with Xpress-MP”, Annals of Operations Research, 149(1) (2007) 5–17.
Danna, E., Rothberg, E., and Le Pape, C., “Exploring Relaxation Induced Neighborhoods to Improve MIP Solutions”, Mathematical Programming, 102(1) (2005) 71–90.
Fischetti, M., and Lodi, A., “Local Branching”, Mathematical Programming, 98(2) (2003) 23–47.
FortMP Manual Release 3. Numerical Algorithms Group Limited, 1999.
Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP Completeness. WH Freeman, San Francisco, 1979.
Glover, F., “Adaptive Memory Projection Methods for Integer Programming”, In Metaheuristic Optimization Via Memory and Evolution, C. Rego and B. Alidaee, Eds., Kluwer Academic Publishers, 425–440, 2005.
Glover, F., “Parametric Tabu Search for Mixed Integer Programs”, Computers and Operations Research, 33 (2006) 2449–2494.
Glover, F., and Hanafi, S., “Metaheuristic Search with Inequalities and Target Objectives for Mixed Binary Optimization Part I: Exploiting Proximity”, International Journal of Applied Metaheuristic Computing, 1 (2010) 1–15.
Glover, F., and Hanafi, S., “Metaheuristic Search with Inequalities and Target Objectives for Mixed Binary Optimization Part II: Exploiting Reaction and Resistance”, International Journal of Applied Metaheuristic Computing, 2 (2010) 1–17.
Lasdon, L., Glover, F., Plummer, J., Duarte, A., Marti, R., Laguna, M., and Rego, C., “Pseudo-Cut Strategies for Global Optimization”, International Journal of Applied Metaheuristic Computing, 2 (2011) 1–12.
Gurobi Optimization Inc., Gurobi Optimizer Reference Manual, Version 2.0, 2009.
Hanafi, S., and Wilbaut, C., “Heuristiques Convergentes Basées sur des Relaxations”, Presented at ROADEF 2006, Lille (February), 2006.
Hanafi, S., and Wilbaut, C., “Improved Convergent Heuristics for the 0-1 Multidimensional Knapsack Problem”, Annals of Operations Research, 183(1) (2011) 125–142.
Hansen, P., Mladenović, N., and Pérez-Britos, D., “Variable Neighborhood Decomposition Search”, Journal of Heuristics, 7(4) (2001) 335–350.
Hansen, P., Mladenović, N., and Urošević, D., “Variable Neighborhood Search and Local Branching”, Computers & Operations Research, 33(10) (2006) 3034–3045.
ILOG, CPLEX 11.2 User’s Manual, 2008.
Lasdon, L., Duarte, A., Glover, F., Laguna, M., and Marti, R., “Adaptive Memory Programming for Constrained Global Optimization”, Computers & Operations Research, 37 (2010) 1500–1509.
Laundy, R., Perregaard, M., Tavares, G., Tipi, H., and Vazacopoulos, A., “Solving Hard Mixed Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study”, Technical Report RRR2-2007, Rutcor Research Report, January 2007.
Lazić, J., Hanafi, S., Mladenović, N., and Urošević, D., “Variable Neighbourhood Decomposition Search for 0–1 Mixed Integer Programs”, Computers and Operations Research, 37(6) (2010) 1055–1067.
Lingo Systems Inc., Optimization Modeling with LINGO, 6th Edition, 2006.
Maniezzo, V., Stutzle, T., and Voss, S. (eds.), Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, Volume 10 of Annals of Information Systems, Springer, 2009.
Mladenović, N., and Hansen, P., “Variable Neighborhood Search”, Computers & Operations Research, 24(11) (1997) 1097–1100.
Shaw, P., “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems”, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, 417–431, 1998.
Soyster, A.L., Lev, B., and Slivka, W., “Zero-One Programming with Many Variables and Few Constraints”, European Journal of Operational Research, 2(3) (1978) 195–201.
Wilbaut, C., and Hanafi, S., “New Convergent Heuristics for 0–1 Mixed Integer Programming”, European Journal of Operational Research, 195 (2009) 62–74.
Wilbaut, C., Hanafi, S., Fréville, A., and Balev, S., “Tabu Search: Global Intensification Using Dynamic Programming”, Control and Cybernetics, 35(3) (2006) 579–598.
Downloads
Published
Issue
Section
License
Copyright (c) 2015 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
