TITLE: Convexification Techniques for Linear Complementarity Constraints

SPEAKER:  Jean-Philippe Richard

ABSTRACT:

In this talk, we discuss strong convex relaxations of mathematical programs with complementarity constraints (MPCCs). MPCCs have numerous practical applications in business, engineering, and economics because complementarity conditions arise in the mathematical modeling of games and equilibria. and because nonlinear programs in which constraint functions are differentiable can be reformulated in a higher dimensional space using optimality conditions.

We first describe a convexification technique for linear programs with linear complementarity constraints that generalizes the reformulation-linearization technique of Sherali and Adams and has similar convergence properties. We then consider certain complementarity problems appearing in KKT systems. For such problems, we show that all nontrivial facet-defining inequalities can be obtained through a simple procedure that aggregates constraints and use McCormick relaxations of bilinear terms. Finally, we discuss the problem of generating strong cutting planes, in the space of the original variables, from the optimal simplex tableaux of the LP relaxation of the problem. We discuss the geometry of the corresponding sets and compare the strength of the cuts thus obtained with respect to RLT, disjunctive, and other approaches in the literature.

This talk is based on joint work with Trang Nguyen (UF) and Mohit Tawarmalani (Purdue).

Bio: Jean-Philippe Richard is an associate professor in the Department of Industrial and Systems Engineering at the University of Florida . After receving a bachelor in Applied Mathematics Engineering at Universite Catholique de Louvain in Louvain-La-Neuve, Belgium, he came to study at the Georgia Institute of Technology where he received a Phd in Algorithms, Combinatorics and Optimization. His current research interests include the use of polyhedral and convex analysis techniques for the derivation of strong convex relaxations of mixed integer linear and nonlinear programs. He is also currently working with CSX on large-scale optimization problems arising in railroads and with SAS-OR on computational issues associated with the solution of integer programs.