A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems

Marianna De Santis (), Sven de Vries (), Martin Schmidt () and Lukas Winkel ()
Additional contact information
Marianna De Santis: Dipartimento di Ingegneria informatica automatica e gestionale Antonio Ruberti, Sapienza Università di Roma, 00185 Roma, Italy
Sven de Vries: Department of Mathematics, Trier University, 54296 Trier, Germany
Martin Schmidt: Department of Mathematics, Trier University, 54296 Trier, Germany
Lukas Winkel: Department of Mathematics, Trier University, 54296 Trier, Germany

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 3117-3133

Abstract: Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations and also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well-studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, almost no tailored algorithms are known besides reformulations of the problem that allow us to apply general purpose mixed integer linear programming solvers. In this paper, we present, theoretically analyze, enhance, and test a novel branch-and-bound method for MILCPs. The main property of this method is that we do not “branch” on constraints as usual but by adding suitably chosen penalty terms to the objective function. By doing so, we can either provably compute an MILCP solution if one exists or compute an approximate solution that minimizes an infeasibility measure combining integrality and complementarity conditions. We enhance the method by MILCP-tailored valid inequalities, node selection strategies, branching rules, and warm-starting techniques. The resulting algorithm is shown to clearly outperform two benchmark approaches from the literature.

Keywords: mixed-integer programming; linear complementarity problems; mixed-integer linear complementarity problems; branch and bound; penalty methods (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1216 (application/pdf)

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:inm:orijoc:v:34:y:2022:i:6:p:3117-3133

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().