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.
A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems / De Santis, M; de Vries, S; Schmidt, M; Winkel, L. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 34:(2022), pp. 3117-3133. [10.1287/ijoc.2022.1216]
A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems
De Santis, M;
2022
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.File | Dimensione | Formato | |
---|---|---|---|
DeSantis_preprint_A-Penalty_2022.pdf
accesso aperto
Tipologia:
Preprint (Submitted version)
Licenza:
Open Access
Dimensione
873.63 kB
Formato
Adobe PDF
|
873.63 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.