Global Optimization – Page 24 – Optimization Online

The Cost of Not Knowing Enough: Mixed-Integer Optimization with Implicit Lipschitz Nonlinearities

Published: 2018/04/26, Updated: 2021/10/13

(Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Global Optimization gas networks, global optimization, lipschitz optimization, mixed-integer nonlinear programming

It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit … Read more

Subdeterminants and Concave Integer Quadratic Programming

Published: 2018/04/23, Updated: 2019/08/28

Alberto Del Pia

(Mixed) Integer Nonlinear Programming, Global Optimization Theory approximation algorithms, concave function, integer quadratic programming, subdeterminants, total bimodularity, total unimodularity

We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of … Read more

Tightening McCormick Relaxations Toward Global Solution of the ACOPF Problem

Published: 2018/04/10, Updated: 2018/11/21

Global Optimization Applications acopf, bounds tightening, convex relaxation

We show that a strong upper bound on the objective of the alternating current optimal power flow (ACOPF) problem can significantly improve the effectiveness of optimization-based bounds tightening (OBBT) on a number of relaxations. We additionally compare the performance of relaxations of the ACOPF problem, including the rectangular form without reference bus constraints, the rectangular … Read more

An Active Set Algorithm for Robust Combinatorial Optimization Based on Separation Oracles

Published: 2018/04/04

Christoph Buchheim

Marianna De Santis

Combinatorial Optimization, Global Optimization, Robust Optimization active-set methods, robust optimization, socp

We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the … Read more

Rigorous global filtering methods with interval unions

Published: 2018/04/03

This paper presents rigorous filtering methods for constraint satisfaction problems based on the interval union arithmetic. Interval unions are finite sets of closed and disjoint intervals that generalize the interval arithmetic. They allow a natural representation of the solution set of interval powers, trigonometric functions and the division by intervals containing zero. We show that … Read more

Rigorous packing of unit squares into a circle

Published: 2018/04/03

Let $r_{n}$ be the radius of the smallest circle into which one can pack $n$ non-overlapping unit squares that are free to rotate. For $n = 1, 2$, $r_{1} = \frac{\sqrt{2}}{2}$ and $r_{2} = \frac{\sqrt{5}}{2}$ are proved to be optimal. For $n \geq 3$ only guesses of $r_{n}$ are known. This paper introduces a computer-assisted … Read more

BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

Published: 2018/04/02, Updated: 2018/04/03

Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming bisection and projection methods, box and complementarity constraints, efficiency, hierarchy of doubly nonnegative relaxations, high-degree polynomial optimization problems with binary, matlab software package, sparsity, tight lower bounds

The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a … Read more

User Manual for BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

Published: 2018/04/02, Updated: 2018/04/03

Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming bisection and projection method, doubly nonnegative relaxation, large-scale optimization, matlab software package, polynomial optimization problems

BBCPOP proposed in [4] is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity constraints. Given a POP in the class and a relaxation order (or a hierarchy level), BBCPOP constructs a simple conic optimization problem (COP), which … Read more

A computational study of global optimization solvers on two trust region subproblems

Published: 2018/04/02

Ferenc Domes

Arnold Neumaier

Tiago Montanher

Global Optimization, Global Optimization Applications, Optimization Software Benchmark

One of the relevant research topics to which Chris Floudas contributed was quadratically constrained quadratic programming (QCQP). This paper considers one of the simplest hard cases of QCQP, the two trust region subproblem (TTRS). In this case, one needs to minimize a quadratic function constrained by the intersection of two ellipsoids. The Lagrangian dual of … Read more

New SOCP relaxation and branching rule for bipartite bilinear programs

Published: 2018/03/25

Santanu S. Dey

Asteroide Santana

Yang Wang

Global Optimization Applications, Global Optimization Theory

A bipartite bilinear program (BBP) is a quadratically constrained quadratic optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than … Read more