Improving Variable Orderings of Approximate Decision Diagrams Using Reinforcement Learning

References

• Albert R, Barabási AL (2002) Statistical mechanics of complex networks. Rev. Modern Phys. 74(1):47.Crossref, Google Scholar
• Andersen HR, Hadzic T, Hooker JN, Tiedemann P (2007) A constraint store based on multivalued decision diagrams. Internat. Conf. Principles Practice Constraint Programming (Springer), 118–132.Google Scholar
• Bello I, Pham H, Le QV, Norouzi M, Bengio S (2016) Neural combinatorial optimization with reinforcement learning. Preprint, submitted November 29, https://arxiv.org/abs/1611.09940.Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• Bergman D, Cire AA (2018) Discrete nonlinear optimization by state-space decompositions. Management Sci. 64(10):4700–4720.Link, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2012) Variable ordering for the application of BDDs to the maximum independent set problem. Internat. Conf. Integration Artificial Intelligence (AI) Oper. Res. (OR) Techniques Constraint Programming (Springer), 34–49.Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2013) Optimization bounds from binary decision diagrams. INFORMS J. Comput. 26(2):253–268.Link, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker J (2016a) Decision Diagrams for Optimization (Springer).Crossref, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2016b) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47–66.Link, Google Scholar
• Bergman D, van Hoeve WJ, Hooker JN (2011) Manipulating MDD relaxations for combinatorial optimization. Achterberg T, Beck JC, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems 20–35.Crossref, Google Scholar
• Berthold T (2006) Primal heuristics for mixed integer programs. Doctoral dissertation, Zuse Institute Berlin (ZIB).Google Scholar
• Bryant RE (1986) Graph-based algorithms for Boolean function manipulation. IEEE Transactions Comput. 100(8):677–691.Crossref, Google Scholar
• Cappart Q, Chételat D, Khalil EB, Lodi A, Morris C, Veličković P(2021a) Combinatorial optimization and reasoning with graph neural networks. Zhou ZH, ed. Proc. Thirtieth Internat. Joint Conf. Artificial Intelligence, IJCAI-21 (International Joint Conferences on Artificial Intelligence Organization), 4348–4355.Google Scholar
• Cappart Q, Goutierre E, Bergman D, Rousseau LM (2019) Improving optimization bounds using machine learning: Decision diagrams meet deep reinforcement learning. Proc. Conf. AAAI Artificial Intelligence 33(01):1443–1451.Crossref, Google Scholar
• Cappart Q, Moisan T, Rousseau LM, Prémont-Schwarz I, Cire AA (2021b) Combining reinforcement learning and constraint programming for combinatorial optimization. Proc. Conf. AAAI Artificial Intelligence 35:3677–3687.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164.Crossref, Google Scholar
• Dai H, Dai B, Song L (2016) Discriminative embeddings of latent variable models for structured data. Internat. Conf. Machine Learning, 2702–2711.Google Scholar
• Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau LM(2018) Learning heuristics for the TSP by policy gradient. Internat. Conf. Integration Constraint Programming, Artificial Intelligence Oper. Res. (Springer), 170–181.Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Farràs O, Kaced T, Martín S, Padró C (2018) Improving the linear programming technique in the search for lower bounds in secret sharing. Annual Internat. Conf. Theory Appl. Cryptographic Techniques (Springer), 597–621.Google Scholar
• Gamrath G, Koch T, Martin A, Miltenberger M, Weninger D (2015) Progress in presolving for mixed integer programming. Math. Programming Comput. 7(4):367–398.Crossref, Google Scholar
• Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Adv. Neural Inform. Process. Systems 32.Google Scholar
• Grötschel M, Lovasz L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization (Springer).Crossref, Google Scholar
• Hadzic T, Hooker J (2006) Postoptimality analysis for integer programming using binary decision diagrams. GICOLAG Workshop.Google Scholar
• Hagberg A, Swart PS, Chult D (2008) Exploring Network Structure, Dynamics, and Function Using NetworkX. Technical report, Los Alamos National Laboratory, Los Alamos, NM.Google Scholar
• He H, Daume H III, Eisner JM (2014) Learning to search in branch and bound algorithms. Adv. Neural Inform. Process. Systems 27:3293–3301.Google Scholar
• Henderson P, Islam R, Bachman P, Pineau J, Precup D, Meger D(2018) Deep reinforcement learning that matters. Proc. AAAI Conf. Artificial Intelligence, volume 32.Google Scholar
• Hutter F, Hoos HH, Leyton-Brown K (2011) Sequential model-based optimization for general algorithm configuration. Internat. Conf. Learning Intelligent Optimization (Springer), 507–523.Google Scholar
• Khalil E, Dai H, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. Adv. Neural Inform. Process. Systems 30:6351–6361.Google Scholar
• Kingma DP, Ba J (2014) Adam: A method for stochastic optimization. Preprint, submitted December 22, https://arxiv.org/abs/1412.6980.Google Scholar
• Kool W, van Hoof H, Welling M (2019) Attention, learn to solve routing problems! Internat. Conf. Learning Representations.Google Scholar
• LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436.Crossref, Google Scholar
• Lee CY (1959) Representation of switching circuits by binary-decision programs. Bell Syst. Tech. J. 38(4):985–999.Crossref, Google Scholar
• Lin LJ (1992) Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning 8(3–4):293–321.Crossref, Google Scholar
• Lodi A, Zarpellon G (2017) On learning and branching: a survey. TOP. 25(2):207–236.Crossref, Google Scholar
• Masters D, Luschi C (2018) Revisiting small batch training for deep neural networks. Preprint, submitted April 20, https://arxiv.org/abs/1804.07612.Google Scholar
• Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, et al. (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529.Crossref, Google Scholar
• Parjadis A, Cappart Q, Rousseau LM, Bergman D (2021) Improving branch-and-bound using decision diagrams and reinforcement learning. Internat. Conf. Integration Constraint Programming Artificial Intelligence Oper. Res. (Springer), 446–455.Google Scholar
• Riedmiller M (2005) Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method. Eur. Conf. Machine Learning (Springer), 317–328.Google Scholar
• Rumelhart DE, Hinton GE, Williams RJ (1986) Learning representations by back-propagating errors. Nature 323(6088):533.Crossref, Google Scholar
• Sadykov R, Vanderbeck F, Pessoa A, Tahiri I, Uchoa E (2019) Primal heuristics for branch and price: The assets of diving methods. INFORMS J. Comput. 31(2):251–267.Link, Google Scholar
• Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, Monfardini G (2008) The graph neural network model. IEEE Trans. Neural Network 20(1):61–80.Crossref, Google Scholar
• Schaul T, Quan J, Antonoglou I, Silver D (2015) Prioritized experience replay. Preprint, submitted November 18, https://arxiv.org/abs/1511.05952.Google Scholar
• Silver D, Huang A, Maddison CJ, Guez A, Sifre L, Van Den Driessche G, Schrittwieser J, et al. (2016) Mastering the game of Go with deep neural networks and tree search. Nature 529(7587):484–489.Crossref, Google Scholar
• Silver D, Hubert T, Schrittwieser J, Antonoglou I, Lai M, Guez A, Lanctot M, et al. (2017) Mastering chess and shogi by self-play with a general reinforcement learning algorithm. Preprint, submitted December 5, https://arxiv.org/abs/1712.01815.Google Scholar
• Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction (MIT Press).Google Scholar
• Tang Y, Agrawal S, Faenza Y (2020) Reinforcement learning for integer programming: Learning to cut. Internat. Conf. Machine Learning (PMLR), 9367–9376.Google Scholar
• Van Hasselt H, Guez A, Silver D (2016) Deep reinforcement learning with double q-learning. Proc. AAAI Conf. Artificial Intelligence, vol. 30.Google Scholar
• Verhaeghe H, Lecoutre C, Schaus P (2018) Compact-mdd: efficiently filtering (s) mdd constraints with reversible sparse bit-sets. Proc. 27th Internat. Joint Conf. Artificial Intelligence (AAAI Press), 1383–1389.Google Scholar
• Watkins CJ, Dayan P (1992) Q-learning. Machine Learning 8(3–4):279–292.Crossref, Google Scholar