Upcoming Events

On Valid Inequalities for Mixed Integer Conic Programs

October 30, 2013 11:00AM to 12:00PM
Presenter 
Fatma Kilinc-Karzan, Carnegie Mellon University
Location 
Building 221, Room A216
Type 
Seminar
Series 
Abstract:
Many operational questions arising in science and engineering, especially from the optimization under uncertainty, can be approximately addressed as systems of quadratic inequalities in continuous and integer variables. The resulting problems belong to the class of optimization problems referred as Mixed Integer Conic Programs (MICPs), which involve a general regular cone K such as the nonnegative orthant, the Lorentz cone (convex quadratic inequalities) or the positive semidefinite cone. In this talk we will describe the broad background of such problems, together with two new results that we have obtained.

First, we will introduce the class of K-minimal valid linear inequalities for MICPs. Under mild assumptions, we will show that these inequalities together with the trivial cone-implied inequalities are sufficient to describe the convex hull. We study the characterization of K-minimal inequalities by identifying necessary, and sufficient conditions for an inequality to be K-minimal; which leads to efficient ways of showing a given linear inequality is K-minimal. Second, we will introduce a disjunctive technique for deriving conic valid inequalities for mixed integer sets defined by convex quadratic functions. This new technique recovers a number of results from the recent literature on deriving split and disjunctive inequalities for the mixed integer sets involving a Lorentz cone.