An enhanced logical benders approach for linear programs with complementarity constraints

Francisco Jara-Moroni (), John E. Mitchell (), Jong-Shi Pang () and Andreas Wächter ()
Additional contact information
Francisco Jara-Moroni: Universidad de Santiago de Chile
John E. Mitchell: Rensselaer Polytechnic Institute
Jong-Shi Pang: University of Southern California
Andreas Wächter: Northwestern University

Journal of Global Optimization, 2020, vol. 77, issue 4, No 1, 687-714

Abstract: 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.

Keywords: Complementarity constraints; Logical benders; Branch-and-bound; Cut generation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00905-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:77:y:2020:i:4:d:10.1007_s10898-020-00905-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00905-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().