Semidefinite relaxation for linear programs with equilibrium constraints |
| |
Authors: | Marcia HC Fampa Wendel AX Melo Nelson Maculan |
| |
Affiliation: | 1. Instituto de Matemática, Universidade Federal do Rio de Janeiro, , Brazil;2. COPPE, Universidade Federal do Rio de Janeiro, , Brazil |
| |
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. |
| |
Keywords: | LPEC bilevel program semidefinite relaxation |
|
|