Obtaining Tighter Relaxations of Mathematical Programs with
Complementarity Constraints
Download the paper,
in pdf.
Authors:
John E. Mitchell
mitchj at rpi dot edu
Department of
Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
Jong-Shi
Pang
jspang at illinois dot edu
Industrial and Enterprise Systems
Engineering,
University of Illinois at Urbana-Champaign,
117 Transportation Bldg., 104 S. Mathews Ave., Urbana, IL 61801.
Bin Yu
yub at rpi dot edu
Department of
Decision Sciences and Engineering Systems,
Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
Chapter 1 in
Springer
Proceedings in Mathematics and Statistics, Volume 21,
August 2012.
Abstract:
The class of mathematical programs with complementarity constraints (MPCCs)
constitutes a powerful modeling paradigm.
In an effort to find a global optimum, it is often useful to examine
the relaxation obtained by omitting the complementarity constraints.
We discuss various methods to tighten the relaxation by exploiting
complementarity, with the aim of constructing better
approximations to the convex hull of the set of feasible solutions
to the MPCC, and hence better lower bounds on the optimal
value of the MPCC.
Better lower bounds can be useful in branching schemes to find
a globally optimal solution.
Different types of linear constraints are constructed,
including cuts based on bounds on the variables
and various types of disjunctive cuts.
Novel convex quadratic constraints are introduced,
with a derivation that is particularly useful when the number
of design variables is not too large.
A lifting process is specialized to MPCCs.
Semidefinite programming constraints are also discussed.
All these constraints are typically applicable to any convex program with
complementarity constraints.
Computational results for linear programs with complementarity constraints
(LPCCs)
are included, comparing the benefit
of the various constraints on the value of the relaxation,
and showing that the constraints can dramatically speed up
the solution of the LPCC.
Keywords:
MPECs;
linear programs with linear complementarity constraints;
LPCCs;
convex relaxation;
semidefinite programming
Submitted.
Download the paper,
in pdf.
Return to my list of papers.