Organizing Committee
 Jesús De Loera
University of California, Davis  Antoine Deza
McMaster University  Marcia Fampa
Federal University of Rio de Janeiro  Volker Kaibel
OttovonGuericke Universität Magdeburg  Jon Lee
University of Michigan  Laura Sanità
Bocconi University
Abstract
This reunion workshop will bring together participants from ICERM's Spring 2023 Discrete Optimization Semester Program and researchers with related interests. Participants will discuss recent advances and catalyze new collaborations related to combinatorial optimization and mixedinteger linear and nonlinear optimization.
The Spring 2023 Semester Program at ICERM explored unsolved fundamental questions in discrete optimization and connected areas of mathematics, computer science, and data analytics.
Confirmed Speakers & Participants
Talks will be presented virtually or inperson as indicated in the schedule below.
 Speaker
 Poster Presenter
 Attendee
 Virtual Attendee

Kurt Anstreicher
University of Iowa

Catherine Babecki
Caltech

Amitabh Basu
Johns Hopkins University

Merve Bodur
University of Edinburgh

Karthekeyan Chandrasekaran
University of Illinois UrbanaChampaign

Gerard Cornuejols
Carnegie Mellon University

Ryan CoryWright
Imperial College London

Claudia D'Ambrosio
LIX  Ecole Polytechnique

Jesús De Loera
University of California, Davis

Santanu Dey
Georgia Institute of Technology.

Alex Dunbar
Emory University

Jillian Eddy
University of California, Davis

Yuri Faenza
Columbia University

Marcia Fampa
Federal University of Rio de Janeiro

Rohan Ghuge
University of Michigan

Swati Gupta
MIT Sloan School of Management

Chengyue He
Columbia University

Sean Kafer
Georgia Tech

Volker Kaibel
OttovonGuericke Universität Magdeburg

Aida Khajavirad
Lehigh University

Sammy Khalife
Johns Hopkins University

Aditi Laddha
Yale University

Jon Lee
University of Michigan

Yongchun Li
University of Tennessee, Knoxville

Siyue Liu
Carnegie Mellon University

Andrea Lodi
Cornell Tech

Brittney Marsters
University of California, Davis

Chiara Meroni
ETHITS

Frédéric Meunier
École nationale des ponts et chaussées

Gonzalo Muñoz
Universidad de Chile

Bento Natura
Columbia University

Gabriel Oliveira da Ponte
University of Michigan

Dimitri Papadimitriou
Universite Libre de Bruxelles

Yushan Qu
University of Michigan

Nick Sahinidis
Georgia Institute of Technology

Laura Sanità
Bocconi University

Mohit Singh
Georgia Tech

Rose Sossou Edou
École nationale des ponts et chaussées

Renata Sotirov
Tilburg University

Emily Speakman
University of Colorado  Denver

Jeff SylvestreDecary
University of Connecticut

Mohit Tawarmalani
Purdue University

Antonio Torres
UCDavis

Lucy Verberk
Eindhoven University of Technology

Luze Xu
University of California, Davis

Yuan Zhou
University of Kentucky
Workshop Schedule
Monday, August 26, 2024

8:30  8:50 am EDTCheck In11th Floor Collaborative Space

8:50  9:00 am EDTWelcome11th Floor Lecture Hall
 Misha Kilmer, Tufts University

9:00  9:45 am EDTSpectral Optimization via Matroid Intersection11th Floor Lecture Hall
 Speaker
 Mohit Singh, Georgia Tech
 Session Chair
 Jon Lee, University of Michigan
Abstract
Representing data via vectors and matrices and optimizing spectral objectives such as determinants, and traces of naturally associated matrices is a standard paradigm that is utilized in multiple areas including machine learning, statistics, convex geometry, location problems, allocation problems, and network design problems. In this talk, we will look at many of these applications with a focus on the determinant objective. We will then give algorithms for these problems that build on classical matroid intersection algorithms.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTThe Lemke—Howson algorithm for oriented matroids, and applications11th Floor Lecture Hall
 Speaker
 Frédéric Meunier, École nationale des ponts et chaussées
 Session Chair
 Jon Lee, University of Michigan
