Optimization Online


Solving Binary-Constrained Mixed Complementarity Problems Using Continuous Reformulations

Steven A. Gabriel(sgabriel***at***umd.edu)
Marina Leal(palazon***at***uni-trier.de)
Martin Schmidt(martin.schmidt***at***uni-trier.de)

Abstract: Mixed complementarity problems are of great importance in practice since they appear in various fields of applications like energy markets, optimal stopping, or traffic equilibrium problems. However, they are also very challenging due to their inherent, nonconvex structure. In addition, recent applications require the incorporation of integrality constraints. Since complementarity problems often model some kind of equilibrium, these recent applications ask for equilibrium points that additionally satisfy certain integer conditions. Obviously, this makes the problem even harder to solve. The solution approach used most frequently in the literature is to recast the complementarity conditions as disjunctive constraints using additional binary variables and big-M constraints. However, both latter aspects create issues regarding the tractability and correctness of the reformulation. In this paper, we follow the opposite route and restate the integrality conditions as complementarity constraints, leading to purely continuous reformulations that can be tackled by local solvers. We study these reformulations theoretically and provide a numerical study that shows that continuous reformulations are useful in practice both in terms of solution times and solution quality.

Keywords: Binary-constrained mixed complementarity problems, Mixed-integer optimization, Continuous reformulations, Spatial price equilibrium problems

Category 1: Complementarity and Variational Inequalities

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Applications -- OR and Management Sciences (Transportation )


Download: [PDF]

Entry Submitted: 02/16/2020
Entry Accepted: 02/16/2020
Entry Last Modified: 02/16/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society