A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910992822173696 |
|---|---|
| author | Pacheco, Bruno Machado Antunes, Pedro Marcolin Camponogara, Eduardo Seman, Laio Oriel Rosa, Vinícius Ramos Vieira, Bruno Ferreira Longhi, Cesar |
| author_facet | Pacheco, Bruno Machado Antunes, Pedro Marcolin Camponogara, Eduardo Seman, Laio Oriel Rosa, Vinícius Ramos Vieira, Bruno Ferreira Longhi, Cesar |
| contents | This paper introduces a novel algorithm for Mixed-Integer Nonlinear Programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objective or constraints contain black-box functions only known at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the multilinear constraints resulting from the multilinear interpolations used to approximate the true functions. Supported by the fact that our proposed relaxation defines the convex hull of the original problem, we propose a novel algorithm that iteratively solves the MILP relaxation and refines the solution space through variable fixing and exclusion strategies. This approach ensures convergence to an optimal solution, which we demonstrate, while maintaining computational efficiency. We apply the proposed algorithm to a real-world offshore oil production optimization problem. In comparison to the Gurobi solver, our algorithm was able to find the optimal solution at least four times faster, and to consistently provide better incumbents under limited time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_21249 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations Pacheco, Bruno Machado Antunes, Pedro Marcolin Camponogara, Eduardo Seman, Laio Oriel Rosa, Vinícius Ramos Vieira, Bruno Ferreira Longhi, Cesar Optimization and Control This paper introduces a novel algorithm for Mixed-Integer Nonlinear Programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objective or constraints contain black-box functions only known at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the multilinear constraints resulting from the multilinear interpolations used to approximate the true functions. Supported by the fact that our proposed relaxation defines the convex hull of the original problem, we propose a novel algorithm that iteratively solves the MILP relaxation and refines the solution space through variable fixing and exclusion strategies. This approach ensures convergence to an optimal solution, which we demonstrate, while maintaining computational efficiency. We apply the proposed algorithm to a real-world offshore oil production optimization problem. In comparison to the Gurobi solver, our algorithm was able to find the optimal solution at least four times faster, and to consistently provide better incumbents under limited time. |
| title | A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2502.21249 |