A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities with Applications to Bilevel Optimization and Gas Transport

We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate … Read more

Optimal configurations for modular systems at the example of crane bridges

The aim of this paper is to optimize modular systems which cover the construction of products that can be assembled on a modular basis. Increasing the number of different variants of individual components on the one hand decreases the cost of oversizing the assembled product, while on the other hand the cost for maintaining the … Read more

Superadditive duality and convex hulls for mixed-integer conic optimization

We present an infinite family of linear valid inequalities for a mixed-integer conic program, and prove that these inequalities describe the convex hull of the feasible set when this set is bounded and described by integral data. The main element of our proof is to establish a new strong superadditive dual for mixed-integer conic programming … Read more

Copositive programming for mixed-binary quadratic optimization via Ising solvers

Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing … Read more

Multilinear formulations for computing Nash equilibrium of multi-player matrix games

We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player strategic-form games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended … Read more

Cutting-plane algorithm for sparse estimation of the Cox proportional-hazards model

Survival analysis is a family of statistical methods for analyzing event occurrence times. In this paper, we address the mixed-integer optimization approach to sparse estimation of the Cox proportional-hazards model for survival analysis. Specifically, we propose a high-performance cutting-plane algorithm based on reformulation of bilevel optimization for sparse estimation. This algorithm solves the upper-level problem … Read more

Recursive McCormick Linearization of Multilinear Programs

Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce … Read more

A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems

We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of … Read more

Computing an enclosure for multiobjective mixed-integer nonconvex optimization problems using piecewise linear relaxations

In this paper, a new method for computing an enclosure of the nondominated set of multiobjective mixed-integer problems without any convexity requirements is presented. In fact, our criterion space method makes use of piecewise linear relaxations in order to bypass the nonconvexity of the original problem. The method chooses adaptively which level of relaxation is … Read more

Piecewise Polyhedral Relaxations of Multilinear Optimization

In this paper, we consider piecewise polyhedral relaxations (PPRs) of multilinear optimization problems over axis-parallel hyper-rectangular partitions of their domain. We improve formulations for PPRs by linking components that are commonly modeled independently in the literature. Numerical experiments with ALPINE, an open-source software for global optimization that relies on piecewise approximations of functions, show that … Read more