Workshop Details

More than 50 years of development have made mixed integer linear programming (MILP) an extremely successful tool. MILP’s modeling flexibility allows it describe a wide range of business, engineering and scientific problems, and, while MILP is NP-hard, many of these problems are routinely solved in practice thanks to state-of-the-art solvers that nearly double their machine-independent speeds every year. Inspired by this success, the last decade has seen a surge of activity on the solution and application of mixed integer convex programming (MICP), which extends MILP’s versatility by allowing the use of convex constraints in addition to linear inequalities.

In this talk we cover various recent developments concerning theory, algorithms and computation for MICP. Solvers for MICP can be significantly more effective than those for more general non-convex optimization, so one of the questions we cover in this talk is what classes of non-convex constraints can be modeled through MICP. We also cover various topics concerning the modeling and computational solution of MICP problems using the Julia programming language and the JuMP modeling language for optimization. In particular, we show how mixed integer optimal control problems where the variables are polynomials can be easily modeled and solved by seamlessly combining several Julia packages and JuMP extensions with the Julia-written MICP solver Pajarito.jl. Finally, we introduce Hypatia.jl: a Julia-based interior point solver for general non-symmetric conic programming.

We introduce a new relaxation framework for MINLPs. These new relaxations, called composite relaxations, are tighter than the prevalent factorable programming relaxations, implemented in many state-of-the-art solvers. The tightness arises from a new way to exploit multiple estimators for each inner function at a time. Our relaxation procedure involves two steps. First, the inner function structure is encoded in a polytope. Second, the outer function is relaxed over this polytope. Although the separation problem for the graph of the outer function over the aforementioned polytope is NP-Hard in general, there are several tractable instances, which provide new ways to develop tight relaxations for MINLP. For example, we show that if the outer function is supermodular and concave-extendable, its hypograph can be separated in O(dn log d) where d is the number of inner functions and n is the number of estimators of each inner function. The validity of the derived inequalities can be seen easily using certain telescoping expansions. This derivation allows us to generalize the construction of valid inequalities to cases where the outer-function is not concave extendable. The composite relaxations, we develop, are well-suited for constructing MIP relaxations via discretization strategies and for relaxing functions over discrete domains. Exploiting these results, we develop various discretization strategies. When the outer function is supermodular and the inner functions are univariate, our relaxations yield an ideal MIP formulation for the discrete case. For the continuous case, when the outer function is also Liptschitz continuous, the ideal formulation yields a sequence of relaxations that converge to the concave envelope.  When the outer-function is convex in each argument, the limiting relaxation obtained with infinitely many estimators for each inner-function arises as a solution of an optimal transport problem. We conclude with preliminary computational experience with these relaxations.

Joint work with Taotao He.

In this talk, we focus on mixed integer non linear programming (MINLP) problems with non convexities that can be formulated as sums of univariate functions. D'Ambrosio et al. 2009 and D'Ambrosio et al. 2012 proposed a method called Sequential Convex MINLP (SC-MINLP), an iterative algorithm based on lower and upper bounds obtained by solving a convex MINLP and a non convex non linear program, respectively. The method aims at finding a global solution of the tackled MINLP and exploits the fact that the convex or concave parts of univariate functions can be identified numerically. The weaknesses of the original version of the SC-MINLP method are mainly two: on the one hand, solving several (one per iteration) convex MINLPs is time-consuming; on the other hand, at each iteration, the convex MINLP is modified to improve the lower bound and no information about the previous convex MINLP and its optimal solution is exploited. These two weaknesses are addressed in two recent works: in the first, a strengthening of the convex MINLP relaxation is proposed based on perspective reformulation. In the second, a disjunctive programming approach was explored to better approximate the concave parts of each univariate function. Extensive computational experiments show a significant speedup of the original SC-MINLP method.

We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. We also introduce novel branching variable selection strategies which can be used in conjunction with the quadratic relaxations investigated in this paper. We integrate the proposed relaxation and branching techniques into the global optimization solver BARON, and test our implementation by conducting numerical experiments on a large collection of problems. Results demonstrate that the proposed implementation leads to very significant reductions in BARON's computational times to solve the test problems. This is joint work with Carlos Nohra and Arvind Raghunathan.