Abstract
Lemke and Howson proposed in 1964 a pivotbased algorithm for solving bimatrix games. The year after, Lemke proposed a closely related algorithm for solving a large class of linear complementarity problems. Although Todd extended the Lemke algorithm to oriented matroids in 1984, the extension of the Lemke—Howson algorithm to oriented matroids has not yet been addressed in the literature. Actually, achieving such an extension requires solving a few issues. One of them is to propose a relevant definition of Nash equilibria for oriented matroids. Another one is more challenging, namely finding the counterpart of the following preliminary operation of the classical Lemke—Howson algorithm: the translation of the payoff matrices so as to make them positive. In this work, we show how to overcome these challenges and extend the Lemke—Howson algorithm to oriented matroids. A few applications are discussed, such as a strengthening of a theorem by McLennan and Tourky, a combinatorial interpretation of the orientation of the pivot step in the classical version, and the localization of tropical bimatrix games in the class PPAD. Joint work with Xavier Allamigeon and Stéphane Gaubert.

11:30 am  12:15 pm EDTIncorporating Service Reliability in Multidepot Vehicle Scheduling: A ChanceConstrained Approach11th Floor Lecture Hall
 Speaker
 Merve Bodur, University of Edinburgh
 Session Chair
 Jon Lee, University of Michigan
Abstract
The multidepot vehicle scheduling problem (MDVSP) is a principal planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chanceconstrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. We propose an exact branchandcut (B&C) scheme to solve our CCP model. We present several cutgeneration procedures that exploit the underlying problem structure and analyze the relationship between the obtained cut families. Additionally, we design a Lagrangianbased heuristic to handle largescale instances reflective of realworld transit operations. Our approach partitions the set of trips, each subset leading to a subproblem that can be efficiently solved with our B&C algorithm, and then employs a procedure to combine the subproblem solutions to create a vehicle schedule that satisfies all the planning constraints of the MDVSP. Our empirical evaluation demonstrates the superiority of our stochastic variant in achieving costeffective schedules with reliable service guarantees compared to alternatives commonly used by practitioners, as well as the computational benefits of our methodologies.

12:30  2:30 pm EDTLunch/Free Time

2:30  3:15 pm EDTSpectrahedral Geometry of Graph Sparsifiers11th Floor Lecture Hall
 Speaker
 Catherine Babecki, Caltech
 Session Chair
 Kurt Anstreicher, University of Iowa
Abstract
We propose an approach to graph sparsification based on the idea of preserving the smallest k eigenvalues and eigenvectors of the Graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph G that have the same first k eigenvalues (and eigenvectors) as G is the intersection of a polyhedron with a cone of positive semidefinite matrices. We discuss the geometry of these sets and deduce the natural scale of k. Various families of graphs illustrate our construction.

3:30  4:00 pm EDTCoffee Break11th Floor Collaborative Space

4:00  4:45 pm EDTInteger Points in Arbitrary Convex Cones: The Case of the PSD and SOC Cones11th Floor Lecture Hall
 Speaker
 Luze Xu, University of California, Davis
 Session Chair
 Kurt Anstreicher, University of Iowa
Abstract
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the secondorder cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, GomoryChvatal closure, and Caratheodory rank to integer points in arbitrary cones.

5:00  6:30 pm EDTWelcome11th Floor Collaborative Space
Tuesday, August 27, 2024

9:00  9:45 am EDTConvexification and optimization of problems involving the Euclidean norm11th Floor Lecture Hall
 Speaker
 Nick Sahinidis, Georgia Institute of Technology
 Session Chair
 Marcia Fampa, Federal University of Rio de Janeiro
Abstract
The field of mixedinteger nonlinear optimization has advanced significantly over the past three decades. Yet, even small instances of many nonconvex optimization problems involving the Euclidean norm are beyond the capabilities of modern codes. Although these models arise from applications as diverse as molecular energy minimization, object packing, and facility location, they often share specific features which lead to computational intractability. In this presentation, we identify these features, introduce new algorithms to address them, and present numerical results showing the impact of our techniques. This is joint work with Anatoliy Kuznetsov.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTOn disjunction convex hulls by lifting11th Floor Lecture Hall
 Speaker
 Yushan Qu, University of Michigan
 Session Chair
 Marcia Fampa, Federal University of Rio de Janeiro
