This paper introduces a novel algorithm for Mixed-Integer Nonlinear Programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objectives 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 interpolants, which require an MINLP formulation. Supported by the fact that our proposed relaxation is as tight as possible, 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 (Relax-Fix-and-Exclude, RFE) to a real-world offshore oil production optimization problem. Compared to the Gurobi solver, RFE was able to solve to optimality 20% more instances within one hour. Furthermore, on medium and large instances that both RFE and Gurobi solved to optimality, our algorithm took, on average, 52% less time than Gurobi to converge, while on all instances that neither solved, RFE always achieved a lower primal-dual gap, on average 91% smaller.