# Discounted Pseudocosts in MILP

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 8 of its 13 references that are in the map.
- First posted on arXiv 7 Jul 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories](https://mlsanity.com/paper/2205.14345/) (2022)
- [An Improved Reinforcement Learning Algorithm for Learning to Branch](https://mlsanity.com/paper/2201.06213/) (2022)
- [Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch](https://mlsanity.com/paper/2206.06965/) (2022)
- [Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning](https://mlsanity.com/paper/2207.13701/) (2022)
- [TreeDQN: Sample-Efficient Off-Policy Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/2306.05905/) (2023)

## Abstract (arXiv)

In this article, we introduce the concept of discounted pseudocosts, inspired by discounted total reward in reinforcement learning, and explore their application in mixed-integer linear programming (MILP). Traditional pseudocosts estimate changes in the objective function due to variable bound changes during the branch-and-bound process. By integrating reinforcement learning concepts, we propose a novel approach incorporating a forward-looking perspective into pseudocost estimation. We present the motivation behind discounted pseudocosts and discuss how they represent the anticipated reward for branching after one level of exploration in the MILP problem space. Initial experiments on MIPLIB 2017 benchmark instances demonstrate the potential of discounted pseudocosts to enhance branching strategies and accelerate the solution process for challenging MILP problems.