# Mixed Integer Programming Workshop 2022

feat. DANniversary

May 23-26, 2022

DIMACS, Rutgers University

The Mixed Integer Programming (MIP) Workshop is a single-track workshop highlighting the latest trends in integer programming and discrete optimization, with speakers chosen by invitation.

The MIP 2022 edition of the workshop will be the nineteenth in the MIP series, and it will be opened by DANniversary, a special conference in celebration of Daniel Bienstock's 60th birthday.

## Program (including abstracts and slides)

### Tuesday, May 24

 08:30-09:00: Breakfast 09:15-09:30: MIP opening remarks 09:30-10:30 Samuel Fiorini – Integer programs with bounded subdeterminants and two nonzeros per rowAbstract: We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching. This is joint work with Gwenaël Joret (ULB, Brussels), Stefan Weltge (TU Munich) and Lena Yuditsky (ULB, Brussels) (slides) 10:30-11:00 Break 11:00-11:30 Ignacio Grossman – Extending Generalized Disjunctive Programming to Model Hierarchical SystemsAbstract: We present an extension to Generalized Disjunctive Programming (GDP) to model hierarchical systems via nested disjunctions. We denote these more general GDP models as Nested GDPs (NGDPs). NGDPs are compared to their Equivalent GDP formulations. Reformulations to algebraic optimization models of NGDPs and the Equivalent GDPs are formalized. The two approaches are compared in terms of resulting model tightness and size (number of discrete and continuous variables, and constraints). Computational results are presented with examples from the areas of process flowsheet synthesis and optimization of electric power expansion planning. The results show the value in using NGDPs to systematically model and solve real-world problems. (slides) 11:30-12:00 Manuel Aprile – Binary extended formulations and sequential convexificationAbstract: A binarization of a variable x is a linear formulation though additional binary variables, whose integrality implies the integrality of x. A binary extended formulation of a polyhedron P is obtained by adding to the original description of P binarizations of some of its variables. In the context of mixed-integer programming, imposing integrality on 0/1 variables rather than on general integer variables has interesting convergence properties and has been studied both from the theoretical and from the practical point of view. We propose a notion of natural binarizations and binary extended formulations, encompassing all the ones studied in the literature. We give a simple characterization of the vertices of such formulations, which allows us to study their behavior with respect to sequential convexification. In particular, given a binary extended formulation and one of its variables x, we study a parameter that measures the progress made towards ensuring the integrality of x via application of sequential convexification. We formulate this parameter, which we call rank, as the solution of a set covering problem and express it exactly for the classical binarizations from the literature. (slides) 12:00-2:00 Lunch 2:00-2:30 JP Richard – A Reciprocity Between Tree Ensemble Optimization and Multilinear OptimizationAbstract: We establish a polynomial equivalence between tree ensemble optimization and optimization of multilinear functions over the Cartesian product of simplices. We use this insight to derive new formulations for tree ensemble optimization problems and to obtain new convex hull results for multilinear polytopes. A computational experiment on multi-commodity transportation problems with costs modeled using tree ensembles shows the practical advantage of our formulation relative to existing formulations of tree ensembles and other piecewise-linear modeling techniques. Motivated by the inability of tree ensembles to model multilinear functions of continuous variables, we then propose a generalization of decision-trees and provide empirical evidence of a better out-of-sample fit for a large collection of randomly perturbed nonlinear functions. This is joint work with Jongeun Kim (University of Minnesota) and Mohit Tawarmalani (Purdue). 2:30-3:00 Oktay Gunluk – Warehouse Problem with Time-varying Bounds, Fixed Costs and Complementarity ConstraintsAbstract: We study a generalization of the warehouse problem with time dependent bounds on purchase, sale and storage quantities as well as fixed costs and complementarity constraints on purchases and sales. This variant is particularly relevant to applications to energy markets. For the general case we present extended LP formulations and pseudo-polynomial time algorithms. For some common special cases we present first polynomial time algorithms. Our approach can handle certain extensions including the stochastic version of the problem. 3:00-3:30 Break 3:30-4:00 Felipe Serrano – Monoidal StrengtheningAbstract: In this talk I'll try to explain monoidal strengthening", a technique introduced by Balas and Jeroslow in the 80's to strengthen intersection cuts by exploiting the integrality of non-basic variables. I'll discuss some limitations of the technique and then explain how one of these limitations forces us to introduce a condition for the application of monoidal strengthening to disjunctive cuts. Finally, I'll mention how monoidal strengthening can be used to strengthen some intersection cuts for quadratic mixed-integer programming. (slides) 4:00-5:00 Computational competition presentations & results 5:30-6:30 Poster session