Abstract
In the study of disjunctive programming, a critical aspect is the exploration of feasible regions formed by the union of multiple convex sets. The `bigM' method is wellestablished and often used (and abused) for formulating multiplechoice constraints. It is wellknown that such formulations can be rather weak and also suffer from numerical instability, even when the bigM coefficients are chosen optimally. So, MILP/MINLP solvers often struggle with these formulations, while they are ubiquitous in MILP/MINLP applications. On the other hand, sometimes these formulations are best possible; that is, the inequalities can give a complete description of the convexhull of the mixedinteger solutions, and we considered broad and useful situations where this is indeed the case. In such situations, the `bigM' inequalities can be derived by optimally lifting facetdescribing inequalities of the disjunctive pieces. Specifically, we study the natural extendedvariable formulation for the disjunction of n+1 polytopes in dimension d. We demonstrate that the convex hull D in the natural extendedvariable space in dimension d+n is given by full optimal bigM lifting (i) when d <= 2 (and that it is not generally true for d >= 3), and also (ii) when the polytopes are all axisaligned hyperrectangles. We note that both of these cases are very natural for applications and within spatial branchandbound, the main algorithmic paradigm for mixedinteger nonlinear optimization. Additionally, we give further results on the polyhedral structure of D, giving very general conditions under which it is full dimensional and when the full optimal bigM liftings of the facetdescribing inequalities for the individual polytopes describe facets of D.

11:30 am  12:15 pm EDTInformation Complexity of MixedInteger Convex Optimization11th Floor Lecture Hall
 Speaker
 Amitabh Basu, Johns Hopkins University
 Session Chair
 Marcia Fampa, Federal University of Rio de Janeiro
Abstract
We consider the problem of minimizing a convex function under convex constraints, where some or all of the decision variables are constrained to be integer, with access to firstorder oracles for the objective function and separation oracles for the constraints. We focus on the information complexity of the problem, i.e., the minimum number of oracle calls to solve the problem to a desired accuracy. We will present nearly tight upper and lower bounds for the problem, extending classical results from continuous convex optimization. We also initiate the study of, and obtain the first set of results on, information complexity under oracles that only reveal partial firstorder information, e.g., where one can only make a binary query on the function value or (sub)gradient at a given point. Our bounds in these new settings show that these oracles are provably less informative than full firstorder oracles for the purpose of optimization. We will close the talk with some open questions.

12:30  2:30 pm EDTNetworking LunchWorking Lunch  11th Floor Collaborative Space

2:30  3:15 pm EDTA strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column11th Floor Lecture Hall
 Speaker
 Bento Natura, Columbia University
 Session Chair
 Amitabh Basu, Johns Hopkins University
Abstract
We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two nonzero entries per row, or at most two nonzero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP '83) and Végh (MOR '17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent primaldual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS '22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL '04), the same bound applies to any linear program with at most two nonzeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is blackbox and can be applied to any logbarrier path following method.

3:30  4:00 pm EDTCoffee Break11th Floor Collaborative Space

4:00  4:45 pm EDTThe packing property11th Floor Lecture Hall
 Speaker
 Gerard Cornuejols, Carnegie Mellon University
 Session Chair
 Amitabh Basu, Johns Hopkins University
Abstract
Analogous to perfection in antiblocking theory is the notion of "the packing property" in blocking theory. A key insight on perfect graphs is the famous replication lemma proved by Laci Lovasz in 1972. In 1993, Michele Conforti and I proposed an analogous replication conjecture when the packing property holds. This conjecture is still open. This talk covers some recent developments related to the replication conjecture. These results are joint with Ahmad Abdi.
Wednesday, August 28, 2024

9:00  9:45 am EDTSplittingoff in Hypergraphs11th Floor Lecture Hall
 Speaker
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
 Session Chair
 Laura Sanità, Bocconi University
