Pareto Optima of Multicriteria Integer Linear Programs

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 determine exactly the num...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2009-12, Vol.21 (1), p.39-48
Main Authors: De Loera, Jesus A, Hemmecke, Raymond, Koppe, Matthias
Format: Article
Language:English
Subjects:
Algorithms
analysis of algorithms
Approximation theory
combinatorics
Computational complexity
Hierarchies
Integer programming
Mathematical models
mathematics
Methods
multicriteria programming
Pareto optimum
Polynomials
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 determine exactly 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) a polynomial-time algorithm to minimize the distance of a Pareto optimum from a prescribed comparison point with respect to arbitrary polyhedral norms; and (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.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.1080.0277