An enhanced logical benders approach for linear programs with complementarity constraints

Francisco Jara-Moroni*, John E. Mitchell, Jong Shi Pang, Andreas Wächter

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

This work extends the logical benders approach for solving linear programs with complementarity constraints proposed by Hu et al. (SIAM J Optim 19(1):445–471, 2008) and Bai et al. (Comput Optim Appl 54(3):517–554, 2013). We develop a novel interpretation of the logical Benders method as a reversed branch-and-bound search, where the whole exploration procedure starts from the leaf nodes in an enumeration tree. This insight enables us to provide a new framework over which we can combine master problem and cut generation in a single process. It also allows us to diversify the search, leading computationally to stronger cuts. We also present an optimization-based sparsification process which makes the cut generation more efficient. Numerical results are presented to show the effectiveness of this enhanced method. Results are also extended to problems with more complementarity constraints, exceeding those that can be handled by the original method in the cited references.

Original languageEnglish (US)
Pages (from-to)687-714
Number of pages28
JournalJournal of Global Optimization
Volume77
Issue number4
DOIs
StatePublished - Aug 1 2020

Keywords

  • Branch-and-bound
  • Complementarity constraints
  • Cut generation
  • Logical benders

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An enhanced logical benders approach for linear programs with complementarity constraints'. Together they form a unique fingerprint.

Cite this