Quadratically-constrained quadratic programs (QCQPs) are an active and challenging research topic in optimization. Their remarkable expressiveness has made these problems a cornerstone in the development of theoretical and practical improvements in non-convex optimization. While modern computational methods, especially those associated to semidefinite programming (SDP), are able to provide strong bounds, they typically rely on computationally-expensive computations hindering their applicability in medium-to-large-scale problems. In this work, we develop a computationally-efficient method that emulates the SDP-based approximations of nonconvex QCQPs via a cutting plane algorithm. These cuts are required to be sparse, in order to ensure attractive numerical properties, and efficiently computable. We present a novel connection between such sparse cut generation and the sparse principal component analysis (PCA) problem in statistics, which allows us to achieve these two goals. We show extensive computational results advocating for the use of our approach.

(Based on joint work with Santanu S. Dey, Andrea Lodi, and Gonzalo Muñoz)

Random projections map a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Although random projections are usually applied to numerical data, we show they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higher-dimensional original problem, we solve the projected problem more efficiently. We also show how to retrieve a feasible solution of the original problem from the lower-dimensional solution of the projected problem. We then show that the retrieved solution can be used to bound the optimal objective function value of the original problem from below and above, and prove that the lower and upper bounds are not too far apart. We then discuss a set of computational results on randomly generated instances, as well as a variant of Markowitz’ portfolio problem.

Joint work with C. D'Ambrosio, P.-L. Poirion, K. Vu

For an integer optimization problem (IP), one important data parameter is the maximum  absolute value among all  square submatrices of the constraint matrix.

We present recent developments about this topic. In particular we show that almost all problems (IP) with constant data parameter can be solved in polynomial time.

We show that local minimality of a point for a cubic polynomial can be checked in polynomial time. This settles the only case in constrained or unconstrained polynomial optimization where the complexity of testing local optimality was left open by prior literature. We also show that a local minimum of a cubic polynomial can be found by solving polynomially many semidefinite programs of polynomial size. What enables these results is some intriguing geometry and algebra that cubic polynomials give rise to. Joint work with Jeffrey Zhang (Princeton).

Decision trees usefully represent sparse, high dimensional and noisy data. Having learned a function from this data, we may want to thereafter integrate the function into a larger decision-making problem, e.g., for picking the best chemical process catalyst. We study a large-scale, industrially-relevant mixed-integer nonlinear nonconvex optimization problem involving both gradient-boosted trees and penalty functions mitigating risk. This mixed-integer optimization problem with convex penalty terms broadly applies to optimizing pre-trained regression tree models. Decision makers may wish to optimize discrete models to repurpose legacy predictive models, or they may wish to optimize a discrete model that particularly well-represents a data set. We develop several heuristic methods to find feasible solutions, and an exact, branch-and-bound algorithm leveraging structural properties of the gradient-boosted trees and penalty functions. We computationally test our methods on concrete mixture design instance and a chemical catalysis industrial instance.

Algorithms to solve mixed integer linear programs have made incredible progress in the past 20 years.  Key to these advances has been a mathematical analysis of the structure of the set of feasible solutions.  We argue that a similar analysis is required in the case of mixed integer quadratic programs, like those that arise in sparse optimization in machine learning.  One such analysis leads to the so-called perspective relaxation, which significantly improves solution performance on separable instances. The most novel contribution of this work is a demonstration that extensions of the perspective reformulation can lead to algorithms that are *equivalent* to popular, modern, sparsity-inducing non-convex regularizations in variable selection.

Based on joint work with Hongbo Dong (Washington State Univ. ), Oktay Gunluk (IBM), and Kun Chen (Univ. Connecticut)

