On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming

Benjamin Müller, Gonzalo Muñoz, Maxime Gasse, Ambros Gleixner, Andrea Lodi, Felipe SerranoMath. Program 2019

Abstract

The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.

Introduction

To solve complex Mixed-Integer Nonlinear Programs (MINLPs) to global optimality, solvers typically employ a "spatial branch-and-bound" algorithm. This process relies heavily on relaxations: simplified versions of the original problem that are easier to solve and provide a "dual bound" (a mathematical floor on how good the solution can be). Traditionally, these relaxations are required to be convex because convex problems are computationally well-behaved. However, convex relaxations are often "loose," meaning the gap between the estimated floor and the actual optimal solution is large, forcing the solver to perform significantly more work in the search tree.

This research breathes new life into "surrogate duality"—a technique from the 1970s—by applying it to modern MINLP. The authors tackle a fundamental question: Since modern solvers have become much better at handling a moderate amount of non-convexity, can we use non-convex relaxations to get tighter bounds? Specifically, they look at surrogate relaxations, which simplify a problem by aggregating many difficult constraints into a single (or a few) weighted sums.

Methodology: The Generalized Surrogate Dual

The core of the paper is the Generalized Surrogate Dual. While classic surrogate duality aggregates all constraints into one ($K=1$), this paper explores using $K$ multiple aggregations. To find the best weights ($\lambda$) for these aggregations, the authors developed a Benders-type algorithm consisting of two parts:

  1. Master Problem: A Mixed-Integer Linear Program (MILP) that searches for the optimal weights to maximize the "violation" of points that were feasible in previous relaxations but should be excluded.
  2. Sub-problem: Solves the resulting surrogate relaxation to find a new candidate solution point.

Computational Enhancements and Stabilization

Solving these problems is computationally expensive, necessitating several "practicality" enhancements. The authors incorporated existing linear cuts (like Gomory or gradient cuts) directly into the surrogate set and utilized early stopping to terminate sub-problems once a "good enough" bound was found.

Comparison of the surrogate dual function S(λ) and the Lagrangian dual function L(λ).

As shown in the figure above, the surrogate dual function $S(\lambda)$ can be non-smooth and even discontinuous compared to the more well-behaved Lagrangian dual $L(\lambda)$. This behavior makes the optimization of weights particularly challenging. To address this, the authors implemented Support Stabilization (restricting the search to a subset of constraints) and Trust-Region Stabilization to prevent the weights from oscillating wildly between iterations.

Key Insights and Results

The authors evaluated their algorithm using MINLPLib, a standard library of 1,671 publicly available MINLP instances, focusing on a subset of 633 challenging instances.

  • The Power of $K > 1$: A single aggregation ($K=1$) often fails to capture the problem's structure. Moving to $K=2$ or $K=3$ aggregations drastically improves the bound. On average, $K=1$ closed 18.4% of the root gap, while $K=3$ closed 23.4%.
  • Non-convexity as a Tool: The paper demonstrates that retaining some non-convexity in the relaxation can lead to much tighter bounds that more than compensate for the extra effort required to solve the relaxation.
  • High-Impact Instances: On a subset of "affected" instances where the method was particularly successful, $K=3$ closed an impressive 46.9% of the gap. For several difficult benchmark problems (like the polygon* and facloc* series), the algorithm found dual bounds significantly stronger than the best-known bounds in existing literature.

Conclusion and Future Work

While the computational cost of solving the MILP master problem and non-convex sub-problems remains a challenge, the results prove that generalized surrogate duality is a powerful tool for tightening dual bounds in MINLP. Future research will focus on quadratic specialization—where sub-problems might be solved as convex Mixed-Integer Quadratically Constrained Programs (MIQCPs)—and developing pure surrogate branching rules to further improve the efficiency of the branch-and-bound search.

Summary updated

Abstract

The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.
BibTeX
@inproceedings{muller2019generalized,
  author = {Benjamin Müller and Gonzalo Muñoz and Maxime Gasse and Ambros Gleixner and Andrea Lodi and Felipe Serrano},
  title = {{On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming}},
  booktitle = {Math. Program},
  year = {2019},
}
Figure