Variable and single neighbourhood diving for MIP feasibility
DOI:
https://doi.org/10.2298/YJOR140417027LKeywords:
mixed integer programming, constructive heuristics, feasibility pump, CPLEXAbstract
In this paper, we propose two new diving heuristics for finding a feasible solution for a mixed integer programming problem, called variable neighbourhood (VN) diving and single neighbourhood (SN) diving, respectively. They perform systematic hard variable fixing (i.e. diving) by exploiting the information obtained from a series of LP relaxations in order to generate a sequence of subproblems. Pseudo cuts are added during the search process to avoid revisiting the same search space areas. VN diving is based on the variable neighbourhood decomposition search framework. Conversely, SN diving explores only a single neighbourhood in each iteration: if a feasible solution is not found, then the next reference solution is chosen using the feasibility pump principle and the search history. Moreover, we prove that the two proposed algorithms converge in a finite number of iterations (i.e. either return a feasible solution of the input problem, or prove its infeasibility). We show that our proposed algorithms significantly outperform the CPLEX 12.4 MIP solver and the recent variants of feasibility pump regarding the solution quality.References
Achterberg, T., and Berthold, T., “Improving the feasibility pump”, Discrete Optimization, 4 (2007) 77-86.
Balas, E., and Zemel, E., “An algorithm for large zero-one knapsack problems”, Operations Research, (1980) 1130-1154.
Bertacco, L., Fischetti, M., and Lodi, A., “A feasibility pump heuristic for general mixed-integer problems”, Discrete Optimization, 4 (2007) 63-76.
Berthold, T., “RENS- relaxation enforced neighborhood search”, Technical report, ZIB-07-28, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2008.
Brucker, P., Burke, E., and Groenemeyer, S., “A mixed integer programming model for the cyclic job-shop problem with transportation”, Discrete Applied Mathematics, 160 (13) (2012) 1924-1935.
Collet, G., Andonov, R., Yanev, N., and Gibrat, J., “Local protein threading by Mixed Integer Programming”, Discrete Applied Mathematics, 159 (16) (2011) 1707-1716.
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., Glover, F., and Lodi, A., “The feasibility pump”, Mathematical Programming, 104 (2005) 91-104.
Fischetti, M., and Lodi, A., “Local branching”, Mathematical Programming, 98 (2) (2003) 23-47.
Fischetti, M., and Lodi, A., “Repairing mip infeasibility through local branching”, Computers & OR, 35 (2008) 1436-1445.
Garey, M., and Johnson, D., Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman, San Francisco, 1979.
Ghosh, S., “DINS, a MIP improvement heuristic”, in: M. Fischetti and D.P. Williamson, (eds.), Proceedings of the Integer Programming and Combinatorial Optimization, vol. 4513 Lecture Notes in Computer Science, Springer, 2007, 310-323.
Hanafi, S., Lazić, J., and Mladenović, N., “Variable neighbourhood pump heuristic for 0-1 mixed integer programming feasibility”, Electronic Notes in Discrete Mathematics, 36 (2010) 59-766.
Hansen, P., and Mladenović, N., “Variable neighborhood search: Principles and applications”, European Journal of Operational Research, 130 (3) (2001) 449-467.
Hansen, P., Mladenović, N., and Perez-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 & OR, 33 (10) (2006) 3034-3045.
Lazić, J., “New variants of variable neighbourhood search for mixed integer programming and clustering”, PhD thesis, Brunel University, West London, UK, 2010.
Lazić, J., Hanafi, S., and Mladenović, N., “Different variants of variable neighbourhood pump for 0-1 MIP feasibility”, 2010. (In preparation)
Lazić, J., Hanafi, S., Mladenović, N., and Urošević, D., “Variable neighbourhood decomposition search for 0–1 mixed integer programs”, Computers & OR, 37 (6) (2010) 1055-1067.
Mitrović-Minić, S., and Punnen, A., “Very large-scale variable neighborhood search for the generalized assignment problem”, Journal of Interdisciplinary Mathematics, 6 (4) (2009) 370–377.
Mitrović-Minić, S., and Punnen, A., “Variable Intensity Local Search”, in: V. Maniezzo, T. Stützle, and S. Voß, (eds.) Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, Springer, 2009, 245-252.
Mitrović-Minić, S., and Punnen, A., “Very large-scale variable neighborhood search for the multi-resource generalized assignment problem”, Discrete Optimization, 6 (4) (2009) 370-377.
Pisinger, D., “An expanding-core algorithm for the exact 0-1 knapsack problem”, European Journal of Operational Research, 87 (1) (1995) 175-187.
Puchinger, J., and Raidl, G.R., “Bringing order into the neighborhoods: Relaxation guided variable neighborhood search”, Journal of Heuristics, 14 (5) (2008) 457-472.
Puchinger, J., Raidl, G.R., and Pferschy, U., “The core concept for the multidimensional knapsack problem”, Lecture Notes in Computer Science, 3906 (2006) 195-208.
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., Salhi, S., and Hanafi, S., “An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem”, European Journal of Operational Research, 199 (2) (2009) 339-348.
Wolsey, L., and Nemhauser, G., Integer and Combinatorial Optimization, 1999.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
