Primal Heuristics for Branch and Price: The Assets of Diving Methods

References

• Achterberg T, Berthold T (2007) Improving the feasibility pump. Discrete Optim. 4(1):77–86.Crossref, Google Scholar
• Agarwal Y, Mathur K, Salkin HM (1989) A set-partitioning-based exact algorithm for the vehicle routing problem. Networks 19(7):731–749.Crossref, Google Scholar
• Ahuja RK, Ergun Ö, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123(1–3):75–102.Crossref, Google Scholar
• Alfandari L, Plateau A, Schepler X (2015) A branch-and-price-and-cut approach for sustainable crop rotation planning. Eur. J. Oper. Res. 241(3):872–879.Crossref, Google Scholar
• Angelelli E, Bianchessi N, Filippi C (2014) Optimal interval scheduling with a resource constraint. Comput. Oper. Res. 51(November):268–281.Crossref, Google Scholar
• Belov G, Scheithauer G (2002) A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. Eur. J. Oper. Res. 141(2):274–294.Crossref, Google Scholar
• Bertacco L, Fischetti M, Lodi A (2007) A feasibility pump heuristic for general mixed-integer problems. Discrete Optim. 4(1):63–76.Crossref, Google Scholar
• Berthold T (2006) Primal heuristics for mixed integer programs. Unpublished master’s thesis, Technische Universität Berlin, Berlin.Google Scholar
• Bianchessi N, Mansini R, Speranza M (2014) The distance constrained multiple vehicle traveling purchaser problem. Eur. J. Oper. Res. 235(1):73–87.Crossref, Google Scholar
• Bixby B (2011) The Gurobi Optimizer. Presentation, Integer Programming Down Under: Theory, Algorithms and Applications Workshop, July 8, University of Newcastle, Newcastle, NSW, Australia.Google Scholar
• Cacchiani V, Hemmelmayr V, Tricoire F (2014) A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Appl. Math. 163(1):53–64.Crossref, Google Scholar
• Ceselli A, Righini G, Salani M (2007) A column generation algorithm for a vehicle routing problem with economies of scale and additional constraints. Proc. TRISTAN 6th Triennial Sympos. Transportation Anal., Phuket, Thailand.Google Scholar
• Chabrier A, Danna E, Le Pape C (2002) Coopération entre génération de colonnes et recherche locale appliquées au problème de routage de véhicules. Huitièmes Journées Nationales sur la résolution de Problèmes NP-Complets, Nice, France, 83–97.Google Scholar
• Chabrier A, Danna E, Le Pape C, Perron L (2004) Solving a network design problem. Ann. Oper. Res. 130(1–4):217–239.Crossref, Google Scholar
• Cintra G, Miyazawa FK, Wakabayashi Y, Xavier E (2008) Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. Eur. J. Oper. Res. 191(1):61–85.Crossref, Google Scholar
• Colombo F, Cordone R, Trubian M (2014) Column-generation based bounds for the homogeneous areas problem. Eur. J. Oper. Res. 236(2):695–705.Crossref, Google Scholar
• Danna E, Rothberg E, Pape CL (2005) Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Programming 102(1):71–90.Crossref, Google Scholar
• Davies T, Pearce A, Stuckey P, Søndergaard H (2014) Fragment-based planning using column generation. Chien S, Do M, Fern A, Ruml W, eds. Proc. 24th Internat. Conf. Automated Planning Scheduling (AAAI Press, Palo Alto, CA), 83–91.Crossref, Google Scholar
• Degraeve Z, Jans R (2007) A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot-sizing problem with setup times. Oper. Res. 55(5):909–920.Link, Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Dobson G (1982) Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res. 7(4):515–531.Link, Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1–3):23–47.Crossref, Google Scholar
• Fischetti M, Lodi A (2011) Heuristics in mixed integer programming, Cochran JJ, ed. Wiley Encyclopedia of Operations Research and Management Science, vol. 3 (Wiley, Hoboken, NJ), 2199–2204.Crossref, Google Scholar
• Fischetti M, Salvagnin D (2009) Feasibility pump 2.0. Math. Programming Comput. 1(2/3):201–222.Crossref, Google Scholar
• Fischetti M, Glover F, Lodi A (2005) The feasibility pump. Math. Programming 104(1):91–104.Crossref, Google Scholar
• Galinier P, Hamiez JP, Hao JK, Porumbel D (2013) Recent advances in graph vertex coloring. Zelinka I, Snášel V, Abraham A, eds. Handbook of Optimization, vol. 38 (Springer, Berlin), 505–528.Crossref, Google Scholar
• Gamache M, Soumis F, Marquis G, Desrosiers J (1999) A column generation approach for large-scale aircrew rostering problems. Oper. Res. 47(2):247–263.Link, Google Scholar
• Grötschel M, Borndörfer R, Löbel A (2003) Duty scheduling in public transit. Jäger W, Krebs HJ, eds. Mathematics—Key Technology for the Future (Springer, Berlin), 653–674.Crossref, Google Scholar
• Gunluk O, Kimbrel T, Ladanyi L, Schieber B, Sorkin GB (2006) Vehicle routing and staffing for sedan service. Transportation Sci. 40(3):313–326.Link, Google Scholar
• Harvey WD, Ginsberg ML (1995) Limited discrepancy search. Morgan K, ed. Proc. 14th Internat. Joint Conf. AI 1995, vol. 1 (Morgan Kaufmann, San Francisco), 607–613.Google Scholar
• Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Herz J (1972) Recursive computational procedure for two-dimensional stock cutting. IBM J. Res. Development 16(5):462–469.Crossref, Google Scholar
• Joncour C, Michel S, Sadykov R, Sverdlov D, Vanderbeck F (2010) Column generation based primal heuristics. Electronic Notes Discrete Math. 36(August):695–702.Crossref, Google Scholar
• Kowalczyk D, Leus R (2017) An exact algorithm for parallel machine scheduling with conflicts. J. Scheduling 20(4):355–372.Crossref, Google Scholar
• Kramer HH, Petrucci V, Subramanian A, Uchoa E (2012) A column generation approach for power-aware optimization of virtualized heterogeneous server clusters. Comput. Indust. Engrg. 63(3):652–662.Crossref, Google Scholar
• Linderoth JT, Savelsbergh MWP (1999) A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2):173–187.Link, Google Scholar
• Lübbecke M, Puchert C (2012) Primal heuristics for branch-and-price algorithms. Klatte D, Lüthi HJ, Schmedders K, eds. Operations Research Proceedings, vol. 2011 (Springer, Berlin), 65–70.Google Scholar
• Michel S, Vanderbeck F (2012) A column-generation based tactical planning method for inventory routing. Oper. Res. 60(2):382–397.Link, Google Scholar
• Östergård PRJ (2001) A new algorithm for the maximum-weight clique problem. Nordic J. Comput. 8(4):424–436.Google Scholar
• Perrot N (2005) Integer programming column generation strategies for the cutting stock problem and its variants. Unpublished PhD thesis, Université Bordeaux, Bordeaux, France.Google Scholar
• Pesneau P, Sadykov R, Vanderbeck F (2012) Feasibility pump heuristics for column generation approaches. Klasing R, ed. Experimental Algorithms, Lecture Notes in Computer Science, vol. 7276 (Springer, Berlin), 332–343.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Pisinger D (1997) A minimal algorithm for the 0-1 knapsack problem. Oper. Res. 45(5):758–767.Link, Google Scholar
• Posta M, Ferland JA, Michelon P (2012) An exact method with variable fixing for solving the generalized assignment problem. Comput. Optim. Appl. 52(3):629–644.Crossref, Google Scholar
• Preshing J (2012) A look back at single-threaded CPU performance. Accessed November 5, 2015, http://preshing.com/20120208/a-look-back-at-single-threaded-cpu-performance/.Google Scholar
• Qureshi AG, Taniguchi E, Yamada T (2010) Column generation-based heuristics for vehicle routing problem with soft time windows. J. East. Asia Soc. Transportation Stud. 8:827–841.Google Scholar
• Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS J. Comput. 25(2):244–255.Link, Google Scholar
• Sadykov R, Vanderbeck F, Pessoa A, Uchoa E (2015a) Column generation based heuristic for the generalized assignment problem. Mota C, Daher S, eds. XLVII Simpósio Brasileiro de Pesquisa Operacional, Porto de Galinhas, Brazil, 3624–3631.Google Scholar
• Sadykov R, Lazarev AA, Pessoa A, Uchoa E, Vanderbeck F (2015b) The prominence of stabilization techniques in column generation: The case of freight transportation. Proc. 6th. Internat. Workshop Freight Transportation Logist., Ajaccio, France, 87–90.Google Scholar
• Schmid V, Doerner KF, Hartl RF, Savelsbergh MWP, Stoecher W (2009) A hybrid solution approach for ready-mixed concrete delivery. Transportation Sci. 43(1):70–85.Link, Google Scholar
• Spliet R, Desaulniers G (2015) The discrete time window assignment vehicle routing problem. Eur. J. Oper. Res. 244(2):379–391.Crossref, Google Scholar
• Taillard ÉD (1999) A heuristic column generation method for the heterogeneous fleet VRP. RAIRO Oper. Res. 33(1):1–14.Crossref, Google Scholar
• Titiloye O, Crispin A (2011) Quantum annealing of the graph coloring problem. Discrete Optim. 8(2):376–384.Crossref, Google Scholar
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston), 331–358.Crossref, Google Scholar
• Vanderbeck F (2011) Branching in branch-and-price: A generic scheme. Math. Programming 130(2):249–294.Crossref, Google Scholar
• Vanderbeck F, Savelsbergh MWP (2006) A generic view of Dantzig–Wolfe decomposition in mixed integer programming. Oper. Res. Lett. 34(3):296–306.Crossref, Google Scholar
• Vanderbeck F, Wolsey LA (2010) Reformulation and decomposition of integer programs. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958-2008 (Springer, Berlin), 431–502.Crossref, Google Scholar
• Yagiura M, Ibaraki T, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. Eur. J. Oper. Res. 169(2):548–569.Crossref, Google Scholar