Webinar link
Webinar ID: 953 4267 1251
Passcode: 805438

We present an iterative method for the solution of a class of non-linear mixed-integer programs to arbitrary numerical precision. At every iteration, our method solves a piece-wise linear approximation of the problem. If the gap -- computed as the (absolute or relative) difference between the evaluation of the original cost function and that of the approximation in the incumbent -- is deemed as not satisfactory, the approximation is locally tightened and the process repeated. By keeping the scope of the update 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 provide a formal proof of the convergence of our method, and assess its efficiency for approximating the non-linear variants of three problems: the uncapacitated facility location problem, the multi-commodity network design problem, and the transportation problem. Our results indicate that, as the desired precision becomes smaller, our approach can lead to significant gains in computing times, often being orders of magnitude faster than a baseline method, and scales to approximate larger problems.