Pareto optima of multicriteria integer linear programs

DOI10.1287/IJOC.1080.0277zbMATH Open1243.90192arXiv0707.1362OpenAlexW1978087936MaRDI 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)

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.

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

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

zbMATH Keywords

computational complexityanalysis of algorithmsinteger programmingmulticriteria programming

Mathematics Subject Classification ID

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

Cited In (19)

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

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)