Abstract:

We consider the problem of minimizing the sum of a series of univariate (possibly non-convex) functions on a polyhedral domain. We introduce an iterative method with optimality guarantees to approximate this problem to an arbitrary numerical precision. It solves a series of piecewise linear approximations of the problem in a way that the tractability of the resulting MIPs is not compromised along the process. A key in its success is the reliance on precision-driven tightening mechanisms rather than domain-driven tightenings. Our method also uses a refinement algorithm known as LinA that is proven to provide a minimal-sized piecewise linear approximation for a given target precision. The convergence of the method in a finite number of iterations is assured under very mild assumptions, and no NLP nor MINLP solver/oracle is required to ever be invoked to do so. We also show that in the worst case, our method performs O(log(n)) iterations, where n is the maximum number of iterations required by other adaptive partitioning based algorithms from the literature to achieve the desired precision. By keeping the scope of the updates local, the computational burden is only slightly increased from iteration to iteration. As a consequence, our method presents very nice scalability properties and is little sensitive to the desired precision. We illustrate its efficiency in approximating the non-linear variants of three problems: the transportation problem, the capacitated facility location problem, and the multi-commodity network design problem.