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.

• Video
• Slides

Abstract

Lemke and Howson proposed in 1964 a pivot-based 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.

• Video

Abstract

The multi-depot vehicle scheduling problem (MDVSP) is a principal planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. We propose an exact branch-and-cut (B&C) scheme to solve our CCP model. We present several cut-generation procedures that exploit the underlying problem structure and analyze the relationship between the obtained cut families. Additionally, we design a Lagrangian-based heuristic to handle large-scale instances reflective of real-world 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 cost-effective schedules with reliable service guarantees compared to alternatives commonly used by practitioners, as well as the computational benefits of our methodologies.

• Video

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.

• Video
• Slides

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 second-order 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, Gomory-Chvatal closure, and Caratheodory rank to integer points in arbitrary cones.

• Video

Abstract

The field of mixed-integer 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.

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 `big-M' method is well-established and often used (and abused) for formulating multiple-choice constraints. It is well-known that such formulations can be rather weak and also suffer from numerical instability, even when the big-M 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 convex-hull of the mixed-integer solutions, and we considered broad and useful situations where this is indeed the case. In such situations, the `big-M' inequalities can be derived by optimally lifting facet-describing inequalities of the disjunctive pieces. Specifically, we study the natural extended-variable formulation for the disjunction of n+1 polytopes in dimension d. We demonstrate that the convex hull D in the natural extended-variable space in dimension d+n is given by full optimal big-M lifting (i) when d <= 2 (and that it is not generally true for d >= 3), and also (ii) when the polytopes are all axis-aligned hyper-rectangles. We note that both of these cases are very natural for applications and within spatial branch-and-bound, the main algorithmic paradigm for mixed-integer 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 big-M liftings of the facet-describing inequalities for the individual polytopes describe facets of D.

• Video

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 first-order 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 first-order 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 first-order oracles for the purpose of optimization. We will close the talk with some open questions.

• Video

Abstract

We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero 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 primal-dual 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 non-zeros 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 black-box and can be applied to any log-barrier path following method.

• Video

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.

• Video

Abstract

The splitting-off 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 splitting-off operation in hypergraphs. Main results are that there exists a local connectivity preserving complete splitting-off in hypergraphs and a strongly polynomial-time algorithm to compute it in weighted hypergraphs. If time permits, I will illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications: (1) constructive characterization of k-hyperedge-connected hypergraphs and (2) alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau (Journal of Combinatorial Theory, 2008)). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams' strong orientation theorem and uses tools developed for hypergraphs. Based on joint work with Kristof Berczi, Tamas Kiraly, and Shubhang Kulkarni.

• Video

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 value-maximizing 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 non-identical 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 non-identical distributions, and can robustly handle outliers/augmentations.

Abstract

We develop a set-cover based integer-programming approach to an optimal safety-landing-site location arising in the design of urban air-transportation networks. We link our minimum-weight set-cover problems to efficiently-solvable cases of minimum-weight 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 reduced-cost fixing, and which we found to be very effective in reducing the size of our integer-programming instances.

• Video

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 Marie-Charlotte Brandenburg, Jesús A. De Loera, Jared Miller, Matteo Tacchi, and Mauricio Velasco.

• Video
• Slides

• Slides

Abstract

The complex cut polytope is the convex hull of Hermitian rank one matrices, where the elements of rank-one 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.

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 non-degenerate 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 so-called True Steepest-Edge pivot rule which is guaranteed to perform a strongly polynomial number of non-degenerate 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 Steepest-Edge 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 non-degenerate 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à

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 positive-definiteness 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.

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 data-driven 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 data-driven algorithm design. We then apply this approach to the problem of making good decisions in the branch-and-cut framework for mixed-integer optimization (e.g., which cut to add?). In other words, the neural network will take as input a mixed-integer optimization instance and output a decision that will result in a small branch-and-cut 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 branch-and-cut tree sizes, compared to previous data-driven approaches.

Abstract

The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unit-demand 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 NP-hard. Joint work with Eric Balkanski and Christopher En

Abstract

We consider sensitivity analysis for Mixed Binary Quadratic Programs (MBQPs) with respect to changing right-hand-sides (rhs). We show that even if the optimal solution of a given MBQP is known, it is NP-hard 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 completely-positive (CPP) reformulation of MBQPs. Its dual is an instance of co-positive 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.

Abstract

With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three.

• Video

Abstract

We introduce new relaxation hierarchies for concavo-convex 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 reformulation-linearization 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.

• Video

Abstract

We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price 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 problem-specific 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 branch-and-bound tree, allowing us to solve many more large instances than classical methods. Moreover, we show how range branching can be successfully generalized to order-based objective functions, such as the Gini deviation.

• Video