Abstract
The splittingoff operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of that vertex while preserving their degrees. Lovász (1974) and Mader (1978) showed the existence of this operation while preserving global and local connectivities respectively in graphs under mild conditions. In this talk, I will introduce a splittingoff operation in hypergraphs. Main results are that there exists a local connectivity preserving complete splittingoff in hypergraphs and a strongly polynomialtime algorithm to compute it in weighted hypergraphs. If time permits, I will illustrate the usefulness of our splittingoff operation in hypergraphs by showing two applications: (1) constructive characterization of khyperedgeconnected hypergraphs and (2) alternate proof of an approximate minmax relation for max Steiner rootedconnected orientation of graphs and hypergraphs (due to Király and Lau (Journal of Combinatorial Theory, 2008)). Our proof of the approximate minmax relation for graphs circumvents the NashWilliams' strong orientation theorem and uses tools developed for hypergraphs. Based on joint work with Kristof Berczi, Tamas Kiraly, and Shubhang Kulkarni.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTExponential Pricing for Online Resource Allocation11th Floor Lecture Hall
 Speaker
 Rohan Ghuge, University of Michigan
 Session Chair
 Laura Sanità, Bocconi University
Abstract
Online resource allocation problem is a central problem in many areas of Computer Science, Operations Research, Economics, and Networks. In this problem, requests arrive sequentially, and each request can be satisfied in multiple ways, each consuming a certain amount of resources while generating different values. The objective is to maximize the overall value without exceeding the budget for any resource. Of particular interest in this problem is the design of pricing algorithms that present each incoming request with prices for the resources, enabling the request to make a valuemaximizing decision based on current resource prices. The goal is to obtain a nearly optimal solution (with respect to the hindsight optimum). Prior works have established that such pricing algorithms exist for i.i.d. requests, provided that each resource has a large budget. Our goal is to obtain similar guarantees for nonidentical request distributions or when the requests have outliers that do not satisfy the stochastic assumptions. Our main contribution is in resolving both these questions via a simple exponential pricing algorithm: it gives a nearly optimal solution for online resource allocation with large budgets, requires only polynomially many (in the allowable error) samples from the nonidentical distributions, and can robustly handle outliers/augmentations.

11:30 am  12:15 pm EDTOn a geometric graphcovering problem related to optimal safetylandingsite location11th Floor Lecture Hall
 Speaker
 Claudia D'Ambrosio, LIX  Ecole Polytechnique
 Session Chair
 Laura Sanità, Bocconi University
Abstract
We develop a setcover based integerprogramming approach to an optimal safetylandingsite location arising in the design of urban airtransportation networks. We link our minimumweight setcover problems to efficientlysolvable cases of minimumweight set covering that have been studied. We were able to solve large random instances to optimality using our modeling approach. We carried out strong fixing, a technique that generalizes reducedcost fixing, and which we found to be very effective in reducing the size of our integerprogramming instances.

12:30  2:30 pm EDTLunch/Free Time

2:30  3:15 pm EDTSlices of convex bodies11th Floor Lecture Hall
 Speaker
 Chiara Meroni, ETHITS
 Session Chair
 Laura Sanità, Bocconi University
Abstract
During the Spring 2023 ICERM semester, we initiated a parametric study of hyperplane sections of polytopes. Our framework enables the resolution of various optimization problems, which we will discuss in detail. However, when extending the study to nonlinear convex bodies, the combinatorial approach proves inadequate. We explore two alternative methods to address analogous optimization problems for slices of more general bodies, such as semialgebraic convex bodies and polygauge convex bodies. This talk is based on joint works with MarieCharlotte Brandenburg, Jesús A. De Loera, Jared Miller, Matteo Tacchi, and Mauricio Velasco.

3:30  5:00 pm EDT
Thursday, August 29, 2024

9:00  9:45 am EDTCuts and liftings for the complex cut polytope11th Floor Lecture Hall
 Speaker
 Renata Sotirov, Tilburg University
 Session Chair
 Volker Kaibel, OttovonGuericke Universität Magdeburg
