# Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing

arXiv: https://arxiv.org/abs/2207.02087 · HTML: https://mlsanity.com/paper/2207.02087/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 76 references that are in the map.
- First posted on arXiv 5 Jul 2022.

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [BranchyNet: Fast Inference via Early Exiting from Deep Neural Networks](https://mlsanity.com/paper/1709.01686/) (2017)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Behavioral Cloning from Observation](https://mlsanity.com/paper/1805.01954/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Sparse and Imperceivable Adversarial Attacks](https://mlsanity.com/paper/1909.05040/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [SparseFool: a few pixels make a big difference](https://mlsanity.com/paper/1811.02248/) (2018)
- [Recent Advances in Imitation Learning from Observation](https://mlsanity.com/paper/1905.13566/) (2019)
- [Structured Adversarial Attack: Towards General Implementation and Better Interpretability](https://mlsanity.com/paper/1808.01664/) (2018)
- [Learning to Stop While Learning to Predict](https://mlsanity.com/paper/2006.05082/) (2020)
- [Feedback Networks](https://mlsanity.com/paper/1612.09508/) (2016)
- [Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks](https://mlsanity.com/paper/1706.07450/) (2017)
- [Bregman Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1306.3203/) (2013)
- [Differentiable Linearized ADMM](https://mlsanity.com/paper/1905.06179/) (2019)
- [Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis](https://mlsanity.com/paper/1705.02502/) (2017)
- [Bethe-ADMM for Tree Decomposition based Parallel MAP Inference](https://mlsanity.com/paper/1309.6829/) (2013)

## Built on by (most cited first, 3 of 3)

- [Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning](https://mlsanity.com/paper/2210.17178/) (2022)
- [Deep-learning-based Early Fixing for Gas-lifted Oil Production Optimization: Supervised and Weakly-supervised Approaches](https://mlsanity.com/paper/2309.00197/) (2023)
- [PersonaX: Multimodal Datasets with LLM-Inferred Behavior Traits](https://mlsanity.com/paper/2509.11362/) (2025)

## Abstract (arXiv)

Integer programming (IP) is an important and challenging problem. Approximate methods have shown promising performance on both effectiveness and efficiency for solving the IP problem. However, we observed that a large fraction of variables solved by some iterative approximate methods fluctuate around their final converged discrete states in very long iterations. Inspired by this observation, we aim to accelerate these approximate methods by early fixing these fluctuated variables to their converged states while not significantly harming the solution accuracy. To this end, we propose an early fixing framework along with the approximate method. We formulate the whole early fixing process as a Markov decision process, and train it using imitation learning. A policy network will evaluate the posterior probability of each free variable concerning its discrete candidate states in each block of iterations. Specifically, we adopt the powerful multi-headed attention mechanism in the policy network. Extensive experiments on our proposed early fixing framework are conducted to three different IP applications: constrained linear programming, MRF energy minimization and sparse adversarial attack. The former one is linear IP problem, while the latter two are quadratic IP problems. We extend the problem scale from regular size to significantly large size. The extensive experiments reveal the competitiveness of our early fixing framework: the runtime speeds up significantly, while the solution quality does not degrade much, even in some cases it is available to obtain better solutions. Our proposed early fixing framework can be regarded as an acceleration extension of ADMM methods for solving integer programming. The source codes are available at urlhttps://github.com/SCLBD/Accelerated-Lpbox-ADMM.