Pareto Optima of Multicriteria Integer Linear Programs

Pareto Optima of Multicriteria Integer Linear Programs

0.00 Avg rating0 Votes
Article ID: iaor200952647
Country: United States
Volume: 21
Issue: 1
Start Page Number: 39
End Page Number: 48
Publication Date: Dec 2009
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: programming: integer
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 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.

Reviews

Required fields are marked *. Your email address will not be published.