A Convexication-based Outer-approximation Method for Convex and Nonconvex MINLP

Zedong Peng, Kaiyu Cao, Kevin C. Furman, Can Li, Ignacio E. Grossmann, David E. Bernal NeiraComputer-aided 2024 · DOI · arXiv · OpenAlex

Introduction

Mixed-Integer Nonlinear Programming (MINLP) represents one of the most challenging classes of mathematical optimization, merging the combinatorial complexity of discrete variables with the geometric intricacies of nonlinear functions. These problems are foundational to critical infrastructure and industrial processes, such as power grid management and chemical plant scheduling.

Traditional decomposition techniques, notably Outer-Approximation (OA), tackle MINLPs by alternating between a linear MILP "master" problem to identify discrete candidates and a nonlinear NLP "subproblem" to optimize continuous variables. However, these methods frequently encounter efficiency bottlenecks due to poor initialization—where early iterations yield infeasible subproblems—and the inherent difficulty of maintaining valid linear relaxations for nonconvex functions.

Methodology: Convexification-based Initialization

This research introduces a refined approach implemented within the Pyomo-MindtPy toolbox, focusing on a robust initialization phase to enhance standard decomposition algorithms. The core strategy involves:

  1. Domain Reduction: Utilizing Feasibility-based and Optimality-based Bound Tightening (FBBT/OBBT) to aggressively shrink the search space before the main iterative loop begins.
  2. Convexification Cuts: Generating valid linear relaxations via McCormick relaxations or the Auxiliary Variable Method. These cuts ensure that the linear approximations remain valid "under-estimators" even for nonconvex functions, facilitating global optimality guarantees.
  3. Subproblem Scaling: The study evaluated "reduced-scale" vs. "complete-scale" NLP subproblems. It was determined that omitting redundant convexification cuts from the NLP subproblems (where original nonlinear constraints are already present) reduces computational overhead without sacrificing accuracy.
  4. Algorithmic Integration: These enhancements were applied to both multi-tree OA and single-tree LP/NLP-based Branch and Bound (B&B) frameworks.

Experimental Evaluation

The proposed methods were benchmarked using the MINLPLib library, comprising 434 convex and 181 nonconvex instances. Each selected problem featured at least one discrete and one continuous variable to ensure a representative MINLP challenge.

Key Results and Insights

The integration of domain reduction and convexification significantly improved solver performance across both problem types.

Convex Performance

For convex instances, the convexification-based variants (prefixed with C-) demonstrated superior speed and iteration efficiency. The C-LP/NLP-B&B(r) variant, in particular, solved more instances within shorter timeframes compared to standard baselines.

Performance profiles for convex MINLP instances comparing solution time and iteration counts across different algorithm variants.

Nonconvex Robustness

In the nonconvex domain, Global Outer-Approximation (GOA) combined with domain reduction showed a distinct advantage. The results confirm that high-quality initial linear approximations are critical for guiding the solver toward global optima in complex mathematical landscapes.

Performance profiles for nonconvex MINLP instances illustrating the effectiveness of Global Outer-Approximation (GOA) with domain reduction.

Strategic Insights

  • Initialization as a Catalyst: The quality of the initial linear approximations dictates the solver's trajectory. Investing in a "smart" start through domain reduction yields substantial long-term time savings.
  • Efficiency in Simplicity: While convexification cuts are essential for the MILP master problem to find viable integer candidates, their inclusion in NLP subproblems is redundant and increases model complexity, slowing down the solver.
  • Single-Tree Advantage: The single-tree (LP/NLP-B&B) approach generally derived greater benefit from these techniques than the iterative multi-tree OA method.

Conclusion and Future Work

While the proposed convexification-based method offers significant improvements, it introduces overhead that may be counterproductive for very simple problems solvable in under a second. Future research will explore dynamic application of these techniques at every node of the search tree (branch-and-reduce) and aim to reduce dependency on external proprietary solvers for domain reduction, enhancing the accessibility of high-performance MINLP solving in open-source environments.

Summary updated

BibTeX
@inproceedings{peng2024convexication,
  author = {Zedong Peng and Kaiyu Cao and Kevin C. Furman and Can Li and Ignacio E. Grossmann and David E. Bernal Neira},
  title = {{A Convexication-based Outer-approximation Method for Convex and Nonconvex MINLP}},
  booktitle = {Computer-aided},
  year = {2024},
  doi = {10.1016/b978-0-443-28824-1.50536-6},
}
Figure