Abstract: In this talk I will describe ongoing work on polynomial optimization problems (POPs), from a discrete optimization perspective, that is to say, using techniques motivated by mixed-integer programming. In particular I will primarily focus on methods for producing solutions, and on the feasibility of such solutions. The current "king of the hill" for computing solutions to POPs are filter methods relying on logarithmic barrier algorithms, implemented in codes such as IPOPT or KNITRO. Instead we will focus on techniques based on integer programming -- such techniques are not yet competitive with the solvers just mentioned, but may soon yield competitive algorithms.

If time permits, I will also describe joint work (with Chen Chen and Gonzalo Munoz) on techniques for obtaining lower bounds for POPs based on classical cutting-plane techniques, such as intersection cuts.

Abstract: Let F be a set defined by quadratic constraints. Understanding the structure of the lifted closed convex hull of C(F) is crucial to solve quadratically constrained quadratic programs related to F. In this talk, we discuss the relationship between C(F) and C(G), where G results by adding non-intersecting quadratic constraints to F. We prove that C(G) can be represented as the intersection of C(F) and some half spaces defined by the added constraints. Our result generalizes an existing result for bounded F. As a byproduct, we provide a complete description of the asymptotic cones of sets defined by a single quadratic equality.

Abstract: We study MINLO (mixed-integer non-linear optimization) formulations of the disjunction x ∈ {0} ∪ [l, u], where z is a binary indicator of x ∈ [l,u] (0 ≤ l < u), and y "captures" f(x), which is assumed to be convex and positive on its domain [l, u], but otherwise y=0 when x=0. This model is very useful in non-linear combinatorial optimization, where there is a fixed cost of operating an activity at level x in the operating range [l, u], and then there is a further (convex) variable cost f(x). In particular, we study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of f, obtained by choosing linearization points for f. Using 3-d volume (in (x,y,z)) as a measure of the tightness of a convex relaxation, we investigate relaxation quality as a function of f, l, u, and the linearization points chosen. We make a careful investigation for convex power functions f(x) := x^p, p > 1.

This is joint work with Daphne Skipper, Emily Speakman, and Luze Xu.

Abstract: We consider a general conic mixed-binary set where each homogeneous conic constraint involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, fⱼ, of common binary variables. Sets of this form naturally arise as substructures in a number of applications including mean-risk optimization, chance-constrained problems, portfolio optimization, lot-sizing and scheduling, fractional programming, variants of the best subset selection problem, and distributionally robust chance-constrained programs. When all of the functions fⱼs are submodular, we give a convex hull description of this set that relies on characterizing the epigraphs of fⱼs. Our result unifies and generalizes an existing result in two important directions. First, it considers multiple general convex cone constraints instead of a single second-order cone type constraint. Second, it takes arbitrary nonnegative functions instead of a specific submodular function obtained from the square root of an affine function. We close by demonstrating the applicability of our results in the context of a number of broad problem classes. This is joint work with Simge Kucukyavuz and Dabeen Lee.

Abstract: In this talk we describe linear and integer programming based methods for two problems in statistics and machine learning. In the first part, we focus on learning causal structures in the presence of latent variables, which can be modeled as the problem of optimizing over the set of acyclic directed mixed graphs (containing directed and bidirected edges) defined on a set of nodes. We give an integer programming formulation of this problem, and the first algorithm to solve this problem to optimality (via branch-and-cut). In the second part of the talk, we will describe a linear programming based approach to learning first-order logical rules for the knowledge graph link prediction problem.

This is joint work with Rui Chen, Tian Gao, and Joao Goncalves.

Abstract: The presence of floating-point roundoff errors compromises the results of virtually all fast mixed integer programming solvers available today. The last milestone achievement for the numerically exact solution of general mixed integer programs over the rational numbers dates back to the hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. In this talk, we describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal floating-point heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. This is joint work with Leon Eifler.

Abstract: "When will this run finish?" is undoubtedly a popular question among users of branch-and-bound based mixed integer programming solvers.

In this talk, we focus on online estimations of the final tree size during the search. We first review existing measures of the search progress such as the (in-)famous gap, and introduce a new measure called leaf-frequency. We then discuss and compare the suitability of the individual measures as predictors of the final tree size either by direct projection or by time series forecasting. Finally, we combine these measures as input of a simple Machine Learning model, which significantly outperforms the prediction accuracy of all individual measures.

