Session: Advances in Mixed-Integer Optimization
Chair: Alberto Del Pia
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Convexification Techniques For Logical Implication Constraints Involving Cardinality Requirements
Speaker: Jean-Philippe Richard
Abstract: Cardinality requirements and implications between groups of distinct variables are pervasive in applications and are often modeled through the use of integer programming techniques. We describe a general constructive scheme that allows for the convex hull of sets involving logical implication constraints relating the cardinality of groups of variables to be derived in a higher dimensional space. We also discuss aspects of projecting the formulations. We provide simple illustrative applications of the scheme, which subsume existing results in the literature.
Talk 2: Transfer Theorems in Mixed-Integer Convex Optimization
Speaker: Phillip Kerger
Abstract: In this talk, we will present two lines of work that explore the transferability of results between different settings in optimization. First, we will show how performance guarantees from noise-free convex optimization can be adapted to the stochastic setting, even when mixed-integer variables are present. This is achieved through a black-box transfer approach that applies broadly to first-order methods. Second, we will discuss how complexity results from continuous convex optimization can be extended to the mixed-integer setting, which leads to new lower bounds under various oracles, such as those with partial first-order information. Such black-box approaches are especially appealing to have results in easier-to-analyze cases immediately transfer to more complex ones. Finally, some remaining open questions will be discussed.
Talk 3: Extended formulations for some class of Delta-modular IPs
Speaker: Luze Xu
Abstract: Conforti et al. give a compact extended formulation for a class of bimodular-constrained integer programs, namely those that model the stable set polytope of a graph with no disjoint odd cycles. We extend their techniques to design compact extended formulations for the integer hull of translated polyhedral cones whose constraint matrix is strictly $\Delta$-modular and has rows that represent a cographic matroid. Our work generalizes the important special case from Conforti et al. concerning 4-connected graphs with odd cycle transversal number at least 4. We also discuss the necessity of our assumptions. This is joint work with Joseph Paat and Zach Walsh.
