# 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.

## Registration

Please register here to attend the MIP 2022 workshop. The registration fee is $30 before April 15, and$45 between April 15 and May 15.

## Program

### 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) 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. 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. 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. 4:00-5:00 Computational competition presentations & results 5:30-6:30 Poster session

### Thursday, May 26

 08:30-09:00: Breakfast 09:30-10:00 Juan Pablo Vielma – Modeling and Duality in Domain Specific Languages for Mathematical OptimizationAbstract: Domain specific languages (DSL) for mathematical optimization allow users to write problems in a natural algebraic format. However, what is considered natural can vary from user to user. For instance, JuMP’s interface makes a distinction between conic formulations and nonlinear programming formulations whose constraints are level-sets of nonlinear functions. Tradeoffs between such alternative modeling formats are further amplified when dual solutions are considered. In this talk we describe work related to these tradeoffs in JuMP and OR-Tools. In particular, we consider modeling using a wide range of non-symmetric cones (and their solution with Hypatia.jl) and defining precise dual contracts for two-sided constraints (and other non-conic convex constraints). 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. 11:30-12:00 Alfredo Torrico – Preserving Diversity when Partitioning: A Geometric ApproachAbstract: Diversity plays a crucial role in team formation, representation of minority groups and generally when allocating resources fairly. Given a community composed by individuals of different types, we study the problem of dividing this community such that the global diversity is preserved as much as possible in each subgroup. We consider the diversity metric introduced by Simpson in his influential work that, roughly speaking, corresponds to the inverse of the probability that two individuals are from the same type when taken at random, with replacement. We provide a novel perspective by reinterpreting this quantity in geometric terms. We characterize the instances in which the optimal partition exactly preserves the global diversity in each subgroup. When this is not possible, we provide an efficient polynomial-time algorithm that outputs an optimal partition for the problem with two types. Finally, we discuss further challenges and open questions for the problem that considers more than two types. This is joint work with Sebastian Perez-Salazar and Victor Verdugo. 12:00-2:00 Best poster award + Closing

## 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. We expect to open the block in mid to late March.

### 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 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.