On the Approximation of Separable Nonconvex Optimization Programs to an Arbitrary Numerical Tolerance

We consider the problem of minimizing the sum of a series of univariate (possibly nonconvex) functions on a polyhedral domain. We introduce an iterative method with optimality guarantees to approximate this problem to an arbitrary numerical tolerance. At every iteration, our method replaces the objective by a piecewise linear relaxation to compute a dual bound. Because the polyhedral domain in our method remains unchanged, a primal bound is computed by evaluating the cost function on the solution provided by the relaxation. If the difference between these two values is deemed as not satisfactory, then the relaxation is locally tightened with an objective-driven refinement procedure that computes an optimal domain partitioning, and the process is repeated. By keeping the scope of the update local, the computational burden is increased only slightly from iteration to iteration. The convergence of the method is assured under very mild assumptions, and no NLP nor MINLP solver/oracle is required to ever be invoked to do so. As a consequence, our method presents very nice scalability properties and is little sensitive to the desired tolerance. We provide a formal proof of the convergence of our method and assess its efficiency in approximating the nonlinear variants of five problems: the transportation problem, the uncapacitated facility location problem, the multicommodity flow problem, the multicommodity network design problem, and the continuous knapsack problem. Our results indicate that the overall performance of our method is competitive to three state-of-the-art, mixed-integer, nonlinear solvers, often performing better. It also scales better than a naive variant of the method that avoids performing successive iterations in exchange for solving a much larger mixed-integer linear program.

History: Accepted by Alice E. Smith, Andrea Lodi/Design & Analysis of Algorithms-Discrete.

Funding: This work was supported by Fondation Mathématique Jacques Hadamard with support from EDF-Thales-Orange, and Natural Sciences and Engineering Research Council of Canada [2020-06311].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0221) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0221). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.