Decomposition branch and bound algorithm for optimization problems over efficient sets

Pages: 647 - 660, Volume 4, Issue 4, November 2008

doi:10.3934/jimo.2008.4.647       Abstract        Full Text (196.8K)       Related Articles

Nguyen Van Thoai - Department of Mathematics, University of Trier, 54286 Trier, Germany (email)

Abstract: The problem of optimizing some given function over the efficient set is one of the most interesting and important concepts in multicriteria decision making. As the efficient set is in general nonconvex, even for the case of linear multicriteria programming problems, optimizing over the efficient set belongs to a typical problem class of multiextremal optimization problems, which can have local optima different from global optima.
    In this article, we consider the case where the multicriteria programming problem is linear. Characterizing the set of efficient solutions by some constraint of 'reverse convex' type in the space of criteria, we formulate the problem of minimizing a function $f$ over the efficient set as a global optimization problem with a special structure. For the resulting problem, a decomposition branch and bound based algorithm is then proposed, in which the branching procedure is performed in the criteria space. Convergence properties of the algorithm are discussed, and preliminary computational results are reported.

Keywords:  Nonconvex programming, multi-criteria optimization, optimization over efficient set, reverse convex constraint, branch and bound, decomposition.
Mathematics Subject Classification:  Primary: 90C26, 90C29.

Received: April 2007;      Revised: June 2008;      Published: November 2008.