Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Aneja YP, Nair KPK (1979) Bicriteria transportation problem. Management Sci. 25(1):73–78.Link, Google Scholar
• Bérubé JF, Gendreau M, Potvin JY (2009) An exact ϵ-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
• Chalmet LG, Lemonidis L, Elzinga DJ (1986) An algorithm for the bi-criterion integer programming problem. Eur. J. Oper. Res. 25(2):292–300.Crossref, Google Scholar
• Cohon JL (1978) Multiobjective Programming and Planning (Academic Press, London).Google Scholar
• Dial RB (1979) A model and algorithm for multicriteria route-mode choice. Transportation Res. Part B: Methodology 13(4):311–316.Crossref, Google Scholar
• Ehrgott M (2005) Multicriteria Optimization, 2nd ed. (Springer, Berlin).Google Scholar
• Ehrgott M, Gandibleux X (2007) Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. 34(9):2674–2694.Crossref, Google Scholar
• Fernandez E, Puerto J (2003) Multiobjective solution of the uncapacitated plant location problem. Eur. J. Oper. Res. 145(3):509–529.Crossref, Google Scholar
• Florios K, Mavrotas G, Diakoulaki D (2010) Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms. Eur. J. Oper. Res. 203(1):14–21.Crossref, Google Scholar
• Franklin WR (2006) PNPOLY—point inclusion in polygon test. Accessed December 13, 2018, http://www.ecse.rpi.edu/∼wrf/Research/Short\_Notes/pnpoly.html.Google Scholar
• Gadegaard SL, Klose A, Nielsen LR (2017) An improved cut-and-solve algorithm for the single-source capacitated facility location problem. Eur. J. Comput. Optim. 6(1):1–27.Google Scholar
• Gadegaard SL, Nielsen LR, Ehrgott M (2016a) A branch and cut algorithm for bi–objective combinatorial optimization problems. Accessed December 13, 2018, https://github.com/SuneGadegaard/BiObjectiveBranchAndCut.Google Scholar
• Gadegaard SL, Nielsen LR, Ehrgott M (2016b) A general two–phase method for bi–objective combinatorial optimization. Accessed December 13, 2018, https://github.com/SuneGadegaard/TwoPhaseMethod.Google Scholar
• Gadegaard SL, Nielsen LR, Ehrgott M (2016c) An instance generator for the capacitated facility location problem. Accessed December 13, 2018, https://github.com/SuneGadegaard/SSCFLPgenerator.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
• 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
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, New York).Google Scholar
• Martin RK (1999) Large Scale Linear and Integer Optimization: A Unified Approach (Kluwer Academic Publishers, Norwell, MA).Crossref, Google Scholar
• Mavrotas G, Diakoulaki D (1998) A branch and bound algorithm for mixed zero-one multiple objective linear programming. Eur. J. Oper. Res. 107(3):530–541.Crossref, Google Scholar
• Mavrotas G, Diakoulaki D (2005) Multi-criteria branch and bound: A vector maximization algorithm for mixed 0-1 multiple objective linear programming. Appl. Math. Comput. 171(1):53–71.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Crossref, Google Scholar
• Parragh S, Tricoire F (2015) Branch-and-bound for bi-objective integer programming. Working paper, University of Vienna, Vienna, Austria.Google Scholar
• Pedersen CR, Nielsen LR, Andersen KA (2008) The bicriterion multimodal assignment problem: Introduction, analysis, and experimental results. INFORMS J. Comput. 20(3):400–411.Link, 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 (2008) Two phase algorithms for the bi-objective assignment problem. Eur. J. Oper. Res. 185(2):509–533.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
• Ramos RM, Alonso S, Sicilia J, González C (1998) The problem of the optimal biobjective spanning tree. Eur. J. Oper. Res. 111(3):617–628.Crossref, Google Scholar
• Schirra S (2008) How reliable are practical point-in-polygon strategies? Halperin D, Mehlhorn K, eds. Algorithms, Lecture Notes in Computer Science, vol. 5193 (Springer, Berlin), 744–755.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
• 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
• Ulungu EL, Teghem J (1997) Solving multi-objective knapsack problem by a branch-and-bound procedure. Climaco J, ed. Multicriteria Analysis (Springer, Berlin), 269–278.Google Scholar
• Vincent T (2013) Caractérisation des solutions efficaces et algorithmes d’énumération exacts pour l’optimisation multiobjectif en variables mixtes binaires. Unpublished PhD thesis, Université de Nantes, Nantes, France.Google Scholar
• Vincent T, Seipp F, Ruzika S, Przybylski A, Gandibleux X (2013) Multiple objective branch and bound for mixed 0-1 linear programming: Corrections and improvements for the biobjective case. Comput. Oper. Res. 40(1):498–509.Crossref, Google Scholar
• Visée M, Teghem J, Pirlot M, Ulungu EL (1998) Two-phases method and branch and bound procedures to solve the bi–objective knapsack problem. J. Global Optim. 12(2):139–155.Crossref, Google Scholar