Branch-and-Bound for Biobjective Mixed-Integer Linear Programming

References

• Achterberg T, Wunderling R (2013) Mixed integer programming: Analyzing 12 years of progress. Jünger M, Reinelt G, eds. Facets of Combinatorial Optimization (Springer, Berlin), 449–481.Crossref, Google Scholar
• Achterberg T, Bixby RE, Gu Z, Rothberg E, Weninger D (2020) Presolve reductions in mixed integer programming. INFORMS J. Comput. 32(2):473–506.Link, Google Scholar
• Adelgren N, Gupte A (2016) Branch-and-bound for biobjective mixed-integer linear programming. Preprint, first available at Optimization Online, http://www.optimization-online.org/DB_HTML/2016/10/5676.html.Google Scholar
• Adelgren N, Belotti P, Gupte A (2018) Effecient storage of Pareto points in biobjective mixed integer programming. INFORMS J. Comput. 30(2):324–338.Link, Google Scholar
• Bazgan C, Jamain F, Vanderpooten D (2013) On the number of non-dominated points of a multicriteria optimization problem. Discrete Appl. Math. 161(18):2841–2850.Crossref, Google Scholar
• Bazgan C, Jamain F, Vanderpooten D (2015) Approximate Pareto sets of minimal size for multi-objective optimization problems. Oper. Res. Lett. 43(1):1–6.Crossref, Google Scholar
• Bazgan C, Jamain F, Vanderpooten D (2017) Discrete representation of the non-dominated set for multi-objective optimization problems using kernels. Eur. J. Oper. Res. 260(3):814–827.Crossref, Google Scholar
• Belotti P, Soylu B, Wiecek MM (2012) A branch-and-bound algorithm for biobjective mixed-integer programs. Preprint, December 2012 Optimization-Online, http://www.optimization-online.org/DB_HTML/2013/01/3719.html.Google Scholar
• Belotti P, Soylu B, Wiecek MM (2016) Fathoming rules for biobjective mixed integer linear programs. Discrete Optim. 22:341–363.Google Scholar
• Bérubé J-F, Gendreau M, Potvin J-Y (2009) An exact eps-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits. Eur. J. Oper. Res. 194(1):39–50.Crossref, Google Scholar
• Blanco V, Puerto J (2012) A new complexity result on multiobjective linear integer programming using short rational generating functions. Optim. Lett. 6(3):537–543.Crossref, Google Scholar
• Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective integer programming. INFORMS J. Comput. 27(4):735–754.Link, Google Scholar
• Boland N, Charkhgard H, Savelsbergh M (2016) The L-shape search method for triobjective integer programming. Math. Programming Comput. 8(2):217–251.Crossref, Google Scholar
• Boland N, Charkhgard H, Savelsbergh M (2017) The Quadrant Shrinking method: A simple and efficient algorithm for solving tri-objective integer programs. Eur. J. Oper. Res. 260(3):873–885.Crossref, Google Scholar
• Boland N, Charkhgard H, Savelsbergh M (2019) Preprocessing and cut generation techniques for multi-objective binary programming. Eur. J. Oper. Res. 274(3):858–875.Crossref, Google Scholar
• Burachik RS, Kaya CY, Rizvi M (2017) A new scalarization technique and new algorithms to generate pareto fronts. SIAM J. Optim. 27(2):1010–1034.Crossref, Google Scholar
• Cacchiani V, D’Ambrosio C (2017) A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs. Eur. J. Oper. Res. 260(3):920–933.Crossref, Google Scholar
• Dächert K, Klamroth K (2015) A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems. J. Global Optim. 61(4):643–676.Crossref, Google Scholar
• De Loera JA, Hemmecke R, Köppe M (2009) Pareto optima of multicriteria integer linear programs. INFORMS J. Comput. 21(1):39–48.Link, Google Scholar
• De Santis M, Eichfelder G, Niebling J, Rocktäschel S (2020) Solving multiobjective mixed integer convex optimization problems. SIAM J. Optim. 30(4):3122–3145.Crossref, Google Scholar
• Ehrgott M (2005) Multicriteria Optimization (Springer, Berlin).Google Scholar
• Ehrgott M (2006) A discussion of scalarization techniques for multiple objective integer programming. Ann. Oper. Res. 147(1):343–360.Crossref, Google Scholar
• Ehrgott M, Gandibleux X (2007) Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. 34(9):2674–2694.Crossref, Google Scholar
• Ehrgott M, Ruzika S (2008) Improved eps-constraint method for multiobjective programming. J. Optim. Theory Appl. 138(3):375–396.Crossref, Google Scholar
• Fattahi A, Turkay M (2018) A one direction search method to find the exact nondominated frontier of biobjective mixed-binary linear programming problems. Eur. J. Oper. Res. 266(2):415–425.Crossref, Google Scholar
• Forget N, Klamroth K, Gadegaard SL, Przybylski A, Nielsen LR (2020) Branch-and-bound and objective branching with three objectives. Preprint, December 2020 Optimization-Online, http://www.optimization-online.org/DB_HTML/2020/12/8158.html.Google Scholar
• Gadegaard SL, Nielsen LR, Ehrgott M (2019) Bi-objective branch-and-cut algorithms based on lp relaxation and bound sets. INFORMS J. Comput. 31(4):790–804.Link, Google Scholar
• Gamrath G, Koch T, Martin A, Miltenberger M, Weninger D (2015) Progress in presolving for mixed integer programming. Math. Programming Comput. 7(4):367–398.Crossref, Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel PM, et al. (2021) MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Math. Programming Comput. 13:443–490.Google Scholar
• Grandoni F, Ravi R, Singh M, Zenklusen R (2014) New approaches to multi-objective optimization. Math. Programming 146(1–2):525–554.Crossref, Google Scholar
• Hale JQ, Zhu H, Zhou E (2020) Domination measure: A new metric for solving multiobjective optimization. INFORMS J. Comput. 32(3):565–581.Link, Google Scholar
• Herzel A, Ruzika S, Thielen C (2021) Approximation methods for multiobjective optimization problems. INFORMS J. Comput., ePub ahead of February 5, https://doi.org/10.1287/ijoc.2020.1028.Link, Google Scholar
• Jozefowiez N, Laporte G, Semet F (2012) A generic branch-and-cut algorithm for multiobjective optimization problems: Application to the multilabel traveling salesman problem. INFORMS J. Comput. 24(4):554–564.Link, Google Scholar
• Kirlik G, Sayin S (2014) A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems. Eur. J. Oper. Res. 232(3):479–488.Crossref, Google Scholar
• Kiziltan G, Yucaoğlu E (1983) An algorithm for multiobjective zero-one linear programming. Management Sci. 29(12):1444–1453.Link, Google Scholar
• Klein D, Hannan E (1982) An algorithm for the multiple objective integer linear programming problem. Eur. J. Oper. Res. 9(4):378–385.Crossref, Google Scholar
• Lee J, Vygen J, eds. (2014) The triangle splitting method for biobjective mixed integer programming. Integer Programming Combinatorial Optim. (IPCO), Lecture Notes in Computer Science, vol. 8494 (Springer International Publishing, Berlin), 162–173.Crossref, Google Scholar
• Leitner M, Ljubić I, Sinnl M (2014) A computational study of exact approaches for the bi-objective prize-collecting steiner tree problem. INFORMS J. Comput. 27(1):118–134.Link, Google Scholar
• Leitner M, Ljubić I, Sinnl M, Werner A (2016) Ilp heuristics and a new exact method for bi-objective 0/1 ilps. Comput. Oper. Res. 72:128–146.Crossref, Google Scholar
• Lokman B, Köksalan M (2013) Finding all nondominated points of multi-objective integer programs. J. Global Optim. 57:347–365.Crossref, Google Scholar
• Mavrotas G, Florios K (2013) An improved version of the augmented ε-constraint method (AUG-MECON2) for finding the exact pareto set in multi-objective integer programming problems. Appl. Math. Comput. 219(18):9652–9669.Crossref, Google Scholar
• Mittal S, Schulz AS (2013) A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one. Oper. Res. 61(2):386–397.Link, Google Scholar
• Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19:79–102.Crossref, Google Scholar
• Özpeynirci Ö, Köksalan M (2010) An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Management Sci. 56(12):2302–2315.Link, Google Scholar
• Parragh SN, Tricoire F (2019) Branch-and-bound for bi-objective integer programming. INFORMS J. Comput. 31(4):805–822.Link, Google Scholar
• Perini T, Boland N, Pecin D, Savelsbergh M (2020) A criterion space method for biobjective mixed integer programming: The boxed line method. INFORMS J. Comput. 32(1):16–39.Link, Google Scholar
• Pettersson W, Ozlen M (2020) Multiobjective integer programming: Synergistic parallel approaches. INFORMS J. Comput. 32(2):461–472.Abstract, Google Scholar
• Przybylski A, Gandibleux X (2017) Multi-objective branch and bound. Eur. J. Oper. Res. 260(3):856–872.Crossref, Google Scholar
• Przybylski A, Gandibleux X, Ehrgott M (2010) A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives. Discrete Optim. 7(3):149–165.Crossref, Google Scholar
• Ralphs TK, Saltzman MJ, Wiecek MM (2006) An improved algorithm for solving biobjective integer programs. Ann. Oper. Res. 147(1):43–70.Crossref, Google Scholar
• Rasmi SAB, Türkay M (2019) GoNDEF: An exact method to generate all non-dominated points of multi-objective mixed-integer linear programs. Optim. Engrg. 20(1):89–117.Crossref, Google Scholar
• Royset JO, Wood RK (2007) Solving the bi-objective maximum-flow network-interdiction problem. INFORMS J. Comput. 19(2):175–184.Link, Google Scholar
• Ruzika S, Wiecek MM (2005) Approximation methods in multiobjective programming. J. Optim. Theory Appl. 126(3):473–501.Crossref, Google Scholar
• Sayin S (2000) Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming. Math. Programming 87(3):543–560.Crossref, Google Scholar
• Sayin S (2003) A procedure to find discrete representations of the efficient set with specified coverage errors. Oper. Res. 51(3):427–436.Link, Google Scholar
• Sourd F, Spanjaard O (2008) A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS J. Comput. 20(3):472–484.Link, Google Scholar
• Soylu B (2015) Heuristic approaches for biobjective mixed 0–1 integer linear programming problems. Eur. J. Oper. Res. 245(3):690–703.Crossref, Google Scholar
• Soylu B (2018) The search-and-remove algorithm for biobjective mixed-integer linear programming problems. Eur. J. Oper. Res. 268(1):281–299.Crossref, Google Scholar
• Soylu B, Yildiz GB (2016) An exact algorithm for biobjective mixed integer linear programming problems. Comput. Oper. Res. 72:204–213.Crossref, Google Scholar
• Stanojević M, Vujošević M, Stanojević B (2013) On the cardinality of the nondominated set of multi-objective combinatorial optimization problems. Oper. Res. Lett. 41(2):197–200.Crossref, Google Scholar
• Stidsen T, Andersen KA, Dammann B (2014) A branch and bound algorithm for a class of biobjective mixed integer programs. Management Sci. 60(4):1009–1032.Link, Google Scholar
• Tamby S, Vanderpooten D (2021) Enumeration of the nondominated set of multiobjective discrete optimization problems. INFORMS J. Comput. 33(1):72–85.Link, Google Scholar
• Towns J, Cockerill T, Dahan M, Foster I, Gaither K, Grimshaw A, Hazlewood V, et al. (2014) XSEDE: Accelerating scientific discovery. Comput. Sci. Engrg. 16(5):62–74.Crossref, Google Scholar
• Turgut O, Dalkiran E, Murat AE (2019) An exact parallel objective space decomposition algorithm for solving multi-objective integer programming problems. J. Global Optim. 75(1):35–62.Crossref, Google Scholar
• Vincent T, Seipp F, Ruzika S, Przybylski A, Gandibleux X (2013) Multiple objective branch and bound for mixed 0-1 linear programming. Comput. Oper. Res. 40(1):498–509.Crossref, Google Scholar
• Visée M, Teghem J, Pirlot M, Ulungu E (1998) Two-phases method and branch and bound procedures to solve the biobjective knapsack problem. J. Global Optim. 12:139–155.Google Scholar
• Zitzler E, Thiele L, Laumanns M, Fonseca CM, Da Fonseca VG (2003) Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans. Evolution Comput. 7(2):117–132.Crossref, Google Scholar