Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications

Abstract: We consider a general conic mixed-binary set where each homogeneous conic constraint involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, $f_j$, of common binary variables. Sets of this form naturally arise as substructures in a number of applications including mean-risk optimization, chance-constrained problems, portfolio optimization, lot-sizing and scheduling, fractional programming, variants of the best subset selection problem, and distributionally robust chance-constrained programs. When all of the functions $f_j$s are submodular, we give a convex hull description of this set that relies on characterizing the epigraphs of $f_j$s. Our result unifies and generalizes an existing result in two important directions. First, it considers multiple general convex cone constraints instead of a single second-order cone type constraint. Second, it takes arbitrary nonnegative functions instead of a specific submodular function obtained from the square root of an affine function. We close by demonstrating the applicability of our results in the context of a number of broad problem classes. This is joint work with Simge Kucukyavuz and Dabeen Lee.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.