Presentation Information
[5H2-OS-18a-02]Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions
〇Akira Kitaoka1 (1. NEC Corporation)
Keywords:
inverse optimization,mixed-integer linear program,mathematical optimization,combinatorial optimization
In mixed-integer linear programming, data-driven inverse optimization seeks to infer objective functions and constraints from observed solutions, thereby facilitating the construction of appropriate mathematical models in application domains such as power systems and scheduling. However, to the best of our knowledge, no existing approach is capable of learning both the objective function and the constraints. In this paper, we propose a two-stage method for a class of problems in which the objective is expressed as a linear combination of prescribed functions and the constraints are characterized by functional forms with threshold parameters. The proposed method first identifies the constraints and subsequently estimates the objective function. On the theoretical side, we establish that the method solves the inverse optimization problem with finite datasets, and we develop a statistical learning framework based on pseudometric spaces and sub-Gaussian distributions, yielding learning guarantees for inverse optimization. On the empirical side, we demonstrate the practical effectiveness of the proposed method on scheduling instances formulated as integer linear programs with up to 100 decision variables, a scale representative of real-world settings.