A Polynomial-Time Inner Approximation Algorithm for Multiobjective and Parametric Optimization

References

• Aneja YP, Nair KPK (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, Ruzika S, Thielen C, Vanderpooten D (2022a) The power of the weighted sum scalarization for approximating multiobjective optimization problems. Theory Comput. Systems 66(1):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(5):1328–1358.Crossref, 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 (2018) Output-sensitive complexity of multiobjective combinatorial optimization problems with an application to the multiobjective shortest path problem. PhD thesis, Technische Universität, Dortmund, Germany.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 Eur. Sympos. Algorithms, Lecture Notes in Computer Science (Springer, Berlin), 288–299.Crossref, Google Scholar
• Bökler F, Nemesch L, Wagner MH (2023) PaMILO: A solver for multi-objective mixed integer linear optimization and beyond. Grothe O, Nickel S, Rebennack S, Stein O, eds. Proc. Ann. Internat. Conf. German Oper. Res. Soc., Lecture Notes in Operations Research (Springer, Cham, Switzerland), 163–170.Crossref, Google Scholar
• Bökler F, Parragh S, Sinnl M, Tricoire F (2024) An outer approximation algorithm for generating the Edgeworth-Pareto hull of multi-objective mixed-integer linear programming problems. Math. Methods Oper. Res. 100(1):263–290.Crossref, Google Scholar
• Borndörfer R, Schenker S, Skutella M, Strunk T (2016) PolySCIP. Greuel GM, Koch T, Paule P, Sommese A, eds. Proc. 5th Internat. Congress Math. Software, Lecture Notes in Computer Science (Springer, Cham, Switzerland), 259–264.Crossref, Google Scholar
• Chazelle B (1993) An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geometry 10(4):377–409.Crossref, Google Scholar
• Chimani M, Gutwenger C, Jünger M, Klau GW, Klein K, Mutzel P (2013) The open graph drawing framework (OGDF). Tamassia R, ed. Handbook of Graph Drawing and Visualization (CRC Press, Boca Raton, FL), 543–569.Google Scholar
• Christofides N (2022) Worst-case analysis of a new heuristic for the traveling salesman problem. Oper. Res. Forum 3(1):20.Crossref, Google Scholar
• Csirmaz L (2021) Inner approximation algorithm for solving linear multiobjective optimization problems. Optimization 70(7):1487–1511.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
• 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 SH, ed. Proc. 19th Ann. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 74–83.Google Scholar
• Ehrgott M (2005) Multicriteria Optimization, 2nd ed. (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
• Fukuda K (2021) Cddlib reference manual. Accessed April 7, 2026, https://people.inf.ethz.ch/fukudak/cdd_home/.Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Rational polyhedra. Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics (Springer, Berlin), 157–196.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 (2025) Efficiently constructing convex approximation sets in multiobjective optimization problems. INFORMS J. Comput. 37(5):1223–1241.Link, 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(3):1459–1494.Crossref, Google Scholar
• Herzel A, Ruzika S, Thielen C (2021) Approximation methods for multiobjective optimization problems: A survey. INFORMS J. Comput. 33(4):1284–1299.Abstract, Google Scholar
• Heyde F, Löhne A (2008) Geometric duality in multiple objective linear programming. SIAM J. Optim. 19(2):836–845.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, 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
• Löhne A (2023) Approximate vertex enumeration. J. Comput. Geometry 14(1):257–286.Google Scholar
• Löhne A, Weiβing B (2017) The vector linear program solver bensolve: Notes on theoretical background. Eur. J. Oper. Res. 260(3):807–813.Crossref, Google Scholar
• Löhne A, Rudloff B, Ulus F (2014) Primal and dual approximation algorithms for convex vector optimization problems. J. Global Optim. 60(4):713–736.Crossref, Google Scholar
• Nemesch L, Ruzika S, Thielen C, Wittmann A (2026) A polynomial-time inner approximation algorithm for multiobjective and parametric optimization. https://doi.org/10.1287/ijoc.2025.1308.cd, https://github.com/INFORMSJoC/2025.1308.Google Scholar
• Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. Young DC, ed. Proc. 41st Ann. Sympos. Foundations Comput. Sci. (IEEE, Los Alamitos), 86–92.Google Scholar
• Przybylski A, Klamroth K, Lacour R (2019) A simple and efficient dichotomic search algorithm for multi-objective mixed integer linear programs. Preprint, submitted November 20, https://arxiv.org/abs/1911.08937.Google Scholar
• Sayın 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
• Sayın S (2024) Supported nondominated points as a representation of the nondominated set: An empirical analysis. J. Multi-Criteria Decision Anal. (Oxford) 31(1–2):e1829.Crossref, 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
• Serafini P (1987) Some considerations about computational complexity for multi objective combinatorial problems. Jahn J, Krabs W, eds. Proc. Internat. Conf. Vector Optim., Lecture Notes in Economics and Mathematical Systems (Springer, Berlin), 222–232.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
• Vazirani VV (2003) Approximation Algorithms, 1st ed. (Springer, Berlin).Crossref, Google Scholar
• Ziegler GM (1995) Lectures on Polytopes, Graduate Texts in Mathematics, 1st ed. (Springer, New York).Crossref, Google Scholar