Institute for Computational and Experimental Research in Mathematics (ICERM)

Abstract

Diminishing Returns (DR)-submodular functions encompass a broad class of functions that are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisingly, turns out to be polyhedral. We propose a polynomial-time exact separation algorithm for our proposed valid inequalities, with which we first establish the polynomial-time solvability of this class of mixed-integer nonlinear optimization problems. This is joint work with Kim Yu.

• Video
• Slides

Abstract

Semidefinite programming (SDP) problems typically utilize the constraint that X-xx' is positive semidefinite to obtain a convex relaxation of the condition X=xx', where x is an n-vector. We consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx'. This branching technique is related to previous work of Saxeena, Bonami and Lee who used such an eigenvector to derive a disjunctive cut. We obtain excellent computational results applying the new branching technique to difficult instances of the two-trust-region subproblem.

• Video
• Slides

Abstract

The maximum diversity, or dispersion, problem (MDP), is to select from a given set a subset of elements of given size (budget), so that the sum of pairwise distances, or utilities, between the selected elements is maximized. We introduce here a method, called the Breakpoints (BP) algorithm, based on a technique proposed in Hochbaum (2009), to generate the concave piecewise linear envelope of the solutions to the relaxation of the problem for all values of the budget. The breakpoints in this envelope are provably optimal for the respective budgets and are attained using a parametric cut procedure that is very efficient. The problem is then solved, for any given value of the budget, by applying a greedy-like method to add or subtract nodes from adjacent breakpoints. This method works well if for the given budget there are breakpoints that are ``close". However, for many data sets and budgets this is not the case, and the breakpoints are sparse. We introduce a perturbation technique applied to the utility values in cases where there is paucity of breakpoints, and show that this results in denser collections of breakpoints. Furthermore, each optimal perturbed solution is quite close to an optimal non-perturbed solution. We compare the performance of our breakpoints algorithm to leading methods for these problems: The metaheuristic OBMA, that was shown recently to perform better than GRASP, Neighborhood search and Tabu Search, and Gurobi--an integer programming software. It is demonstrated that our method dominates the performance of these methods in terms of computation speed and in comparable or better solution quality.

Abstract

We consider the problem of maximizing a function over integer points in a compact set. Inner- and outer-approximations of the integer feasible set are obtained using families of monomial orders over the integer lattice. The convex hull is characterized when the monomial orders satisfy some properties. When the objective function is submodular or subadditive, we provide a theoretical guarantee on the quality of the inner-approximations in terms of their gap to the optimal value. An algorithm is proposed to generate feasible solutions, and it is competitive with a commercial solver in numerical experiments on benchmark test instances for integer LPs.

Abstract

In this talk we will detail our recent experience in solving the ACOPF problem, a notorious MINLP. We will do this from two perspectives. First, we will detail our experience in the recent, and on-going GO competition for solving modern, large-scale versions of ACOPF which include scenario constraints and integer variables. Second, we will outline challenges to state-of-the-art MINLP solvers based on spatial branch-and-bound that arise in ACOPF instances. Finally we will discuss some fundamental issues related to numerical precision.

• Video Available Soon

Abstract

In 1971, Balas introduced intersection cuts as a method for generating cutting planes in integer optimization. These cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied from theoretical and computational standpoints. In this talk, we focus on the case when S is defined by a general quadratic inequality and show how to construct basic maximal quadratic-free sets. Additionally, we explore how to generalize the basic procedure to construct a plethora of new maximal quadratic-free sets for homogeneous quadratics. Joint work with Joseph Paat and Felipe Serrano.

• Video
• Slides

Abstract

The fact that "challenging problems motivate methodological advances", as obvious as it may seem, is nonetheless very true. I was drawn long ago to Unit Commitment problems because of a specific methodology, but studying it led us to interesting results for entirely different ones. This talk will summarise on (the current status of) a long journey of discovery that ebbed and flowed between different notions of structure, starting from the "macro" one of spatial decomposition and its algorithmic implications, descending to the "micro" one of the Perspective Reformulation of tiny fragments of the problem, putting both back together to full-problem size with the definition of strong but large formulations (and the nontrivial trade-offs they entail), and finally skyrocketing to large- and huge-scale problems (stochastic UC, stochastic reservoirs optimization, long-term energy system design) where UC (and its sub-structures) is but one of the multiple nested forms of structure. The talk will necessarily have to focus on a few of the results that hopefully have broader usefulness than just UC, among which a recent one on the Convex Hull of Star-Shaped MINLPs, but it will also try to give a broad-brush of the larger picture, with some time devoted to discussing the nontrivial implications of actually implementing solution methods for huge-scale problems with multiple nested form of heterogeneous structure and the (surely partial and tentative) attempts at tackling these issues within the SMS++ modelling system.

• Video
• Slides

Abstract

