Pareto optima of multicriteria integer linear programs

DOI10.1287/IJOC.1080.0277zbMATH Open1243.90192OpenAlexW1978087936MaRDI QIDQ2901044FDOQ2901044

Authors Jesús A. De Loera, Raymond Hemmecke, Matthias Köppe

Publication date 28 July 2012

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.1362

zbMATH Keywords

computational complexityanalysis of algorithmsinteger programmingmulticriteria programming

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Integer programming (90C10)

Abstract: We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered fixed constants. In particular we construct: 1. polynomial-time algorithms to exactly determine the number of Pareto optima and Pareto strategies; 2. a polynomial-space polynomial-delay prescribed-order enumeration algorithm for arbitrary projections of the Pareto set; 3. an algorithm to minimize the distance of a Pareto optimum from a prescribed comparison point with respect to arbitrary polyhedral norms; 4. a fully polynomial-time approximation scheme for the problem of minimizing the distance of a Pareto optimum from a prescribed comparison point with respect to the Euclidean norm.

Recommendations

• On a multicriteria problem of integer linear programming
• scientific article; zbMATH DE number 4076985
• Publication:4939985
• On the number of criteria needed to decide Pareto optimality
• Finding the set of alternatives in discrete multicriterion problems

Cited in

(19)

• A note on global Pareto optimality in multicriteria optimization problems
• scientific article; zbMATH DE number 614558 (Why is no real title available?)
• scientific article; zbMATH DE number 7351034 (Why is no real title available?)
• On a multicriteria problem of integer linear programming
• scientific article; zbMATH DE number 7339100 (Why is no real title available?)
• A new complexity result on multiobjective linear integer programming using short rational generating functions
• A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization
• PolySCIP
• scientific article; zbMATH DE number 4010232 (Why is no real title available?)
• Computation of several power indices by generating functions
• Integrating Pareto optimization into dynamic programming
• scientific article; zbMATH DE number 4076985 (Why is no real title available?)
• Branch-and-Bound for Biobjective Mixed-Integer Linear Programming
• Short Presburger Arithmetic Is Hard
• A mathematical programming approach to the computation of the omega invariant of a numerical semigroup
• Pareto-optimal and lexicographic solutions to mixed-integer problems of linear form in continuous variables
• Characteruzation of pareto optimal points in problems with mult-eqality constraints
• Efficient Storage of Pareto Points in Biobjective Mixed Integer Programming
• Polyhedral omega: a new algorithm for solving linear Diophantine systems

This page was built for publication: Pareto optima of multicriteria integer linear programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2901044)