Methods for finding global optimal solutions to linear programs with equilibrium constraints (Q1862683)

The authors study the mathematical program with equilibrium constraints \[ (P):\quad \min\bigl\{f (x,y):(x,y)\in D\bigr\} \] where \(y\) solves the parametric variational inequality problem \[ (V1(X)): \quad\text{find }y\in C(x): (x-y)^TF(x,y)\geq 0\text{ for all }v\in C(x). \] Here \(D\subseteq \mathbb{R}^{n+ m}\), \(C(x)\subseteq \mathbb{R}^m\) are polyhedral convex sets for every \(x\) and \(f\): \(\mathbb{R}^{n+m} \to\mathbb{R}\), \(F:\mathbb{R}^{n+m} \to\mathbb{R}^m\) are affine functions. Applying Kuhn-Tucker conditions the above problem is reformulated as a linear program with an additional complementarity constraint. The authors propose two branch-and-bound algorithms for solving globally the above problem. While the first algorithm uses a simplical subdivision accompanied with a decoupling technique for bounding, the second one uses a binary tree defined according to the sign of the dual variable appearing in the complementarity condition. It is claimed that the algorithm using a binary tree is more efficient than the first algorithm.