Semidefinite relaxation for linear programs with equilibrium constraints

Semidefinite relaxation for linear programs with equilibrium constraints

0.00 Avg rating0 Votes
Article ID: iaor201524314
Volume: 20
Issue: 2
Start Page Number: 201
End Page Number: 212
Publication Date: Mar 2013
Journal: International Transactions in Operational Research
Authors: , ,
Keywords: programming: branch and bound
Abstract:

In this paper, we present a semidefinite programming (SDP) relaxation for linear programs with equilibrium constraints (LPECs) to be used in a branch‐and‐bound (B&B) algorithm. The procedure utilizes the global optimal solution of LPECs and was motivated by the B&B algorithm proposed by Bard and Moore for linear/quadratic bilevel programs, where complementarities are recursively enforced. We propose the use of the SDP relaxation to generate bounds at the nodes of the B&B tree. Computational results compare the quality of the bounds given by the SDP relaxation with the ones given by conventional linear programming relaxations.

Reviews

Required fields are marked *. Your email address will not be published.