Abstract
Finding tight bounds on the optimal solution is a critical element ofpractical solution methods for discrete optimization problems. In the lastdecade, decision diagrams (DDs) have brought a new perspective on obtainingupper and lower bounds that can be significantly better than classical boundingmechanisms, such as linear relaxations. It is well known that the quality ofthe bound achieved through this flexible bounding method is highly reliant onthe ordering of variables chosen for building the diagram, and finding anordering that optimizes standard metrics, or even improving one, is an NP-hardproblem. In this paper, we propose an innovative and generic approach based ondeep reinforcement learning for obtaining an ordering for tightening the boundsobtained with relaxed and restricted DDs. We apply the approach to both theMaximum Independent Set Problem and the Maximum Cut Problem. Experimentalresults on synthetic instances show that the deep reinforcement learningapproach, by achieving tighter objective function bounds, generally outperformsordering methods commonly used in the literature when the distribution ofinstances is known. To the best knowledge of the authors, this is the firstpaper to apply machine learning to directly improve relaxation bounds obtainedby general-purpose bounding mechanisms for combinatorial optimization problems.