An SOS1-Based Approach for Solving MPECs with a Natural Gas Market Application

This paper presents a new method for solving mathematical programs with equilibrium constraints. The approach uses a transformation of the original problem via Schur's decomposition coupled with two separate formulations for modeling related absolute value functions. The first formulation, based on SOS1 variables, when solved to optimality will provide a global solution to the MPEC. The second, penalty-based formulation is used to heuristically obtain local solutions to large-scale MPECs. The advantage of these methods over disjunctive constraints for solving MPECs is that computational time is much lower, which is corroborated by numerical examples. Finally, an application of the method to an MPEC representing the United States natural gas market is given.