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

07/27/2022, 7:30 PM8:00 PM UTC
JuMP

Abstract:

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.

Description:

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.

Platinum sponsors

Julia ComputingRelational AIJulius Technology

Gold sponsors

IntelAWS

Silver sponsors

Invenia LabsBeacon BiosignalsMetalenzASMLG-ResearchConningPumas AIQuEra Computing Inc.Jeffrey Sarnoff

Media partners

Packt PublicationGather TownVercel

Community partners

Data UmbrellaWiMLDS

Fiscal Sponsor

NumFOCUS