Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization

2023/07/07 by Mexi, Gioni, Besançon, Mathieu, Bolusani, Suresh +3 · 2 citations
#FOS: Computer and information sciences #FOS: Mathematics #Mathematical Software (cs.MS) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2307.03466

Abstract

We introduce Scylla, a primal heuristic for mixed-integer optimization problems. It exploits approximate solves of the Linear Programming relaxations through the matrix-free Primal-Dual Hybrid Gradient algorithm with specialized termination criteria, and derives integer-feasible solutions via fix-and-propagate procedures and feasibility-pump-like updates to the objective function. Computational experiments show that the method is particularly suited to instances with hard linear relaxations.

Cited by

• GPU-Accelerated Primal Heuristics for Mixed Integer Programming
• Successive Fixing for Large-Scale SCUC Using First-Order Methods

Related

• The Differentiable Feasibility Pump
• Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization
• The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
• Combining Gradient Information and Primitive Directions for High-Performance Mixed-Integer Optimization
• Mixed-integer Nonlinear Optimization: A Hatchery for Modern Mathematics