ZIB PaperWeb

SC 92-23

Nguyen Ngoc Chu An Algorithm for Optimizing a Linear Function over the Integer Efficient Set.

Abstract: Whereas optimization of a linear function over an efficient set is a favourite topic for theoretical studies, the problem ($P^I$) of finding a maximal value of a linear function $dx$ over an integer efficient set is still open. The problem ($P^I$) is NP-hard and it is very unlikely that the maximal objective value of the integer problem ($P^I$) in many cases is greater than the maximal objective value of its corresponding continuous problem ($P$). In this paper we pay atention to the study of the problem ($P^I$) and some related properties of the problem ($P$). In particular, we establish conditions determining whether or not an optimal solution to the problem ($P$) is an optimal solution to the its corresponding linear program. For the problem ($P^I$) we find an upper bound for its optimal objective value and present an algorithm which gives a global optimal solution after a finite number of steps. We also study two particular classes of problems ($P^I$) : the bicriteria case and the case when $d$ is a nonnegative linear combination of the vectors-criteria defining the efficient set.
Key words: Multiple objective linear programming, integer efficient set, efficient cone, cutting plane.