### Thursday, May 26

 09:30-10:00: Breakfast 10:00-10:30 Yiling Zhang – Integer Programming Approaches for Chance-Constrained Building Load Control with Wasserstein Ambiguity and Risk-Adjustable VariantsAbstract: Aggregation of heating, ventilation, and air conditioning (HVAC) loads can provide reserves to absorb volatile renewable energy, especially solar photo-voltaic (PV) generation. In this work, we decide HVAC control schedules under uncertain PV generation, using a distributionally robust chance-constrained (DRCC) building load control model under Wasserstein ambiguity sets. We derive strengthened mixed integer linear programming (MILP) reformulations for DRCC problems with right-hand side uncertainty. To achieve tradeoff between the operational risk and costs, we propose an adjustable chance-constrained variant. MILP and conic reformulations are derived. Using real-world data, we conduct computational studies to demonstrate the efficiency of the solution approaches and the effectiveness of the solutions. 10:30-11:00 Break 11:00-11:30 Sam Burer – A Strengthened SDP Relaxation for an Extended Trust Region SubproblemAbstract: We study an extended trust region subproblem minimizing a nonconvex function over the hollow ball $r \le \|x\| \le R$ intersected with a full-dimensional second order cone (SOC) constraint of the form $\|x - c\| \le b^T x - a$. In particular, we present a class of valid cuts that improve existing semidefinite programming (SDP) relaxations and are $\epsilon$-separable in polynomial time. We connect our cuts to the literature on the optimal power flow (OPF) problem by demonstrating that previously derived cuts capturing a convex hull important for OPF are actually just special cases of our cuts. (slides) 11:30-1:30 Best poster award + Closing

### Presented posters

 Eleonora Vercesi On the generation of Metric TSP instances with a large integrality gap by branch-and-cut Anna Deza Safe Screening for Logistic Regression with Regularization Yatharth Dubey On Polytopes with Linear Rank with respect to Generalizations of Split Cuts Sumin Kang Distributionally Risk-Receptive and Risk-Averse Network Interdiction Problems with General Ambiguity Set Ramin Fakhimi Formulations of the max k-cut problem on classical and quantum computers Luca Ferrarini The Total Matching Problem: A Polyhedral Perspective Bainian Hao Inefficiency of pure Nash equilibria in series-parallel network congestion games Chengyue He Scarf's algorithm for matching polytopes Federico D'Onofrio Maximum Margin Optimal Classification Trees Hassan Mortagy Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes Kartik Kulkarni Tractability of Optimizing over Multi-Constrained Knapsack Sets using Lot-Sizing with Multiple Modules Yongchun Li D-optimal Data Fusion: Exact and Approximation Algorithms Kayhan Behdin Gaussian Graphical Models: A Scalable Framework Based on Combinatorial Optimization Alex Black Monotone Diameters of Lattice Polytopes Nan Jiang DFO: A Framework for Data-driven Decision-making with Outliers Antonia Chmiela Monoidal Strengthening for Intersection Cuts Using Maximal Quadratic-Free Sets Qimeng Yu On constrained mixed-integer DR-submodular minimization Aleksandr Touzov An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone Defeng Liu Learning to Search in Local Branching Jannik Irmai A Polyhedral Study of Lifted Multicuts Henri Lefebvre Adjustable Robust Optimization with discrete uncertainty Raul Garcia A Combinatorial Disjunctive Constraint Approach to Optimal Path Planning Nathan Justin Optimal Robust Classification Trees Xin Yu The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks Dekun Zhou An SDP relaxation for the Sparse Integer Least Square Problem Yu Xie Mixed integer bilevel linear optimization with bounded rationality Rachael Alfant Evaluating Mixed-Integer Programming Models over Multiple Right-hand Sides Tu Nguyen Neural Network Verification as Piecewise Linear Optimization: A Composition of Staircase Function Formulation Ritesh Ojha Dynamic Discretization Discovery Algorithm for Unrelated Parallel Machine Scheduling Problems

## Impressions

MIP 2022 participants
Dan Bienstock with organizers
Dan Bienstock with some participants
Computational Competition winners Bjørnar Luteberget and Giorgio Sartor (left), Computational Competition runner up Domenico Salvagnin, and Gonzalo Munoz (Competition Chair)
Jon Lee (Poster Competition jury Chair) with Best Poster awardee Alex Black
Jon Lee with Best Poster Honorable Mention awardee Dekun Zhou
Jon Lee with Best Poster Honorable Mention awardees Jai Moondra and Hassan Mortagy
Jon Lee with Best Poster Honorable Mention awardee Qimeng Yu
Yuri Faenza (MIP 2022 PC Chair) with Most Popular Poster (as voted by the workshop participants) awardee Anna Deza
Margaridinhas team, recipients of the 'Outstanding student submission' honorable mention of the MIP computational competition, and PC member Margarida Carvalho (left)

## Local information

### Conference venue

The workshop will be held on the College Avenue Campus of Rutgers University. The activities will take place in the Rutgers Academic Building located at 15 Seminary Place, New Brunswick, NJ. Presentations will be in room 4225, which is located in the East Wing of the building. The main important locations are indicated in this map.

### Accomodation

A block of rooms has been arranged with the Hyatt Regency in New Brunswick (see this map).

### Dining options

New Brunswick has a wide variety of dining options to fit all budgets. Many are within an easy walk of the conference venue and the Hyatt hotel. We have compiled some information on lunch options, quick lunch options (see this map), and options for dinner. Recall that we are having a conference dinner on Monday at The Frog & The Peach.

Additional material can be found at the DIMACS page.

## COVID-19 policy

In order to attend the MIP workshop, every participant must provide a proof of either full COVID vaccination or a negative COVID PCR test taken within 72 hours of arrival at the workshop. For the safety of everyone in attendance, DIMACS requests that event participants wear masks in the lecture room and other crowded indoor spaces.

## Credits

Logo by ©Julia Silbermann (fonts: Cornerstone by Zac Freeland, Oraqle Script by Union Hands). Website hosted at GitHub Pages, layout based on skeleton using Raleway font