We study the value function of an integer program (IP) by characterizing how its optimal value changes as the right-hand side varies. We show that the IP value function can be approximated to any desired degree of accuracy using machine learning (ML) techniques. Since an IP value function is a Chvátal-Gomory (CG) function, we first propose a neural network (NN) architecture as a universal approximator, which requires an explicit construction of the IP value function. We then derive a connection between CG cuts and the IP value function, which resulted in another NN architecture that does not require any information about the CG operations of the IP value function. Our novel NN architecture draws the relation between the weights of the NN and CG multipliers and inspired methods to derive a valid bound of the IP value function.
Article
View Representing Integer Program Value Function with Neural Networks