|
Vietnam Journal of Mathematics 35:4(2007)
523-539
|
On Branch-and-Bound Algorithms for Global
Optimal Solutions to Mathematical Programs with Affine Equilibrium
Constraints
|
Le Dung Muu and
Nguyen Van Quy
|
Abstract. Mathematical programming problems
with affine equilibrium constraints, shortly AMPEC, have many applications
in different fields of engineering and economics. AMPEC contains several
classes of optimization problems such as bilevel convex quadratic
programming, optimization over the efficient set as special cases. AMPEC is
known to be very difficult to solve globally due to its nested structure.
We propose a relaxation algorithm for globally solving AMPEC by using a
branch-and-bound strategy. The proposed algorithm uses a binary tree
enumeration search for bounding and branching. We also discuss bounding
operations by linear programming relaxation and the convex envelope.
Numerical experiences and results for the proposed algorithm are discussed
and reported.
|
|
1991 Mathematics Subject Classification: 90C29.
|
Keywords: Optimization with equilibrium
constraints, brach-and-bound, relaxation, bilevel convex quadratic program,
optimization over the efficient set, enumeration binary tree.
|
|
Established
by Vietnam Academy of Science and Technology & Vietnam Mathematical
Society
Published
by Springer since January 2013
|
|