An RLT approach for solving the binary-constrained mixed linear complementarity problem. (October 2019)

• Record Type: Journal Article
• Authors: Djeumou Fomeni, Franklin; Gabriel, Steven A.; Anjos, Miguel F.
• Is Part Of: Computers & operations research. Volume 110(2019)
• Page Start: 48
• Page End: 59
• Publication Date: 2019-10
• Subjects: Mixed linear complementarity problems -- Mixed integer linear programming -- Reformulation linearization technique -- Electricity market -- Linear programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.05.008
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We give a new way to solve binary-constrained mixed linear complementarity problems. These arise in energy, transportation, facility location, and land-use planning. The algorithm does not relax the binary nor the complementarity constraints. The algorithm is validated on some 1400 instances including engineering test cases. Abstract: It is well known that the mixed linear complementarity problem can be used to model equilibria 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 optimization problems that enables us to replace some of the complementarity constraints with linear equations. Then we solve an equivalent mixed integer linear programming 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.