Abstract
We present a parallel large neighborhood search framework for finding high quality primal solutions for general mixed-integer programs (MIPs). The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary MIPs, where subsets of the variables are fixed. In contrast to prior approaches, ours does not require a feasible starting solution. We leverage parallelism to perform multiple searches simultaneously, with the objective of increasing the effectiveness of our heuristic. We computationally compare the proposed framework with a state-of-the-art MIP solver in terms of solution quality, scalability, reproducibility, and parallel efficiency. Results show the efficacy of our approach in finding high quality solutions quickly both as a standalone primal heuristic and when used in conjunction with an exact algorithm.
Similar content being viewed by others
References
Achterberg, T.: Constraint integer programming. Ph.D. thesis (2007)
Achterberg, T., Berthold, T.: Improving the feasibility pump. Discrete Optim. 4(1), 77–86 (2007)
Achterberg, T., Berthold, T., Hendel, G.: Rounding and propagation heuristics for mixed integer programming. In: Operations Research Proceedings, 2011, pp. 71–76. Springer (2012)
Bader, D.A., Hart, W.E., Phillips, C.A.: Parallel algorithm design for branch and bound. In: Tutorials on Emerging Methodologies and Applications in Operations Research, Chap. 5. Springer (2005)
Baena, D., Castro, J.: Using the analytic center in the feasibility pump. Oper. Res. Lett. 39(5), 310–317 (2011)
Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G.: Octane: a new heuristic for pure 0–1 programs. Oper. Res. 49(2), 207–225 (2001)
Balas, E., Schmieta, S., Wallace, C.: Pivot and shift-a mixed integer programming heuristic. Discrete Optim. 1(1), 3–12 (2004)
Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discrete Optim. 4(1), 63–76 (2007)
Berthold, T.: Primal heuristics for mixed integer programs. Diploma Thesis, Technische Universitat Berlin (2006)
Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611–614 (2013)
Berthold, T.: Rens. Math. Program. Comput. 6(1), 33–54 (2014)
Berthold, T., Hendel, G.: Shift-and-propagate. J. Heuristics 21(1), 73–106 (2015)
Bixby, R., Gu, Z., Rothberg, E.: Gurobi optimization (2010). http://www.gurobi.com/
Boland, N.L., Eberhard, A.C., Engineer, F.G., Fischetti, M., Savelsbergh, M.W.P., Tsoukalas, A.: Boosting the feasibility pump. Math. Program. Comput. 6(3), 255–279 (2014). doi:10.1007/s12532-014-0068-9
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)
Corporation, I.B.M.: Ibm cplex optimizer (2015). http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/
Danna, E.: Performance variability in mixed integer programming. In: Presentation at Workshop on Mixed Integer Programming. http://coral.ie.lehigh.edu/mip-2008/talks/danna.pdf (2008)
Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve mip solutions. Math. Program. 102(1), 71–90 (2005)
Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104(1), 91–104 (2005)
Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1–3), 23–47 (2003)
Fischetti, M., Lodi, A.: Repairing mip infeasibility through local branching. Comput. Oper. Res. 35(5), 1436–1445 (2008). (Part Special Issue: Algorithms and Computational Methods in Feasibility and Infeasibility)
Fischetti, M., Lodi, A.: Heuristics in Mixed Integer Programming. Wiley, London (2010)
Fischetti, M., Lodi, A., Monaci, M., Salvagnin, D., Tramontani, A.: Improving branch-and-cut performance by random sampling. Math. Program. Comput. 8(1), 113–132 (2016)
Fischetti, M., Monaci, M.: Proximity search for 0–1 mixed-integer convex programming. J. Heuristics 20(6), 709–731 (2014)
Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. Comput. 1(2–3), 201–222 (2009)
Gamrath, G., Berthold, T., Heinz, S., Winkler, M.: Structure-based primal heuristics for mixed integer programming, pp. 37–53. Springer, Japan, Tokyo (2016)
Ghosh, S.: Dins, a mip improvement heuristic. Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4513, pp. 310–323. Springer, Berlin, Heidelberg (2007)
Glover, F., Laguna, M.: General purpose heuristics for integer programming–part i. J. Heuristics 2(4), 343–358 (1997)
Glover, F., Laguna, M.: General purpose heuristics for integer programming–part ii. J. Heuristics 3(2), 161–179 (1997)
Glover, F., LøKketangen, A., Woodruff, D.L.: Scatter Search to Generate Diverse MIP Solutions, pp. 299–317. Springer, Boston (2000)
Goel, V., Furman, K.C., Song, J.H., El-Bakry, A.S.: Large neighborhood search for lng inventory routing. J. Heuristics 18(6), 821–848 (2012)
Gropp, W., Lusk, E., Doss, N., Skjellum, A.: A high-performance, portable implementation of the MPI message passing interface standard. Parallel Comput. 22(6), 789–828 (1996)
Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search and local branching. Comput. Oper. Rese. 33(10), 3034–3045 (2006). (Part Special Issue: Constraint Programming)
Hendel, G.: New rounding and propagation heuristics for mixed integer programming. Bachelor’s thesis, TU Berlin (2011)
Hewitt, M., Nemhauser, G.L., Savelsbergh, M.W.P.: Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS J. Comput. 22(2), 314–325 (2010)
Koc, U., Mehrotra, S.: Generation of feasible integer solutions on a massively parallel computer (submitted)
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Mathematical Programming Computation 3(2), 103–163 (2011)
Koch, T., Ralphs, T., Shinano, Y.: Could we use a million cores to solve an integer program? Math. Methods Oper. Res. 76(1), 67–93 (2012)
Mercé, C., Fontan, G.: Mip-based heuristics for capacitated lotsizing problems. Int. J. Prod. Econ. 85(1), 97–111 (2003). (Planning and Control of Productive Systems)
Munguía, L.M., Ahmed, S., Bader, D.A., Nemhauser, G.L., Goel, V., Shao, Y.: A parallel local search framework for the fixed-charge multicommodity network flow problem. Comput. Oper. Res. 77, 44–57 (2017)
Naoum-Sawaya, J.: Recursive central rounding for mixed integer programs. Comput. Oper. Res. 43, 191–200 (2014)
Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19(4), 534–541 (2007)
Shao, Y., Furman, K.C., Goel, V., Hoda, S.: A hybrid heuristic strategy for liquefied natural gas inventory routing. Transp. Res. C: Emerg. Technol. 53, 151–171 (2015)
Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: Parascip: a parallel extension of scip. In: Competence in High Performance Computing, 2010, pp. 135–148. Springer (2012)
Thakur, R., Rabenseifner, R., Gropp, W.: Optimization of collective communication operations in mpich. Int. J. High Perform. Comput. Appl. 19(1), 49–66 (2005)
Wallace, C.: Zi round, a mip rounding heuristic. J. Heuristics 16(5), 715–722 (2010)
Acknowledgements
We wish to thank the referees, whose comments led to an improved version of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been supported in part by ExxonMobil Upstream Research Company, the National Science Foundation, the Office of Naval Research and the Air Force Office of Scientific Research.
Rights and permissions
About this article
Cite this article
Munguía, LM., Ahmed, S., Bader, D.A. et al. Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs. Comput Optim Appl 69, 1–24 (2018). https://doi.org/10.1007/s10589-017-9934-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-017-9934-5