Pareto Optima of Multicriteria Integer Linear Programs

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.

17 pages, 1 figure

Cited by in corpus (9)

• Rational Generating Functions and Integer Programming Games
• Computing zeta functions of sparse nondegenerate hypersurfaces
• Efficient storage of Pareto points in biobjective mixed integer programming
• Branch-and-bound for biobjective mixed-integer linear programming
• Short Rational Generating Functions For Multiobjective Linear Integer Programming
• Short Presburger arithmetic is hard
• On the computation of the Omega invariant of a numerical semigroup by optimizing over an efficient integer set
• An Invitation to Ehrhart Theory: Polyhedral Geometry and its Applications in Enumerative Combinatorics
• Integer Programming and m-irreducibility of numerical semigroups