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: | Maculan Nelson, Fampa Marcia H C, Melo Wendel A X |
Keywords: | programming: branch and bound |
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.