METHODS FOR FINDING GLOBAL OPTIMAL SOLUTIONS TO LINEAR PROGRAMS WITH EQUILIBRIUM CONSTRAINTS
LE DUNG MUU, NGUYEN VAN QUY
A mathematical program with equilibrium constraints is an optimization problem with two sets of variables $x$ and $y$, in which some or all of its constraints are defined by a parametric variational inequality or complementarity system with $y$ as its primary variables and $x$ the parameter vector. This problem even in the linear case is a difficult global optimization problem because of its nested structure. We use a dual formulation of this problem to develop two decomposition branch-and-bound algorithms for finding a global optimal solution of a linear mathematical program with equilibrium constraints. The first algorithm uses a simplicial subdivision whereas the second one uses a binary tree defined by using the sign (zero or positive) of the dual variables. The searching trees in both lgorithms are created in the dual space. Preliminary computational experiences and results show that on a PC computer the lgorithm using binary tree can solve linear problems with equilibrium constraints up to twenty-five dual variables; the number of the primal variables may be larger.