Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions
This addresses a gap in data-driven inverse optimization for constructing mathematical models in fields like power systems and scheduling, though it is incremental as it builds on existing inverse optimization methods.
The paper tackles the problem of learning both objective functions and constraints in mixed-integer linear programming from observed data, proposing a two-stage method that first learns constraints and then the objective function, and demonstrates applicability on scheduling problems with up to 100 decision variables.
In mixed-integer linear programming, data-driven inverse optimization that learns the objective function and the constraints from observed data plays an important role in constructing appropriate mathematical models for various fields, including power systems and scheduling. However, to the best of our knowledge, there is no known method for learning both the objective functions and the constraints. In this paper, we propose a two-stage method for a class of problems where the objective function is expressed as a linear combination of functions and the constraints are represented by functions and thresholds. Specifically, our method first learns the constraints and then learns the objective function. On the theoretical side, we show the proposed method can solve inverse optimization problems in finite dataset, develop statistical learning theory in pseudometric spaces and sub-Gaussian distributions, and construct a statistical learning for inverse optimization. On the experimental side, we demonstrate that our method is practically applicable for scheduling problems formulated as integer linear programmings with up to 100 decision variables, which are typical in real-world settings.