2022年7月27日 –, JuMP
We present Scylla, a primal heuristic for mixed-integer optimization. It uses matrix-free approximate LP solving with specialized termination criteria and parallelized fix-and-propagate procedures blended with feasibility pump-like objective updates. Besides the presentation of the method and results, we will go over lessons learned on experimentation and implementation tricks including overhead reduction, asynchronous programming, and interfacing with natively-compiled libraries.
The talk will present our work on Scylla in two aspects. The first will be the presentation of the method and different components and ideas they link to, from feasibility pump to primal-dual hybrid gradients for linear optimization and fix-and-propagate procedures. The second aspect of the talk will include lessons learned on asynchronous programming using the Task-Channel model, working with and interfacing native libraries or time management for time-constrained experimental runs.
Mathieu Besançon is a researcher at the Zuse Institute Berlin, in the AI in Society, Science, and Technology department, associated with the MODAL-SynLab project and a member of the MATH+ Berlin Mathematics Research Center.
His research interests span solution methods and software in MI(N)LP and convex optimization and in particular the SCIP framework and Frank-Wolfe related approaches.