Abstract
The complex cut polytope is the convex hull of Hermitian rank one matrices, where the elements of rankone matrices are the unit roots. We first introduce the complex elliptope that is considered to be the first semidefinite lifting of the complex cut polytope. Then, we show how to derive valid cuts in the complex plane that separate the complex elliptope from the complex cut polytope. Further, we consider a second semidefinite lifting of the complex cut polytope. Finally, we present numerical results that verify quality of our complex semidefinite approximations of the complex cut polytope.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTSolving 0/1 LPs in Polynomial Time with Simplex11th Floor Lecture Hall
 Speaker
 Sean Kafer, Georgia Tech
 Session Chair
 Volker Kaibel, OttovonGuericke Universität Magdeburg
Abstract
We show that given any 0/1 LP (i.e., one whose feasible region is a 0/1 polytope) and any initial basis, there exists a pivot rule for the Simplex method that performs a strongly polynomial number of pivots in total (i.e., counting both degenerate and nondegenerate pivots) where each pivot is computable in polynomial time. Our rule is an improvement on previous work by Black, De Loera, K., and Sanità (MOR'24) which proposed the socalled True SteepestEdge pivot rule which is guaranteed to perform a strongly polynomial number of nondegenerate pivots on 0/1 LPs. It was shown that this rule performs a finite number of pivots in total, but no bound was given on the number of degenerate pivots it performs. Inspired by recent work of Kukharenko and Sanità (IPCO'24), we give a modification to the True SteepestEdge rule which causes it to escape degeneracy in a number of degenerate pivots which is linear in the number of variables while still performing the same sequence of nondegenerate pivots, thus giving a strongly polynomial number of pivots in total. For arbitrary 0/1 LPs, we are only able to show that our pivots can be computed in weakly polynomial time. However, we show that our pivots can be computed in strongly polynomial time as long as the given description of our 0/1 LP has no implied equalities (i.e., no inequality constraints which are satisfied with equality at all feasible points). To do this, we make a novel use of a classical result of Frank and Tardos (Combinatorica'87) to reduce the encoding length of our constraint matrix. It was shown by Tardos (Operations Research'86) that an LP whose constraint matrix has small encoding length can be solved in strongly polynomial time, but this algorithm does not imply that this can be done by Simplex. Joint work with Alex Black and Laura Sanità

11:30 am  12:15 pm EDTSolid Angles of Polyhedral Cones and the Strength of Cutting Planes11th Floor Lecture Hall
 Speaker
 Yuan Zhou, University of Kentucky
 Session Chair
 Volker Kaibel, OttovonGuericke Universität Magdeburg
Abstract
The solid angle of a polyhedral cone, indicating the proportion of space occupied by the cone, holds significant relevance in integer programming. In 1969, Gomory introduced the cyclic group relaxation of IP, where facets of the cyclic group polyhedra play a crucial role in generating cutting planes. However, predicting the importance or relative size of each facet has been challenging due to inconsistencies in results obtained from the shooting experiment, which estimates the solid angle subtended by each facet at the origin. To address this, we propose computing the solid angle measures directly, whose closed formulas were well established in two and three dimensions. For higher dimensions, Aomoto and Ribando demonstrated computing the solid angle of a simplicial cone using a multivariable hypergeometric series, subject to a positivedefiniteness criterion. We provide decomposition methods to meet this criterion and implement the algorithm in SageMath. Furthermore, we examine the asymptotic error of the series. We present the results of our solid angle measure approximation algorithm and compare them with those obtained from the shooting experiments and the Cousins–Vempala volume approximation algorithm, showcasing advantages in speed and consistency. This is a joint work with Allison Fitisone.

12:25  12:30 pm EDTGroup Photo (Immediately After Talk)11th Floor Lecture Hall

12:30  1:30 pm EDTNetworking LunchWorking Lunch  11th Floor Collaborative Space

