Tighter McCormick Relaxations through Subgradient Propagation

Tight convex and concave relaxations are of high importance in the field of deterministic global optimization. We present a heuristic to tighten relaxations obtained by the McCormick technique. We use the McCormick subgradient propagation (Mitsos et al., SIAM J. Optim., 2009) to construct simple affine under- and overestimators of each factor of the original factorable … Read more

BASBL: Branch-And-Sandwich BiLevel solver. II. Implementation and computational study with the BASBLib test set

We describe BASBL, our implementation of the deterministic global optimization algorithm Branch-and-Sandwich for nonconvex/nonlinear bilevel problems, within the open-source MINOTAUR framework. The solver incorporates the original Branch-and-Sandwich algorithm and modifications proposed in the first part of this work. We also introduce BASBLib, an extensive online library of bilevel benchmark problems collected from the literature and … Read more

Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

We introduce Sieve-SDP, a simple algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP belongs to the class of facial reduction algorithms. It inspects the constraints of the problem, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine … Read more

Best subset selection of factors affecting influenza spread using bi-objective optimization

A typical approach for computing an optimal strategy for non-pharmaceutical interventions during an influenza outbreak is based on statistical ANOVA. In this study, for the first time, we propose to use bi-objective mixed integer linear programming. Our approach employs an existing agent-based simulation model and statistical design of experiments presented in Martinez and Das (2014) … Read more

BASBL: Branch-And-Sandwich BiLevel solver I. Theoretical advances and algorithmic improvements

In this paper, we consider the global solution of bilevel programs involving nonconvex functions. We present algorithmic improvements and extensions to the recently proposed deterministic Branch-and-Sandwich algorithm (Kleniati and Adjiman, J. Glob. Opt. 60, 425–458, 2014), based on the theoretical results and heuristics. Choices in the way each step of the Branch-and-Sandwich algorithm is tackled, … Read more

Convergence rates of accelerated proximal gradient algorithms under independent noise

We consider an accelerated proximal gradient algorithm for the composite optimization with “independent errors” (errors little related with historical information) for solving linear inverse problems. We present a new inexact version of FISTA algorithm considering deterministic and stochastic noises. We prove some convergence rates of the algorithm and we connect it with the current existing … Read more

Approximation of Minimal Functions by Extreme Functions

In a recent paper, Basu, Hildebrand, and Molinaro established that the set of continuous minimal functions for the 1-dimensional Gomory-Johnson infinite group relaxation possesses a dense subset of extreme functions. The n-dimensional version of this result was left as an open question. In the present paper, we settle this query in the affirmative: for any … Read more

Optimal cutting planes from the group relaxations

We study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson’s finite and infinite group models and we describe the valid inequalities that are optimal for these criteria. We justify and focus on the criterion of maximizing the volume of the nonnegative orthant cut off by a valid inequality. For the … Read more

Global optimization of mixed-integer ODE constrained network problems using the example of stationary gas transport

In this paper we propose a new approach for finding global solutions of mixed-integer nonlinear optimization problems with ordinary differential equation constraints on networks. Instead of using a first discretize then optimize approach, we combine spatial and variable branching with appropriate discretizations of the differential equations to derive relaxations of the original problem. To construct … Read more

Complete Facial Reduction in One Step for Spectrahedra

A spectrahedron is the feasible set of a semidefinite program, SDP, i.e., the intersection of an affine set with the positive semidefinite cone. While strict feasibility is a generic property for random problems, there are many classes of problems where strict feasibility fails and this means that strong duality can fail as well. If the … Read more