A matrix-free fix-propagate-and-project heuristic for MILPs

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.