1:30  2:15 pm EDTSample complexity of algorithm selection and its applications to branchandcut11th Floor Lecture Hall
 Speaker
 Sammy Khalife, Johns Hopkins University
 Session Chair
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
Abstract
Can we learn efficiently good cutting planes to solve integer programs faster? What do we mean by efficient learning, and what is a good cutting plane? In this talk, I will delve into these questions, building upon recent work in datadriven algorithm design. This paradigm uses statistical and machine learning techniques to select from a class of algorithms for a computational problem an algorithm that has the best expected performance with respect to some (unknown) distribution on the instances of the problem. In this context, instead of selecting a single algorithm that has the best performance, we allow the possibility of selecting an algorithm based on the instance to be solved. In particular, given a representative sample of instances, we learn a neural network that maps an instance of the problem to the most appropriate algorithm for that instance. By formalizing this idea, I will present rigorous sample complexity bounds for this learning problem, in the spirit of recent work in datadriven algorithm design. We then apply this approach to the problem of making good decisions in the branchandcut framework for mixedinteger optimization (e.g., which cut to add?). In other words, the neural network will take as input a mixedinteger optimization instance and output a decision that will result in a small branchandcut tree for that instance. Our computational results provide evidence that our particular way of using neural networks for cut selection can make a significant impact in reducing branchandcut tree sizes, compared to previous datadriven approaches.

2:30  3:15 pm EDTAn Algorithm for the Assignment Game, Beyond Additive Valuations11th Floor Lecture Hall
 Speaker
 Yuri Faenza, Columbia University
 Session Chair
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
Abstract
The assignment game, introduced by Shapley and Shubik (1971), is a classic model for twosided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unitdemand valuations for the items being sold. Two important and mostly independent lines of work have studied more general settings with imperfectly transferable utility and gross substitutes valuations. Multiple efficient algorithms have been proposed for computing a competitive equilibrium, the standard solution concept in assignment games, in these two settings. Our main result is an efficient algorithm for computing competitive equilibria in a setting with both imperfectly transferable utility and gross substitutes valuations. Our algorithm combines augmenting path techniques from maximum matching and algorithms for matroid intersection. We also show that, in a mild generalization of our model, computing a competitive equilibrium is NPhard. Joint work with Eric Balkanski and Christopher En

3:30  4:00 pm EDTCoffee Break11th Floor Collaborative Space

4:00  4:45 pm EDTSensitivity Analysis for Mixed Binary Quadratic Programs11th Floor Lecture Hall
 Speaker
 Santanu Dey, Georgia Institute of Technology.
 Session Chair
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
Abstract
We consider sensitivity analysis for Mixed Binary Quadratic Programs (MBQPs) with respect to changing righthandsides (rhs). We show that even if the optimal solution of a given MBQP is known, it is NPhard to approximate the change in objective function value with respect to changes in rhs. Next, we study algorithmic approaches to obtaining dual bounds for MBQP with changing rhs. We leverage Burer’s completelypositive (CPP) reformulation of MBQPs. Its dual is an instance of copositive programming (COP), and can be used to obtain sensitivity bounds. We prove that strong duality between the CPP and COP problems holds if the feasible region is bounded or if the objective function is convex, while the duality gap can be strictly positive if neither condition is met. We also show that the COP dual has multiple optimal solutions, and the choice of the dual solution affects the quality of the bounds with rhs changes. We finally provide a method for finding good nearly optimal dual solutions, and we present preliminary computational results on sensitivity analysis for MBQPs.
Friday, August 30, 2024

9:00  9:45 am EDTThe pseudoBoolean polytope and polynomialsize extended formulations for binary polynomial optimization11th Floor Lecture Hall
 Speaker
 Aida Khajavirad, Lehigh University
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudoBoolean polytope. By representing the pseudoBoolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomialsize extended formulation. Our new framework unifies and extends all prior results on the existence of polynomialsize extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTNew Finite Relaxation Hierarchies for Disjoint Bilinear Programs11th Floor Lecture Hall
 Speaker
 Mohit Tawarmalani, Purdue University
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
We introduce new relaxation hierarchies for concavoconvex programs, including disjoint bilinear and concave minimization. These hierarchies utilize rational functions that are barycentric coordinates of polytopes. The hierarchies have a geometric and an algebraic underpinning and converge to convex hull of the problem at a finite level. Relaxation techniques for this class of problems include disjunctive programming and reformulationlinearization technique. Our hierarchy provides the first unifying framework relating these hierarchies to one another while strengthening the relaxations. The new hierarchy exploits the linear precision of barycentric coordinates to improve the relaxation at each level and leverages recent advances in convexification of fractional optimization problems.

