Reinforcement Learning Algorithm for Learning Shadow Variables in Combinatorial Optimization Problems

Abstract: Many real-world decision-making problems are modeled as Mixed-Integer Linear Optimization (MILO) problems, and are solved by exact tree-search-based optimization algorithms. Some knowledge, such as preferences for the solution, often exists but is not explicitly modeled. We examine incorporating such knowledge as additional constraints to potentially shorten optimization. A wise choice of "equality preferences" (i.e., preferring certain equalities between decision variables) to add as equality constraints reduces the search-tree size, resulting in a shorter optimization, but some choices might make the problem infeasible, or make the solution suboptimal. Therefore, adding such constraints requires experts to set them. We present a method for incorporating expert knowledge as additional constraints while guaranteeing optimality, and we found that this indeed shortens optimization for various instances. Furthermore, we define a new and innovative deep reinforcement learning (RL) algorithm to learn additional problem-specific constraints for MILO solvers. Specifically, our approach is to define an algorithm that learns a policy of choosing equality preferences to set as constraints, such that after training and given a new problem, the policy will choose constraints to add, for quicker optimization. The algorithm is trained using deep RL on a set of instances, by using the MILO solver's runtime as feedback. Problem data and partial constraints settings serve as states, while the choices of additional constraints serve as actions. We tested our approach, using the "Gurobi" optimizer, on the "floor-assignment" problem. The agent's performance was compared to benchmarks such as optimizing without additional constraints and optimizing while enforcing all equality preferences.