Branch & Learn for Recursively and Iteratively Solvable Problems in Predict+Optimize
This addresses the Predict+Optimize problem for domains like logistics or scheduling where parameters are uncertain, offering a methodical approach but is incremental in building on recursive algorithms.
The paper tackles optimization problems with unknown parameters by proposing the Branch & Learn framework, which constructs learning algorithms from recursive or iterative solvers, and shows better performance over existing methods in experiments.
This paper proposes Branch & Learn, a framework for Predict+Optimize to tackle optimization problems containing parameters that are unknown at the time of solving. Given an optimization problem solvable by a recursive algorithm satisfying simple conditions, we show how a corresponding learning algorithm can be constructed directly and methodically from the recursive algorithm. Our framework applies also to iterative algorithms by viewing them as a degenerate form of recursion. Extensive experimentation shows better performance for our proposal over classical and state-of-the-art approaches.