Efficiently Constructing Convex Approximation Sets in Multiobjective Optimization Problems

References

• Alves MJ, Costa JP (2016) Graphical exploration of the weight space in three-objective mixed integer linear programs. Eur. J. Oper. Res. 248(1):72–83.Crossref, Google Scholar
• Aneja YP, Nair PK (1979) Bicriteria transportation problem. Management Sci. 25(1):73–78.Link, Google Scholar
• Barber CB, Dobkin DP, Huhdanpaa H (1996) The quickhull algorithm for convex hulls. ACM Trans. Math. Software 22(4):469–483.Crossref, Google Scholar
• Bazgan C, Hugot H, Vanderpooten D (2009) Implementing an efficient FPTAS for the 0-1 multi-objective knapsack problem. Eur. J. Oper. Res. 198(1):47–56.Crossref, Google Scholar
• Bazgan C, Ruzika S, Thielen C, Vanderpooten D (2022a) The power of the weighted sum scalarization for approximating multiobjective optimization problems. Theory Comput. Systems 66:395–415.Crossref, Google Scholar
• Bazgan C, Herzel A, Ruzika S, Thielen C, Vanderpooten D (2022b) An approximation algorithm for a general class of parametric optimization problems. J. Combinatorial Optim. 43:1328–1358.Crossref, Google Scholar
• Bökler F, Mutzel P (2015) Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. Bansal N, Finocchi I, eds. Proc. 23rd Annual Eur. Sympos. Algorithms, LNCS, vol. 9294 (Springer, Berlin, Heidelberg), 288–299.Google Scholar
• Borrelli F, Bemporad A, Morari M (2003) Geometric algorithm for multiparametric linear programming. J. Optim. Theory Applications 118(3):515–540.Crossref, Google Scholar
• Carstensen PJ (1983) Complexity of some parametric integer and network programming problems. Math. Programming 26(1):64–75.Crossref, Google Scholar
• Chazelle B (1993) An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geometry 10:377–409.Crossref, Google Scholar
• Christofides N (2022) Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum 3(1):1–4.Crossref, Google Scholar
• Daskalakis C, Diakonikolas I, Yannakakis M (2016) How good is the chord algorithm? SIAM J. Comput. 45(3):811–858.Crossref, Google Scholar
• Diakonikolas I (2011) Approximation of multiobjective optimization problems. PhD thesis, Columbia University, New York.Google Scholar
• Diakonikolas I, Yannakakis M (2008) Succinct approximate convex Pareto curves. Teng S-H, ed. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 74–83.Google Scholar
• Eben-Chaime M (1996) Parametric solution for linear bicriteria knapsack models. Management Sci. 42(11):1565–1575.Link, Google Scholar
• Ehrgott M (2005) Multicriteria Optimization (Springer, Berlin).Google Scholar
• Ehrgott M, Löhne A, Shao L (2012) A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming. J. Global Optim. 52(4):757–778.Crossref, Google Scholar
• Eisner MJ, Severance DG (1976) Mathematical techniques for efficient record segmentation in large shared databases. J. ACM 23(4):619–635.Crossref, Google Scholar
• Florios K, Mavrotas G (2014) Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems. Appl. Math. Comput. 237:1–19.Crossref, Google Scholar
• Gal T, Nedoma J (1972) Multiparametric linear programming. Management Sci. 18(7):406–422.Link, Google Scholar
• Gass S, Saaty T (1955) Parametric objective function (Part 2)—Generalization. J. Oper. Res. Soc. Amer. 3(4):395–401.Link, Google Scholar
• Gassner E, Klinz B (2010) A fast parametric assignment algorithm with applications in max-algebra. Networks 55(2):61–77.Crossref, Google Scholar
• Giudici A, Halffmann P, Ruzika S, Thielen C (2017) Approximation schemes for the parametric knapsack problem. Inform. Processing Lett. 120:11–15.Crossref, Google Scholar
• Glaßer C, Reitwießner C, Schmitz H, Witek M (2010) Approximability and hardness in multi-objective optimization. Ferreira F, Löwe B, Mayordomo E, Mendes Gomes L, eds. Proc. 6th Conf. Computability Europe, LNCS, vol. 6158 (Springer, Berlin, Heidelberg), 180–189.Google Scholar
• Goldberg AV, Tarjan RE (1988) A new approach to the maximum-flow problem. J. ACM 35(4):921–940.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (2012) Geometric Algorithms and Combinatorial Optimization, vol. 2 (Springer Science & Business Media, Boston).Google Scholar
• Halffmann P, Dietz T, Przybylski A, Ruzika S (2020) An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem. J. Global Optim. 77:715–742.Crossref, Google Scholar
• Halffmann P, Ruzika S, Thielen C, Willems D (2017) A general approximation method for bicriteria minimization problems. Theoretical Comput. Sci. 695(1–2):1–15.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 Analysis 29(5–6):341–363.Crossref, Google Scholar
• Hamel AH, Löhne A, Rudloff B (2014) Benson type algorithms for linear vector optimization and applications. J. Global Optim. 59(4):811–836.Crossref, Google Scholar
• Helfrich S, Ruzika S, Thielen C (2024a) Efficiently constructing convex approximation sets in multiobjective optimization problems. http://dx.doi.org/10.1287/ijoc.2023.0220.cd, https://github.com/INFORMSJoC/2023.0220.Google Scholar
• Helfrich S, Herzel A, Ruzika S, Thielen C (2022) An approximation algorithm for a general class of multi-parametric optimization problems. J. Combinatorial Optim. 44:1459–1494.Crossref, Google Scholar
• Helfrich S, Herzel A, Ruzika S, Thielen C (2024b) Using scalarizations for the approximation of multiobjective optimization problems: Towards a general theory. Math. Oper. Res. 100:27–63.Crossref, Google Scholar
• Herzel A, Ruzika S, Thielen C (2021a) Approximation methods for multiobjective optimization problems: A survey. INFORMS J. Comput. 33(4):1284–1299.Abstract, Google Scholar
• Herzel A, Bazgan C, Ruzika S, Thielen C, Vanderpooten D (2021b) One-exact approximate Pareto sets. J. Global Optim. 80:87–115.Crossref, Google Scholar
• Holzhauser M, Krumke SO (2017) An FPTAS for the parametric knapsack problem. Inform. Processing Lett. 126:43–47.Crossref, Google Scholar
• Karp RM, Orlin JB (1981) Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math. 3(1):37–45.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• Lust T, Teghem J (2009) Two-phase pareto local search for the biobjective traveling salesman problem. J. Heuristics 16(3):475–510.Crossref, Google Scholar
• Oberdieck R, Diangelakis NA, Nascu I, Papathanasiou MM, Sun M, Avraamidou S, Pistikopoulos EN (2016) On multi-parametric programming and its applications in process systems engineering. Chemical Engrg. Res. Design 116:61–82.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
• Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. Blum A, ed. Proc. 41st Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, New York), 86–92.Google Scholar
• Paquete L, Stützle T (2010) On the performance of local search for the biobjective traveling salesman problem. Coello Coello CA, Dhaenens C, Jourdan L, eds. Advances in Multi-Objective Nature Inspired Computing (Springer, Berlin, Heidelberg), 143–165.Crossref, Google Scholar
• Przybylski A, Gandibleux X, Ehrgott M (2010) 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
• Ruhe G (1988) Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh. Zeitschrift Oper. Res. 32(1):9–27.Crossref, Google Scholar
• Saaty T, Gass S (1954) Parametric objective function (Part 1). J. Oper. Res. Soc. Amer. 2(3):316–319.Link, Google Scholar
• Seidel R (1995) The upper bound theorem for polytopes: An easy proof of its asymptotic version. Comput. Geometry 5(2):115–116.Crossref, Google Scholar
• Vassilvitskii S, Yannakakis M (2005) Efficiently computing succinct trade-off curves. Theoretical Comput. Sci. 348(2–3):334–356.Crossref, Google Scholar
• Williamson DP, Shmoys DB (2011) The Design of Approximation Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Zitzler E, Thiele L, Laumanns M, Fonseca CM, Grunert da Fonseca V (2003) Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans. Evolutionary Comput. 7(2):117–132.Crossref, Google Scholar