# Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Benchmarking TPU, GPU, and CPU Platforms for Deep Learning](https://mlsanity.com/paper/1907.10701/) (2019)
- [JuMP: A Modeling Language for Mathematical Optimization](https://mlsanity.com/paper/1508.01982/) (2015)
- [SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning](https://mlsanity.com/paper/2102.09193/) (2021)
- [Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art](https://mlsanity.com/paper/2008.12646/) (2020)

## Abstract (arXiv)

Current state-of-the-art solvers for mixed-integer programming (MIP) problems are designed to perform well on a wide range of problems. However, for many real-world use cases, problem instances come from a narrow distribution. This has motivated the development of specialized methods that can exploit the information in historical datasets to guide the design of heuristics. Recent works have shown that machine learning (ML) can be integrated with an MIP solver to inject domain knowledge and efficiently close the optimality gap. This hybridization is usually done with deep learning (DL), which requires a large dataset and extensive hyperparameter tuning to perform well. This paper proposes an online heuristic that uses the notion of entropy to efficiently build a model with minimal training data and tuning. We test our method on the locomotive assignment problem (LAP), a recurring real-world problem that is challenging to solve at scale. Experimental results show a speed up of an order of magnitude compared to a general purpose solver (CPLEX) with a relative gap of less than 2%. We also observe that for some instances our method can discover better solutions than CPLEX within the time limit.