<p>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 known only at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the multilinear interpolants, which originally require an MINLP formulation. Supported by the fact that our proposed relaxation is tight, we present a novel algorithm that iteratively solves the Mixed-Integer Linear Programming (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 and compare it against the global solvers SCIP, BARON, and Gurobi. RFE was able to solve 20% more instances to optimality within one hour than any of the standalone solvers. In particular, when compared to the best standalone solver, Gurobi, our algorithm was either significantly faster or provided smaller gaps on the instances that were solved by both or neither approach, respectively.</p>