(676c) Learning Parametric Valid Inequalities for Mixed-Integer Linear Optimization

Efficient and safe process operations require decision making in real time. Many online decision-making frameworks involve solving discrete optimization problems, many of which present themselves as mixed-integer linear programs (MILPs). However, often the computational complexity of these MILPs presents a major challenge such that the long solution times render them ineffective in time-critical applications. To tackle this challenge, we previously proposed a data-driven surrogate modeling approach, where surrogate models for the MILPs were trained offline in a decision-focused fashion [1]. These surrogate models take the form of linear programs (LPs) and can be solved much more efficiently online. The corresponding learning problem is formulated as a large-scale bilevel program, which we solve using a penalty-based block coordinate descent algorithm [2]. While these LP surrogate models prove to be very efficient in providing near-optimal solutions, they are not guaranteed to preserve the true optimal solutions or to even directly predict feasible solutions.

In this work, we build upon our previous work and propose a method for learning effective valid inequalities offline. This is inspired by the cutting-plane method commonly used to solve MILPs, where adding valid inequalities (or cuts) results in tighter MILP formulations [3,4]. In state-of-the-art MILP solvers, these cuts are added “on the fly” and need to be generated from scratch for every new instance. In contrast, the learned inequalities in our proposed framework are parametric in the input parameters such that they get automatically updated with every new instance. The resulting tighter MILP formulation can then be employed online where it is expected to solve more efficiently while still obtaining the same optimal solution as the original MILP.

In the proposed framework, we first generate data by solving several instances of the original MILP offline, which gives us the true optimal solutions for different model inputs. We then apply an algorithm consisting of a master and a subproblem. The master problem employs the previously developed decision-focused surrogate modeling approach to learn a set of parametric cuts offline. Then the subproblem tries to select an integer-feasible point for which the violation w.r.t these cuts is maximized. These violated points are then added to our master problem that is solved to generate updated cuts that are now valid for the previously violated points. This is done iteratively until no more integer-feasible point can be found that violates any of the cuts, at which point the learned cuts are proven to be valid inequalities. Results from our computational case study show that the presence of such learned valid inequalities allows the MILPs to be solved exactly much more efficiently.

References

[1] S. Dixit, R. Gupta and Q. Zhang (2023). Decision-focused surrogate modeling for mixed-integer optimization. AIChE Annual Meeting.

[2] R. Gupta and Q. Zhang (2023). Efficient learning of decision-making models : A penalty block coordinate descent algorithm for data-driven inverse optimization. Computers and Chemical Engineering, 170, 108123.

[3] A. Fügenschuh and A. Martin (2005). Computational integer programming and cutting planes. Handbooks in Operations Research and Management Science, 12, 69-121.

[4] J. H. Owen and S. Mehrotra (2001). A disjunctive cutting plane procedure for general mixed-integer linear programs. Mathematical Programming, 89, 437-448.