Methods for finding global optimal solutions to linear programs with equilibrium constraints
type: Item
instance of: scholarly article
title: Methods for finding global optimal solutions to linear programs with equilibrium constraints
zbMATH Open document ID: 1027.90057
author: Nguyen V. Quy
author: Le Dung Muu
published in: Vietnam Journal of Mathematics
publication date: 2003-05-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C47
zbMATH DE Number: 1885669
zbMATH Keywords: global optimal solution
zbMATH Keywords: Kuhn-Tucker conditions
zbMATH Keywords: linear program
zbMATH Keywords: complementarity constraint
zbMATH Keywords: branch-and-bound algorithms
reviewed by: R. N. Kaul
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1885669