期刊
INFORMS JOURNAL ON COMPUTING
卷 34, 期 6, 页码 3117-3133出版社
INFORMS
DOI: 10.1287/ijoc.2022.1216
关键词
mixed-integer programming; linear complementarity problems; mixed-integer linear complementarity problems; branch and bound; penalty methods
资金
- Sapienza, University of Rome [RM120172A2970290]
- Deutsche Forschungsgemeinschaft (DFG) [SFB TRR 154]
- DFG within the Research Training Group 2126: Algorithmic Optimization
This paper presents a novel branch-and-bound method for solving mixed-integer linear complementarity problems (MILCPs). The method branches by adding penalty terms to the objective function, allowing for calculation of MILCP solutions or approximate solutions. The method is enhanced with MILCP-tailored valid inequalities, node selection strategies, branching rules, and warm-starting techniques.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据