We propose quantum subroutines for the simplex method that avoid classical computation of the basis inverse. For a well-conditioned $m times n$ constraint matrix with at most $d_c$ nonzero elements per column, at most $d$ nonzero elements per column or row of the basis, and optimality tolerance $epsilon$, we show that pricing can be performed in time $tilde{O}(frac{1}{epsilon}sqrt{n}(d_c n + d^2 m))$, where the $tilde{O}$ notation hides polylogarithmic factors; if the sparsity is constant, which is often the case in practice, this yields a runtime of $tilde{O}(frac{1}{epsilon}  sqrt{n}(n + m))$. If the ratio $n/m$ is larger than a certain threshold, the runtime of the quantum routine can be reduced to $tilde{O}(frac{1}{epsilon}d sqrt{d_c} n sqrt{m})$. Classically, pricing would require $O(m^{2.373} + d_c n)$ in the worst case. The ratio test can be performed in time $tilde{O}(frac{1}{delta} d^2 m^{1.5})$, where $delta$ is a feasibility tolerance; classically, this requires $O(m^2)$ in the worst case. For well-conditioned sparse problems, the quantum subroutines may therefore have a worst-case asymptotic advantage. The input of our quantum subroutines is the natural description of the problem data, and the output is the index of the variables that should leave or enter the basis.

We propose polyhedral relaxations for several NP-hard problems that arise in community detection and data clustering. We study the theoretical properties of these relaxations and compare them with the widely-used semi-definite programming relaxations in data-science literature.

Linearizable binary quadratic problem (BQP) instances are instances whose optimal solution can be obtained by solving the corresponding linear instance of the problem. In general, BQP instances are not linearizable and for many BQPs we do not have a complete characterization of the set of the linearizable instances. However, it is not difficult to identify a subset of linearizable instances for a given BQP. In this talk we show how to exploit such subset to obtain bounds for the original problem.

In particular, we propose a bounding strategy, called the linearization based scheme that is based on a simple certificate for a quadratic function to be non-negative on the feasible set. We also show that several known bounding approaches including the Generalized Gilmore-Lawler scheme and the first level RLT relaxation provide linearization based bounds. Finally, we demonstrate quality of linearization based bounds for the Quadratic Shortest Path problem and the Quadratic Cycle Cover Problem.

We address two classes of MINLP problems in this talk: convex MINLP and nonconvex MIQP. For the first, we discuss linearization algorithms and different strategies of adding linear cuts to strengthen the MILP master problem. We compare the outer approximation (OA) and the extended cutting plane (ECP) algorithms, and present a modification in ECP that aims at accelerating its convergence, still keeping the algorithm as a first order method. For MIQP, we discuss different strategies of convexifying an indefinite quadratic form, by decomposing it into the difference of two quadratic functions and applying linearization techniques for the remaining nonconvex quadratic.

We first provide a brief description of the "moment-SOS hierarchy". Initially designed for solving polynomial optimization problems, it is based on powerful positivity certificates from real algebraic geometry combined with semidefinite programming (an efficient technique from convex optimization).  it consists of a hierarchy of convex (semidefinite) relaxations whose size increases and whose associated monotone sequence of optimal values converges to the global minimum. Finite convergence is generic and fast in practice. 

In fact, this methodology also applies to solve the "Generalized Problem of Moments" (GPM) (of which global optimization is only a particular instance, and even the simplest). Then we briefly describe its application to several of many other applications outside optimization, notably in dynamical systems (control, optimal control, and analysis of some non-linear hyperbolic PDEs), statistics (optimal design), probability, computational geometry?

A convex cone $K$ that is a subset of the positive semidefinite (PSD) cone is called rank-one generated (ROG) if all of its extreme rays are generated by rank 1 matrices. ROG property is closely related to the characterizations of exactness of SDP relaxations, e.g., of nonconvex quadratic programs. We consider the case when $K$ is obtained as the intersection of the PSD cone with finitely many linear (or conic) matrix inequalities, and identify sufficient conditions that guarantee that $K$ is ROG. In the case of two linear matrix inequalities, we also establish the necessity of our sufficient condition.

This is joint work with C.J. Argue.

We describe the properties of a smooth exact merit function first proposed by Fletcher (1970), and the details of our own implementation. The main computational kernel is solving structured linear systems. We show how to solve these systems efficiently by storing a single factorization per iteration when the matrices are available explicitly. We also give a factorization-free implementation. The penalty function shows particular promise when such linear systems can be solved efficiently, e.g., for PDE-constrained optimization problems where efficient preconditioners exist. Regularization provides robustness towards the solution of degenerate problems. A special feature of our implementation is the ability to evaluate inexact first and second derivatives of the merit function while preserving global convergence.

Co-Authors: Ron Estrin, Michael Saunders, Michael Friedlander

