Decomposition branch and bound algorithm for optimization problems over efficient sets
Nguyen Van Thoai
Journal of Industrial & Management Optimization 2008, 4(4): 647-660 doi: 10.3934/jimo.2008.4.647
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: decomposition. branch and bound multi-criteria optimization reverse convex constraint Nonconvex programming optimization over efficient set
Global optimization algorithm for solving bilevel programming problems with quadratic lower levels
Paul B. Hermanns Nguyen Van Thoai
Journal of Industrial & Management Optimization 2010, 6(1): 177-196 doi: 10.3934/jimo.2010.6.177
In this article, we propose a method for finding the global optimum of a class of nonlinear bilevel programming problems. The main idea of this method is to construct iteratively a sequence of points either ending at an optimal solution of the equivalent problem with a complementarity constraint, or converging to an optimal solution. The construction of such a sequence is performed by using a branch-and-bound scheme, together with some relaxation techniques, which are successfully applied in global optimization. Some illustrative examples and results on computational experiments are reported.
keywords: Bilevel programming nonconvex programming branch and bound.

Year of publication

Related Authors

Related Keywords

[Back to Top]