Global optimization algorithm for mixed-integer nonlinear programs with trigonometric functions

Christopher Montez, Sujeevraja Sanjeevi, Kaarthik SundarJ. Glob. Optim 2025 · DOI

TL;DR

This paper introduces a novel MILP-based algorithm to solve mixed-integer nonlinear programs (MINLPs) containing trigonometric functions to global optimality. It achieves this by developing new piecewise polyhedral relaxations for these functions and integrating them into an iterative MILP framework with adaptive partitioning and refinement strategies, demonstrating significant performance improvements on a challenging path planning problem.

What Problem Does This Paper Address?

Many real-world optimization problems, particularly in fields like chemical engineering, energy systems, and robotics, are modeled as Mixed-Integer Nonlinear Programs (MINLPs). These problems involve both continuous and discrete variables, and their constraints or objectives can be nonlinear and non-convex. While solvers exist for certain classes of MINLPs, those involving periodic functions, especially trigonometric functions (like sine and cosine), pose a significant challenge. Existing solvers often struggle with the non-convexity and the specific nature of these periodic terms. This paper addresses the need for a robust and efficient algorithm that can reliably find the global optimum for MINLPs containing trigonometric functions, which are common in applications like robotics and control systems.

Methods

The core of this paper is an MILP-based iterative algorithm. At each iteration, the algorithm solves a Mixed-Integer Linear Programming (MILP) relaxation of the original MINLP to obtain a lower bound on the optimal objective value. The key innovations lie in:

  • Piecewise Polyhedral Relaxations: The authors develop novel relaxations for univariate trigonometric functions and bilinear terms. These relaxations approximate the non-convex functions with a series of linear pieces (triangles for trigonometric, tetrahedrons for bilinear).
  • Incremental Formulation: An "incremental formulation" is used to construct these relaxations, which is noted for its computational superiority.
  • Adaptive Partitioning and Refinement: The algorithm iteratively refines the partitions of the variables involved in the nonlinear terms. This involves:
  • Refinement Strategies: Methods for selecting which partitions to refine (e.g., complete refinement, k-worst refinement based on relaxation quality).
  • Refinement Schemes: Techniques for actually refining a partition (e.g., bisection, direct addition of the optimal solution, non-uniform schemes).
  • Principal Domain Reformulation: For periodic functions, the authors propose reformulating the problem to use a "principal domain" (a period-width interval) to reduce the number of binary variables and potentially tighten relaxations across multiple original sub-domains.
  • Shared Partitions: The algorithm can share partitions between multiple functions that depend on the same variable, further reducing the number of binary variables.

Datasets

The paper evaluates its proposed algorithm on a Markov-Dubins Path Planning Problem (MDPPP). This problem is formulated as an MINLP and serves as a motivating example and benchmark. The instances are generated by placing $n$ points (ranging from 2 to 8) within a 10x10 grid, with constraints on the separation of consecutive points and randomly selected initial/final heading angles.

Key Insights and Ideas

  • MILP Power for Trigonometric Functions: The paper demonstrates that by carefully constructing MILP relaxations, the power of modern MILP solvers can be effectively leveraged to tackle challenging non-convexities introduced by trigonometric functions.
  • Adaptive Refinement is Crucial: The choice of refinement strategy and scheme significantly impacts performance. Non-uniform refinement schemes (NU2 and NU3) consistently outperform simpler methods like bisection, highlighting the benefit of intelligently focusing refinement efforts.
  • Principal Domains Offer Significant Gains: Reformulating periodic functions using principal domains drastically reduces computational effort, especially for problems with wide angle ranges, by simplifying variable relationships and reducing binary variables.
  • Sharing Partitions Reduces Complexity: When multiple functions share variables, using a single partition for all of them can lead to substantial reductions in binary variables and computation time.

Key Results

The proposed MILP-based algorithm, particularly when using the principal domain reformulation and non-uniform refinement schemes (NU2 and NU3), shows significant performance improvements on the MDPPP benchmark.

  • Principal Domain Reformulation: Outperforms the original formulation across all tested refinement schemes, solving instances much faster.
  • Refinement Schemes: Non-uniform schemes (NU2, NU3) significantly outperform bisection and direct schemes. NU2 with k=50% (a specific k-worst strategy) is identified as the default configuration.
  • Comparison with Solvers: The proposed method (NU2 with k=50%) is compared against state-of-the-art solvers like Gurobi and SCIP. For small instances, the proposed method is competitive, and for larger instances where other solvers time out, it provides solutions within a reasonable time. For example, on instances where Gurobi and SCIP timed out, the proposed method solved them in seconds to minutes.

Limitations and Future Work

  • General MINLPs: While the framework is designed for trigonometric functions, the authors suggest future work to extend its effectiveness to MINLPs with other types of nonlinearities.
  • Non-Smooth Periodic Functions: The current approach relies on differentiable periodic functions. Future research could explore handling non-smooth periodic functions that cannot be well-approximated by Fourier series.
  • Choice of Principal Domain: The performance of the principal domain reformulation is sensitive to the choice of the principal domain. Further computational studies are needed to determine optimal choices for specific applications.
  • Branching Decisions: The paper touches upon how branching decisions in MILP solvers can be influenced by the principal domain reformulation, suggesting this as an area for further investigation to potentially improve computational times.

Summary updated

BibTeX
@article{montez2025global,
  author = {Christopher Montez and Sujeevraja Sanjeevi and Kaarthik Sundar},
  title = {{Global optimization algorithm for mixed-integer nonlinear programs with trigonometric functions}},
  journal = {J. Glob. Optim},
  year = {2025},
  doi = {10.1007/s10898-025-01547-9},
}
Figure