Augmented IRUP (AI

Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances

Announce Type: replace Abstract: The Cutting Stock Problem (CSP) and Bin Packing Problem (BPP) are classical combinatorial optimization problems extensively studied since the 1960s. State-of-the-art exact algorithms are based on set-cover and arc-flow models whose linear relaxation, rounded up, matches the integer optimum for most benchmark instances, a condition known as the Integer Round-up Property (IRUP). In 2016, Delorme et al. showed that all existing instances could be solved within...