11:30 am  12:15 pm EDTEfficient Branching Rules for Optimizing Range and OrderBased Objective Functions11th Floor Lecture Hall
 Speaker
 Andrea Lodi, Cornell Tech
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
We consider range minimization problems featuring exponentially many variables, as frequently arising in fairnessoriented or biobjective optimization. While branch and price is successful at solving costoriented problems with many variables, the performance of classical branchandprice algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top of problemspecific branching schemes. We show several desirable properties of range branching and show its effectiveness on a series of instances of the fair capacitated vehicle routing problem and fair generalized assignment problem. Range branching significantly improves multiple classical branching schemes in terms of computing time, optimality gap, and size of the branchandbound tree, allowing us to solve many more large instances than classical methods. Moreover, we show how range branching can be successfully generalized to orderbased objective functions, such as the Gini deviation.

12:30  2:30 pm EDTLunch/Free Time
All event times are listed in ICERM local time in Providence, RI (Eastern Daylight Time / UTC4).
All event times are listed in .
ICERM local time in Providence, RI is Eastern Daylight Time (UTC4). Would you like to switch back to ICERM time or choose a different custom timezone?
Request Reimbursement
This section is for general purposes only and does not indicate that all attendees receive funding. Please refer to your personalized invitation to review your offer.
 ORCID iD
 As this program is funded by the National Science Foundation (NSF), ICERM is required to collect your ORCID iD if you are receiving funding to attend this program. Be sure to add your ORCID iD to your Cube profile as soon as possible to avoid delaying your reimbursement.
 Acceptable Costs

 1 roundtrip between your home institute and ICERM
 Flights on U.S. or E.U. airlines – economy class to either Providence airport (PVD) or Boston airport (BOS)
 Ground Transportation to and from airports and ICERM.
 Unacceptable Costs

 Flights on nonU.S. or nonE.U. airlines
 Flights on U.K. airlines
 Seats in economy plus, business class, or first class
 Change ticket fees of any kind
 Multiuse bus passes
 Meals or incidentals
 Advance Approval Required

 Personal car travel to ICERM from outside New England
 Multipledestination plane ticket; does not include layovers to reach ICERM
 Arriving or departing from ICERM more than a day before or day after the program
 Multiple trips to ICERM
 Rental car to/from ICERM
 Flights on a Swiss, Japanese, or Australian airlines
 Arriving or departing from airport other than PVD/BOS or home institution's local airport
 2 oneway plane tickets to create a roundtrip (often purchased from Expedia, Orbitz, etc.)
 Travel Maximum Contributions

 New England: $350
 Other contiguous US: $850
 Asia & Oceania: $2,000
 All other locations: $1,500
 Note these rates were updated in Spring 2023 and superseded any prior invitation rates. Any invitations without travel support will still not receive travel support.
 Reimbursement Requests

Request Reimbursement with Cube
Refer to the back of your ID badge for more information. Checklists are available at the front desk and in the Reimbursement section of Cube.
 Reimbursement Tips

 Scanned original receipts are required for all expenses
 Airfare receipt must show full itinerary and payment
 ICERM does not offer per diem or meal reimbursement
 Allowable mileage is reimbursed at prevailing IRS Business Rate and trip documented via pdf of Google Maps result
 Keep all documentation until you receive your reimbursement!
 Reimbursement Timing

6  8 weeks after all documentation is sent to ICERM. All reimbursement requests are reviewed by numerous central offices at Brown who may request additional documentation.
 Reimbursement Deadline

Submissions must be received within 30 days of ICERM departure to avoid applicable taxes. Submissions after thirty days will incur applicable taxes. No submissions are accepted more than six months after the program end.