Two-Stage Predict+Optimize for Mixed Integer Linear Programs with Unknown Parameters in Constraints
Preprint
Abstract
Consider the setting of constrained optimization, with some parameters unknown at solving time and requiring prediction from relevant features. Predict+Optimize is a recent framework for end-to-end training supervised learning models for such predictions, incorporating information about the optimization problem in the training process in order to yield better predictions in terms of the quality of the predicted solution under the true parameters. Almost all prior works have focused on the special case where the unknowns appear only in the optimization objective and not the constraints. Hu et al.~proposed the first adaptation of Predict+Optimize to handle unknowns appearing in constraints, but the framework has somewhat ad-hoc elements, and they provided a training algorithm only for covering and packing linear programs. In this work, we give a new \emph{simpler} and \emph{more powerful} framework called \emph{Two-Stage Predict+Optimize}, which we believe should be the canonical framework for the Predict+Optimize setting. We also give a training algorithm usable for all mixed integer linear programs, vastly generalizing the applicability of the framework. Experimental results demonstrate the superior prediction performance of our training framework over all classical and state-of-the-art methods.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Contrastive Losses and Solution Caching for Predict-and-Optimize2021
- Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problemJournal of Scheduling, 2009
- Joining of titanium/stainless steel by explosive welding and effect on interfaceJournal of Materials Processing Technology, 2005