## 90C26 Nonconvex programming, global optimization

### Refine

#### Document Type

- ZIB-Report (17)
- Doctoral Thesis (2)

#### Keywords

- Pooling Problem (4)
- nonconvex (3)
- Cutting Planes (2)
- Large Neighborhood Search (2)
- MINLP (2)
- Nonconvexity (2)
- Primal Heuristic (2)
- Quadratic Programming (2)
- Relaxation (2)
- Relaxations (2)

#### Institute

We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.

This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with
fixed convexity behavior over a box.
Computational results comparing our cut-generation algorithms with
state-of-the-art global
optimization software on a series of randomly generated test instances are reported and discussed.

Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times.

In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP).
In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are:
- Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation,
- a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP,
- an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures,
- RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution,
- Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP,
- Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs,
- Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection.
Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes.
The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress.

This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.

Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty
(2017)

The amazing success of computational mathematical optimization over
the last decades has been driven more by insights into mathematical
structures than by the advance of computing technology. In this vein,
we address applications, where nonconvexity in the model and
uncertainty in the data pose principal difficulties.
The first part of the thesis deals with non-convex quadratic programs.
Branch&Bound methods for this problem class depend on tight
relaxations. We contribute in several ways: First, we establish a new
way to handle missing linearization variables in the well-known
Reformulation-Linearization-Technique (RLT). This is implemented
into the commercial software CPLEX. Second, we study the optimization
of a quadratic objective over the standard simplex or a knapsack
constraint. These basic structures appear as part of many complex
models. Exploiting connections to the maximum clique problem and RLT,
we derive new valid inequalities. Using exact and heuristic separation
methods, we demonstrate the impact of the new inequalities on the
relaxation and the global optimization of these problems. Third, we
strengthen the state-of-the-art relaxation for the pooling problem, a
well-known non-convex quadratic problem, which is, for example,
relevant in the petrochemical industry. We propose a novel relaxation
that captures the essential non-convex structure of the problem but is
small enough for an in-depth study. We provide a complete inner
description in terms of the extreme points as well as an outer
description in terms of inequalities defining its convex hull (which
is not a polyhedron). We show that the resulting valid convex
inequalities significantly strengthen the standard relaxation of the
pooling problem.
The second part of this thesis focuses on a common challenge in real
world applications, namely, the uncertainty entailed in the input
data.
We study the extension of a gas transport network, e.g., from our
project partner Open Grid Europe GmbH.
For a single scenario this maps to a challenging non-convex MINLP.
As the future transport patterns are highly uncertain, we propose a
robust model to best prepare the network operator for an array of
scenarios.
We develop a custom decomposition approach that makes use of the
hierarchical structure of network extensions and the loose coupling
between the scenarios.
The algorithm used the single-scenario problem as black-box subproblem
allowing the generalization of our approach to problems with the same
structure.
The scenario-expanded version of this problem is out of reach for
today's general-purpose MINLP solvers.
Yet our approach provides primal and dual bounds for instances with up
to 256 scenarios and solves many of them to optimality.
Extensive computational studies show the impact of our work.

The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties.
This paper summarizes the dissertation of Jonas Schweiger for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quadratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch&Bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases.

In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.

We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.