This work manifests as a new display column in SCIP 7.0 that displays the approximate search progress percentage, which can be trained further to user instances of interest.

Abstract: In malleable scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Each job is required to be executed non-preemptively and in unison, i.e., it has to occupy the same time interval on all its allocated machines. In this talk, we discuss a generalization of malleable scheduling, in which a function f(S, j) determines the processing time of job j on machine subset S. Under different discrete concavity assumptions on 1/f(S,j), we show that the scheduling problem can be approximated by a considerably simpler assignment problem and derive LP-based approximation algorithms.

This is joint work with Dimitris Fotakis and Orestis Papadigenopoulos.

Abstract: We study a competitive facility location problem (CFLP), in which two firms sequentially select locations of new facilities, in order to maximize their market shares of customer demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. Through integer programming methods, we derive an equivalent, single-level MINLP reformulation. In addition, we exploit the problem structures and derive two classes of valid inequalities, one based on submodularity and the other based on concave overestimation. We apply these inequalities in a branch-and-cut algorithm to find a globally optimal solution to CFLP. Furthermore, we propose an approximation algorithm for solving CFLP that is computationally more effective. Notably, this algorithm admits a constant approximation guarantee. Extensive numerical studies demonstrate that the exact algorithm can significantly accelerate the solving of CFLP on problem instances that have not been solved to optimality by existing methods. The approximation algorithm can find near-optimal solutions even more quickly.

This is joint work with Mingyao Qi (Tsinghua U) and Ruiwei Jiang (U of Michigan).

Abstract: We discuss the complexity of the two main ingredients in integer optimization algorithms: cutting planes and branch-and-bound. We prove upper and lower bounds on the efficiency of these algorithms, when efficiency is measured in terms of complexity of the LPs that are solved. More precisely, we focus on the sparsity of the LPs and the number of LPs as measures of complexity. We also give general conditions under which combining branching and cutting into a branch-and-cut algorithm can do exponentially better than pure cutting planes or pure branch-and-bound. Time permitting, some connections to mathematical logic and proof complexity will be discussed.

Abstract: In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminals, and the goal is to partition the vertices into k parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k>=3 is APX-hard. Assuming the unique games conjecture, the approximability of this problem coincides with the integrality gap of an LP-relaxation, known as the CKR relaxation. The CKR relaxation embeds the graph into a (k-1)-dimensional simplex. For arbitrary k, the best-known upper bound on the integrality gap is 1.2965 while the previous best-known lower bound on the integrality gap was 1.2. In a recent work, we improved the lower bound to 1.20016 by constructing a 3-dimensional simplex instance. In this talk, I will present the main ideas underlying the construction and the analysis of this instance.

Based on joint work with Kristof Berczi, Tamas Kiraly, and Vivek Madan.

Abstract: The relaxation complexity rc(X) of a set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is an important tool to investigate the existence of compact linear descriptions of X. In this talk, I will address computational aspects of relaxation complexity such as finding computable upper bounds on rc(X) or the exact value of rc(X). For the latter, I will show generic algorithmic approaches and provide explicit formulas for rc(X) for specific classes of sets X.

This is joint work with Gennadiy Averkov and Matthias Schymura.

Abstract: A backdoor is a small set of variables that leads to a certificate branch-and-bound tree for a mixed-integer program: it suffices to branch on the backdoor variables to solve an instance to global optimality or conclude infeasibility. Experimental results by Dilkina et al. (2009) and Fischetti-Monaci (2011) have shown that many MILP instances from MIPLIB admit backdoors of sizes 10-20, which may lead to smaller branch-and-bound trees if identified efficiently. We revisit the problem of finding small backdoors to MILP problems from the perspective of reinforcement learning and heuristic search and propose a new algorithm with some practical advantages over existing approaches.

Abstract: We can compress a neural network while exactly preserving its underlying functionality with respect to a given input domain if some of its neurons are stable. However, current approaches to determine the stability of neurons require solving or finding a good approximation to multiple discrete optimization problems. In this talk, we present an algorithm based on solving a single optimization problem to identify all stable neurons. Our approach is on median 21 times faster than the state-of-art method, which allows us to explore exact compression on deeper (5 x 100) and wider (2 x 800) networks within minutes. For classifiers trained under an amount of L1 regularization that does not worsen accuracy, we can remove up to 40% of the connections.

