The Parallel Epsilon Algorithm for Triobjective Integer Optimization Problems

References

• Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. Amer. Federation Inform. Processing Soc. Proc. AFIPS‘67 Spring Joint Comput. Conf. April 18–20 1967 Atlantic City New Jersey USA, vol. 30 (AFIPS/ACM/Thomson Book Company, Washington, DC), 483–485. Google Scholar
• Avis D, Fukuda K (1996) Reverse search for enumeration. Discrete Appl. Math. 65(1–3):21–46.Crossref, Google Scholar
• Barlas GD (2022) Multicore and GPU Programming: An Integrated Approach, 2nd ed. (Elsevier, Amsterdam).Google Scholar
• Benson HP (1998) An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J. Global Optim. 13(1):1–24.Crossref, Google Scholar
• Bökler F, Nemesch L (2023) TriPoD: Engineering the first polynomial delay solver for tri-objective linear programming. MA thesis, Osnabrück University, Osnabrück, Germany.Google Scholar
• Boland N, Charkhgard H, Savelsbergh MWP (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 MWP (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
• Bücker HM, Löhne A, Weiβing B, Zumbusch GW (2018) On parallelizing Benson’s algorithm: Limits and opportunities. Gervasi O, Murgante B, Misra S, Stankova EN, Torre CM, Rocha AMAC, Taniar D, Apduhan BO, Tarantino E, Ryu Y, eds. Comput. Sci. Its Appl. ICCSA 2018 18th Internat. Conf. Melbourne VIC Australia July 2–5 2018 Proc. Part II, vol. 10961 (Springer, Cham, Switzerland), 653–668.Google Scholar
• Chankong V, Haimes YY (1983) Multiobjective Decision Making: Theory and Methodology (North Holland, New York).Google Scholar
• Dächert K, Klamroth K (2015) A linear bound on the number of scalarizations needed to solve discrete tricriteria optimzation problems. J. Global Optim. 61(4):643–676.Crossref, Google Scholar
• Dächert K, Fleuren T, Klamroth K (2024) A simple, efficient and versatile objective space algorithm for multiobjective integer programming. Math. Methods Oper. Res. 100(1):351–384.Crossref, Google Scholar
• Dächert K, Klamroth K, Lacour R, Vanderpooten D (2017) Efficient computation of the search region in multi-objective optimization. Eur. J. Oper. Res. 260(3):841–855.Crossref, Google Scholar
• Dagum L, Menon R (1998) OpenMP: An industry standard API for shared-memory programming. IEEE Comput. Sci. Engrg. 5(1):46–55.Crossref, Google Scholar
• Dhaenens C, Lemesre J, Talbi E (2010) K-PPM: A new exact method to solve multi-objective combinatorial optimization problems. Eur. J. Oper. Res. 200(1):45–53.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Ehrgott M (2005) Multicriteria Optimization, 2nd ed. (Springer, Berlin).Google Scholar
• Falcón-Cardona JG, Gómez RH, Coello CAC, Tapia MGC (2021) Parallel multi-objective evolutionary algorithms: A comprehensive survey. Swarm Evolutionary Comput. 67:100960.Crossref, Google Scholar
• Figueira JR, Fonseca CM, Halffmann P, Klamroth K, Paquete L, Ruzika S, Schulze B, Stiglmayr M, Willems D (2017) Easy to say they are hard, but hard to see they are easy—Towards a categorization of tractable multiobjective combinatorial optimization problems. J. Multi-Criteria Decision Anal. 24(1–2):82–98.Crossref, Google Scholar
• Gurobi Optimization (2023) Gurobi optimizer reference manual. Accessed May 15, 2024, https://www.gurobi.com/.Google Scholar
• Haimes YY, Lasdon LS, Wismer DA (1971) On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans. Systems Man Cybernetics 1(3):296–297.Crossref, Google Scholar
• Halffmann P, Schäfer LE, Dächert K, Klamroth K, Ruzika S (2022) Exact algorithms for multiobjective linear optimization problems with integer variables: A state of the art survey. J. Multi-Criteria Decision Anal. 29(5–6):341–363.Crossref, Google Scholar
• IBM (2023) IBM ILOG CPLEX Optimization Studio documentation. Accessed May 15, 2024, https://www.ibm.com/docs/en/icos.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, Sayın 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
• Klamroth K, Lacour R, Vanderpooten D (2015) On the representation of the search region in multi-objective optimization. Eur. J. Oper. Res. 245(3):767–778.Crossref, Google Scholar
• Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur. J. Oper. Res. 169(3):932–942.Crossref, Google Scholar
• Lemesre J, Dhaenens C, Talbi E (2007) Parallel partitioning method (PPM): A new exact method to solve bi-objective problems. Comput. Oper. Res. 34(8):2450–2462.Crossref, Google Scholar
• Ozlen M, Burton BA, MacRae CAG (2014) Multi-objective integer programming: An improved recursive algorithm. J. Optim. Theory Appl. 160(2):470–482.Crossref, Google Scholar
• Pettersson W, Ozlen M (2020) Multiobjective integer programming: Synergistic parallel approaches. INFORMS J. Comput. 32(2):461–472.Abstract, Google Scholar
• Prinz K, Ruzika S (2025) The parallel epsilon algorithm for triobjective integer optimization problems. https://doi.org/10.1287/ijoc.2024.0798.cd, https://github.com/INFORMSJoC/2024.0798.Google Scholar
• Przybylski A, Gandibleux X, Ehrgott M (2010a) A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS J. Comput. 22(3):371–386.Link, Google Scholar
• Przybylski A, Gandibleux X, Ehrgott M (2010b) 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
• Sahni S, Thanvantri V (1996) Performance metrics: Keeping the focus on runtime. IEEE Parallel Distrib. Tech. Syst. Appl. 4(1):43–56. Crossref, Google Scholar
• Santis MD, Eichfelder G, Patria D (2022) On the exactness of the ϵ-constraint method for biobjective nonlinear integer programming. Oper. Res. Lett. 50(3):356–361.Crossref, Google Scholar
• Stidsen TR, Andersen KA (2018) A hybrid approach for biobjective optimization. Discrete Optim. 28:89–114.Crossref, 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
• 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