Generalized inverses are ubiquitous in matrix algebra and its applications. Not all Moore-Penrose properties are needed to ensure that a generalized inverse solves key problems, like least squares. So there is the opportunity to find sparser generalized inverses that do the jobs. I will present theoretical and computational results on various approaches to this, in particular approximation algorithms and convex relaxation. Joint works with: Marcia Fampa, Luze Xu and Gabriel Ponte.

An interesting class of nonlinear discrete optimization problems arises in robust optimization. For a combinatorial optimization problem with linear but uncertain objective, the (strictly) robust counterpart has a nonlinear objective whose characteristics depend on the considered uncertainty set. E.g., if the latter is an ellipsoid, the objective can be modelled by a second-order cone constraint. A lot of effort has been put into the investigation of specific combinatorial structures, in order to develop tailored algorithms or to show hardness results. In our talk, the focus is on algorithms that can access the underlying combinatorial structure only via a linear optimization or a separation routine. We first discuss the existence of oracle-polynomial algorithms for some typical classes of uncertainty sets. In the second part of the talk, we present new algorithmic approaches that allow to deal with general ellipsoidal or polytopal uncertainty sets, which lead to NP-hard problems in general. These approaches are based on well-known methods from continuous optimization, such as the Frank-Wolfe technique or active set methods, and do not depend on the specific combinatorial structure but require only an optimization or a separation oracle for the underlying problem.

A mixed-integer conic program (MICP) optimizes a linear function over the set of mixed-integer points in the nonnegative orthant satisfying the conic inequality constraints $A(x) preceq_K b$, where $A: R^n to E$ is a linear map, E is a  Euclidean space (either $R^m$ or $R^{mtimes m}$), and $K$ is a nonempty closed convex pointed full-dimensional cone. Commonly occurring special cases are MILP, MISOCP, and MISDP. Strong duals for MILPs were established in the 1970’s and these duals are infinite-dimensional optimization problems in the space of subadditive functionals. More recently, Moran, Dey, and Vielma (2012) generalized these results to MICP and established strong duality under some technical conditions. This dual imposes subadditivity over the domain of the functionals, which is taken to be the entire space $E$. Our first main result is to show that strong duality persists even if the domain of the functional is any set that is closed under sum decomposition over the polyhedral cone formed by the generators of $A$. This reduces the size of the subadditive dual and in particular, our dual is an LP when the primal is pure integer, which is a generalization of classical results on linear IPs. Our second result is to establish a new strong dual for MICP that has subadditivity constraints and some other linear and conic constraints. Thus, it dispenses with the directional-derivative constraints that the Moran et al. dual has for continuous variables and which are computationally intractable. Our third result is to use our strong duals to construct extended formulations for the integer hull of MICP. This  generalizes the extension for linear IPs that was derived by Lasserre (2004,2005) using connections with integer Farkas lemma and subadditive duality.

This is based on joint work with Temitayo Ajayi and Andrew Schaefer (Rice University) and Amin Khademi (Clemson University).

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms. In the first part of the talk, we study the relative efficiency of BB and CP, when both are based on variable disjunctions. In the second part of the talk, we will discuss the conjecture that the split closure has polynomial complexity in fixed dimension, which has remained open for a while now even in 2 dimensions. We settle it affirmatively in two dimensions, and complement it with a polynomial time pure cutting plane algorithm for 2 dimensional IPs based on split cuts.

An important approach to solving non-convex quadratically constrained quadratic program (QCQP) to global optimality is to use convex relaxations and branch-and-bound algorithms. In our first result, we show that the exact convex hull of the solutions of a general quadratic equation intersected with any polytope is second-order cone representable. The proof is constructive and relies on the discovery of an interesting property of quadratic functions, which may be of independent interest: A set defined by a single quadratic equation is either (1) the boundary of a convex set, or (2) the boundary of union of two convex sets or (3) it has the property that through every point on the surface, there exists a straight line that is entirely contained in the surface. We next study sets defined for matrix variables that satisfy rank-1 constraint together with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. Finally, we present results from comprehensive set of computational experiments and show that our convexification results together with discretization significantly help in improving dual bounds for the generalized pooling problem.

This is joint work with Asteroide Santana and Burak Kocuk.