This talk is based on joint work with Abhinav Kumar (Michigan State University) and Srikumar Ramalingam (Google Research).

Abstract: MIP plays a crucial role to support several decisions within the scope of my organization, Amazon Fulfillment Optimization. In this talk I will present a couple of problems spanning real-time and tactical planning models.

I will start with a problem that we solve millions of times per day: how to fulfill each order striving to maximize customer experience and ensure fast delivery while keeping our costs low. I will then discuss our approach to improve Amazon Logistics efficiency by exploiting delivery densification opportunities and solving routing and demand assignment models together.

Abstract: The diameter of polyhedra has attracted attention for years due to its connection with the complexity of the simplex algorithm. In particular, giving sharp bounds on the diameter in terms of specified parameters is a central topic in mathematical optimization and computational geometry. In this talk, we will survey some recent results on the diameter of polyhedra with emphasis on those for lattice polytopes. A lattice polytope means a polytope whose vertices are drawn from {0,1,...,k}^d (namely, here, k and d are the parameters). It is known since the 1990s that the diameter of lattice polytopes behaves as Θ(k^2/3) in dimension 2. We give an explicit expression for the diameter of lattice zonotopes in fixed dimension for infinitely many k, which implies that the diameter of lattice polytopes behaves as Ω(k^d/(d+1)) in dimension d. This talk is based on joint work with Antoine Deza and Lionel Pournin.

Abstract: Linear programs and the simplex method are at the core of mathematical optimization, both in theory and in practice.

Today plenty of fascinating open questions remain about the behavior of the simplex method.

In this lecture we introduce natural geometric-topological structure one can associate to the set of all possible monotone paths of a linear program. Using this structure we are interested to find the extreme behavior of LPs regarding the following questions: a) How long can the monotone paths on a linear program be? b) How many different monotone paths can there be on a linear program?

We report on some highlights from three recent papers, the first joint work with Moise Blanchard (MIT) and Quentin Louveaux (U. Liege), the second with Sean Kafer (U. Waterloo) and Laura Sanità (TU Eindhoven) and the third with Christos Athanasiadis (U. Athens) and Zhenyang Zhang (U. California, Davis).

Papers are available at and https://arxiv.org/abs/2002.00999, https://arxiv.org/abs/1909.12863 and https://arxiv.org/abs/2001.09575

Abstract: The complexity of Philip Wolfe's method for the minimum Euclidean-norm point problem over a convex polytope has remained unknown since he proposed the method in 1974. The method is important because it is used as a subroutine for one of the most practical algorithms for submodular function minimization. We present the first example that Wolfe's method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in strongly-polynomial time to the minimum norm point problem over a simplex.

Abstract: Breaking symmetries is a popular way of speeding up the branch-and-bound method for symmetric integer programs. We study symmetry-breaking polyhedra, more precisely, fundamental domains.

In this talk, I will introduce the necessary mathematical concepts to understand the implications of symmetries in polyhedral objects.
In particular, we will derive several general geometric properties of fundamental domains and how these geometric considerations can affect the power for breaking symmetries. I will also mention some recent results for constructing more general fundamental domains ("On the Geometry of Symmetry Breaking Inequalities" IPCO 2021). Finally, I will focus on several open questions regarding fundamental domains, their geometric properties, and how they could help us better understand the capabilities and limitations of symmetry-breaking systems.

This is joint with Matías Villagra (U Columbia) and Leonard von Niederhäusern (UOH & CMM).

Abstract: The V-polyhedral framework is a recent approach for generating disjunctive cutting planes for mixed-integer linear programs. Unlike the lift-and-project method, which requires the construction of a computationally demanding higher-dimensional formulation, V-polyhedral disjunctive cuts can be computed via a linear program in the same dimension as the original problem. However, without the values of the extra variables used for lift-and-project cuts, one cannot directly apply a posteriori cut strengthening techniques such as monoidal strengthening. We show how the values of those extra variables can be computed efficiently, and thereby lay the groundwork for strengthening arbitrary valid disjunctive cuts. We present computational experiments with this idea on V-polyhedral disjunctive cuts.