Groupe d’études et de recherche en analyse des décisions

G-2015-60

An RLT approach for solving the binary-constrained mixed linear complementarity problem

, et

It is well known that the mixed linear complementarity problem can be used to model the equilibrium in energy markets as well as a host of other engineering and economic problems. The binary-constrained mixed linear complementarity problem is a formulation of the mixed linear complementarity problem in which some variables are restricted to be binary. This paper presents a novel approach for solving the binary-constrained mixed linear complementarity problem. First we solve a series of linear programs that enables us to replace some of the complementarity constraints with linear equations. Then we solve an equivalent mixed integer linear program formulation of the original binary-constrained mixed linear complementarity problem (with a smaller number of complementarity constraints) to guarantee a solution to the problem. Our computational results on a wide range of test problems, including some engineering examples, demonstrate the usefulness and the effectiveness of this novel approach.

, 22 pages