Two-Stage Predict+Optimize for Mixed Integer Linear Programs with Unknown Parameters in Constraints
This work addresses a key limitation in Predict+Optimize for practitioners dealing with mixed integer linear programs with unknown constraints, though it appears incremental by building on prior adaptations.
The paper tackles the problem of constrained optimization with unknown parameters in constraints by proposing a new Two-Stage Predict+Optimize framework, which simplifies and generalizes prior methods to handle all mixed integer linear programs, demonstrating superior prediction performance over existing approaches.
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.