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

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. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: M. De Santis acknowledges support within the project RM120172A2970290, which has received funding from Sapienza, University of Rome. M. Schmidt thanks the Deutsche Forschungsgemeinschaft (DFG) for its support within project A05 and B08 in the "SFB TRR 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks." L. Winkel is supported by the DFG within the Research Training Group 2126: "Algorithmic Optimization." Supplemental Material: The online supplementary material is available at https://doi.org/10.1287/ijoc.2022.1216. [ABSTRACT FROM AUTHOR]

Copyright of INFORMS Journal on Computing is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Volltext ist im Gastzugang nicht verfügbar. Melden Sie sich für Vollzugriff an.