The single-level (classical) knapsack problem consists of picking a subset of n items maximizing profit, subject to a budget (knapsack) constraint. In the bilevel knapsack interdiction problem, there are two levels of decision-makers. The lower-level decision maker is attempting to solve the classical knapsack problem. The upper-level decision maker has the goal of minimizing the profit of the lower-level decision maker, by picking items that will be then unavailable. The upper-level has its own (independent) knapsack constraint to satisfy too. Previous approaches to this problem were based on using MIP solvers. We develop a branch-and-bound algorithm for the problem that relies on a strong lower bound and specialized branching, using combinatorial arguments. Our approach improves on the previous best approaches by up to two orders of magnitude in our test instances, significantly increasing the size of instances that can be consistently solved to optimality. This is joint work with Noah Weninger.

• Video
• Slides

Abstract

We present several queueing-based optimization models to design networks in which the objective is to minimize the response time. The networks are modelled as collections of interdependent M/G/1 or M/G/K queueing systems with fixed and mobile servers. The optimization models take the form of nonconvex MINLP problems with fractional and bilinear terms. We derive a reformulation approach and propose a solution method that features a warm-start component, new optimality-based bound tightening (OBBT) techniques, and an outer approximation algorithm. In particular, we propose new MILP and feasibility OBBT models that can derive multiple variable bounds at once. The proposed approach is applied to the drone-based delivery of automated external defibrillators to out-of-hospital cardiac arrests (OHCA) and naloxone to opioid overdoses. The computational experiments are based on real-life data from Virginia Beach, and ascertain the computational efficiency of the approach and its impact on the response time and the probability of survival of patients.

• Video

Abstract

I will introduce SageMath, a general-purpose, Python-based, open-source mathematics system in development since 2005, from the viewpoint of its use in Mixed Integer Programming research. Originally conceived as a computer algebra system focused on algebraic number theory, SageMath has grown to a major integrating force in the mathematical software world that provides convenient and unified access to the best libraries and systems for polyhedral geometry, mixed integer linear programming, lattices, graph theory, commutative algebra, symbolic computation, computational group theory, and more. I will demonstrate some of these capabilities. The SageMath community welcomes contributions in the form of expository mathematical writing, constructions, algorithm development and implementation, cataloging, mathematical software integration, and more. I will highlight some possible entry points for making such contributions.

• Video

Abstract

Mixed integer quadratic programming is the problem of minimizing a quadratic polynomial over points in a polyhedral region with some integer components. It is a natural extension of mixed integer linear programming and it has a wide array of applications. In this talk, I will survey some recent theoretical developments in mixed integer quadratic programming, with a focus on complexity, algorithms, and fundamental properties.

• Video
• Slides

Abstract

In the Environmental Justice literature, the Kolm-Pollak Equally Distributed Equivalent (EDE) is the preferred metric for quantifying the experience of a population. The metric incorporates both the center and the spread of the distribution of the individual experiences, and therefore, captures the experience of an “average” individual more accurately than the population mean. In particular, the mean is unable to measure the equity of a distribution, while the Kolm-Pollak EDE is designed to penalize for inequity. In this talk, we explore the problem of finding an optimal distribution from various alternatives using the Kolm-Pollak EDE to quantify optimal. Unfortunately, optimizing over the Kolm-Pollak EDE in a mathematical programming model is not trivial because of the nonlinearity of the function. We discuss methods to overcome this difficulty and present computational results for practical applications. Our results demonstrate that optimizing over the Kolm-Pollak EDE in a standard facility location model has the same computational burden as optimizing over the population mean. Moreover, it often results in solutions that are significantly more equitable while having little impact on the mean of the distribution, versus optimizing over the mean directly. Joint work with Drew Horton, Tom Logan, and Daphne Skipper

• Video

Abstract

We obtain an explicit description for the closure of the convex hull of bivariate quadratic sets with indicator variables the space of original variables. We present a simple separation algorithm that can be incorporated in branch-and-cut based solvers to enhance the quality of existing relaxations.

• Video
• Slides

• Slides

Abstract

We discuss integer-programming-based approaches to doing low-rank matrix completion over the finite field of two elements. We are able to derive an explicit description for the convex hull of an individual matrix element in the decomposition, using this as the basis of a new formulation. Computational results showing the superiority of the new formulation over a natural formulation based on McCormick inequalities with integer-valued variables, and an extended disjunctive formulation arising from the parity polytope are given in the context of linear index coding.

• Video
• Slides

Abstract

Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed-integer programming for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate Fenchel cuts that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. We show that these cuts, in essence, decompose the objective function cut one can simply write using the DW bound. Compared to the objective function cut, these Fenchel cuts lead to a formulation with lower dual degeneracy, and consequently a better computational performance under the standard branch-and-cut framework in the original space. We also discuss how to strengthen these cuts to improve the computational performance further. We test our approach on the Multiple Knapsack Assignment Problem and show that the proposed cuts are helpful in accelerating the solution time without the need to implement branch and price.

• Video

Abstract

I am going to present results obtained jointly with Manuel Aprile, Marco Di Summa, Christopher Hojny and Matthias Schymura. Assume you want to describe a set X of integer points as the set of integer solutions of a linear system of inequalities and you want to use a system for X with the minimum number of inequalities. Can you compute this number algorithmically? The answer is not known in general! Does the choice of the coefficient field (like the field of real and the fiel of rational numbers) have any influence on the number you get as the answer? Surprisingly, it does! On a philosophical level, should we do integer programming over the rationals or real coefficients? That's actually not quite clear, but for some aspects there is a difference so that it might be interesting to reflect on this point and weigh pros and cons.

