# Exact solution of network flow models with strong relaxations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2021.

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

- [Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem](https://mlsanity.com/paper/2310.04471/) (2023)

## Abstract (arXiv)

We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig-Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and packing problems from the literature. The efficiency of the framework is proved by extensive computational experiments, in which a significant number of open instances could be solved to proven optimality for the first time.