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.