• Video
• Slides

Abstract

In this talk, we present new strong relaxations for the convex quadratic optimization problem with indicator variables. For the bivariate case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the bivariate case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including Shor's SDP relaxation, the optimal perspective relaxation as well as the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems. This is a joint work with Shaoning Han and Andres Gomez.

Abstract

Integer semidefinite programming can be viewed as a generalization of integer programming where the vector variables are replaced by positive semidefinite integer matrix variables. The combination of positive semidefiniteness and integrality allows to formulate various optimization problems as integer semidefinite programs (ISDPs). Nevertheless, ISDPs have received attention only very recently. In this talk we show how to extend the Chv\'atal-Gomory (CG) cutting-plane procedure to ISDPs. We also show how to exploit CG cuts in a branch-and-cut framework for ISDPs. Finally, we demonstrate the practical strength of the CG cuts in our branch-and-cut algorithm. Our results provide a new perspective on ISDPs.

• Video

Abstract

We establish a polynomial equivalence between tree ensemble optimization and optimization of multilinear functions over the Cartesian product of simplices. Using this, we derive new formulations for tree ensemble optimization problems and 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. We then consider piecewise polyhedral relaxation of multilinear optimization problems. We provide the first ideal formulation over non-regular partitions. We also improve the relaxations over regular partitions by adding linking constraints. These relaxations significantly improve performance of ALPINE and are included in the software.
This is joint work with Jongeun Kim (Google) and J.-P. P. Richard (University of Minnesota).

• Video

Abstract

We introduce a novel aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We present a novel branch-and-cut algorithm integrated with stochastic dual dynamic programming as an exact solution method to the aggregated MSILP, which can also be used in an approximation form to obtain dual bounds and implementable feasible solutions. Moreover, we apply two-stage linear decision rule (2SLDR) approximations and propose MC-based variants to obtain high-quality decision policies with significantly reduced computational effort. We test the proposed methodologies in a novel MSILP model for hurricane disaster relief logistics planning.

• Video
• Slides

Abstract

Solving linear programs is nowadays an everyday task. Used even in embedded systems, but also run on very large hardware. However, solving very large models has remained a major challenge. Either because most successful algorithms require more than linear space to solve such models, or because they become extremely slow in practice. Although the concept of first order-methods, and potential function methods have been around for a long time, they have failed to be broadly applicable, or no competitive implementations are widely available. In this talk we will be motivating the need for such a class of algorithms, share some (known) evidence that such schemes have worked in special situations, and present results of experiments running one such algorithm (PDLP) both in standard benchmark models, and also on very large models arising from network planning. And also on a first order method for general LPs using an exponential potential function to deal with unstructured constraints.

• Video

Abstract

Algorithms for mixed-integer optimization problems are based on the sequential construction of tractable relaxations of the discrete problem, until the relaxations are sufficiently tight to guarantee optimality of the resulting solution. For classical operational and logistics problems, which can be formulated as mixed-integer linear optimization problems, it is well-known that such relaxations should be polyhedral. Thus, there has been a sustained stream of research spanning several decades on constructing and exploiting linear relaxations. As a consequence, mixed-integer linear optimization problems deemed to be intractable 30 years old can be solved to optimality in seconds or minutes nowadays. Modern statistical and decision-making problems call for mixed-integer nonlinear optimization (MINLO) formulations, which inherently lead to non-polyhedral relaxations. There has been a substantial progress in extending and adapting techniques for both the mixed-integer linear optimization and continuous nonlinear literatures, but there may a fundamental limit on the effectiveness of such approaches as they fail to exploit the specific characteristics of MINLO problems. In this talk, we discuss recent progress in studying the fundamental structure of MINLO problems. In particular, we show that such problems have a hidden polyhedral substructure that captures the non-convexities associated with discrete variables. Thus, by exploiting this substructure, convexification theory and methods based on polyhedral theory can naturally be used study non-polyhedral sets. We also provide insights into how to design algorithms that tackle the ensuing relaxations.

• Video

Abstract

This paper studies the rank constrained optimization problem (RCOP) that aims to minimize a linear objective function over intersecting a prespecified closed rank constrained domain set with two-sided linear matrix inequalities. The generic RCOP framework exists in many nonconvex optimization and machine learning problems. Although RCOP is, in general, NP-hard, recent studies reveal that its Dantzig-Wolfe Relaxation (DWR), which refers to replacing the domain set by its closed convex hull, can lead to a promising relaxation scheme. This motivates us to study the strength of DWR. Specifically, we develop the first-known necessary and sufficient conditions under which the DWR and RCOP are equivalent. Beyond the exactness, we prove the rank bound of optimal DWR extreme points. We design a column generation algorithm with an effective separation procedure. The numerical study confirms the promise of the proposed theoretical and algorithmic results.

• Video
• Slides