nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Improving the Filtering of Branch-and-Bound MDD Solver

verfasst von : Xavier Gillard, Vianney Coppé, Pierre Schaus, André Augusto Cire

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDD). It adopts the branch-and-bound framework proposed by Bergman et al. in 2016 to solve dynamic programs to optimality. In particular, our paper presents and evaluates the effectiveness of the local-bound (LocB) and rough upper-bound pruning (RUB). LocB is a new and effective rule that leverages the approximate MDD structure to avoid the exploration of non-interesting nodes. RUB is a rule to reduce the search space during the development of bounded-width-MDDs. The experimental study we conducted on the Maximum Independent Set Problem (MISP), Maximum Cut Problem (MCP), Maximum 2 Satisfiability (MAX2SAT) and the Traveling Salesman Problem with Time Windows (TSPTW) shows evidence indicating that rough-upper-bound and local-bound pruning have a high impact on optimization solvers based on branch-and-bound with MDDs. In particular, it shows that RUB delivers excellent results but requires some effort when defining the model. Also, it shows that LocB provides a significant improvement automatically; without necessitating any user-supplied information. Finally, it also shows that rough-upper-bound and local-bound pruning are not mutually exclusive, and their combined benefit supersedes the individual benefit of using each technique.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Two Deadline Reduction Algorithms for Scheduling Dependent Tasks on Parallel Processors

Nächstes Kapitel On the Usefulness of Linear Modular Arithmetic in Constraint Programming

https://github.com/xgillard/ddo.

An incremental refinement a.k.a. construction by separation procedure is detailed in [11, pp. 51–52] but we will not cover it here for the sake of conciseness.

Consequently, it also suffers from a potentially exponential time requirement in the worst case. Indeed, time is constant in the final number of nodes (unless the transition functions themselves are exponential in the input).

The very definition of these operators is problem-specific. However, [22] formally defines the conditions that are necessary to correctness.

https://github.com/xgillard/ddo.

Available online at: http://hdl.handle.net/2078.1/245322.

Andersen, H.R., Hadzic, T., Hooker, J.N., Tiedemann, P.: A constraint store based on multivalued decision diagrams. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 118–132. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_11CrossRef

Ascheuer, N.: Hamiltonian path problems in the on-line optimization of flexible manufacturing systems (1996)

Bellman, R.: The theory of dynamic programming. Bull. Am. Math. Soc. 60(6), 503–515 (1954). https://projecteuclid.org:443/euclid.bams/1183519147

Bergman, D., Cire, A.A.: Multiobjective optimization by decision diagrams. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 86–95. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44953-1_6CrossRef

Bergman, D., Cire, A.A.: Theoretical insights and algorithmic tools for decision diagram-based optimization. Constraints 21(4), 533–556 (2016). https://doi.org/10.1007/s10601-016-9239-9

Bergman, D., Cire, A.A.: On finding the optimal BDD relaxation. In: Salvagnin, D., Lombardi, M. (eds.) CPAIOR 2017. LNCS, vol. 10335, pp. 41–50. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59776-8_4CrossRef

Bergman, D., Cire, A.A., van Hoeve, W.J., Hooker, J.N.: Optimization bounds from binary decision diagrams. INFORMS J. Comput. 26(2), 253–268 (2014). https://doi.org/10.1287/ijoc.2013.0561

Bergman, D., Cire, A.A., van Hoeve, W.J., Hooker, J.N.: Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1), 47–66 (2016). https://doi.org/10.1287/ijoc.2015.0648

Bergman, D., Cire, A.A., Sabharwal, A., Samulowitz, H., Saraswat, V., van Hoeve, W.J.: Parallel combinatorial optimization with decision diagrams. In: International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems, pp. 351–367 (2014)

10.

Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: \(10^{20}\) states and beyond. Inf. Comput. 98(2), 142–170 (1992). https://doi.org/10.1016/0890-5401(92)90017-A

11.

Cire, A.A.: Decision diagrams for optimization. Ph.D. thesis, Carnegie Mellon University Tepper School of Business (2014)

12.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)

13.

Davarnia, D., van Hoeve, W.J.: Outer approximation for integer nonlinear programs via decision diagrams (2018)

14.

Dumas, Y., Desrosiers, J., Gelinas, E., Solomon, M.M.: An optimal algorithm for the traveling salesman problem with time windows. Oper. Res. 43(2), 367–371 (1995)MathSciNetCrossRef

15.

Erdös, P., Rényi, A.: On random graphs i. Publicationes Mathematicae Debrecen 6, 290 (1959)MathSciNetMATH

16.

Gendreau, M., Hertz, A., Laporte, G., Stan, M.: A generalized insertion heuristic for the traveling salesman problem with time windows. Oper. Res. 46(3), 330–335 (1998)CrossRef

17.

Gillard, X., Schaus, P., Coppé, V.: Ddo, a generic and efficient framework for MDD-based optimization. Accepted at the International Joint Conference on Artificial Intelligence (IJCAI-20); DEMO track (2020)

18.

Gonzalez, J.E., Cire, A.A., Lodi, A., Rousseau, L.M.: Integrated integer programming and decision diagram search tree with an application to the maximum independent set problem. Constraints 1–24 (2020)

19.

Hadžić, T., Hooker, J., Tiedemann, P.: Propagating separable equalities in an MDD store. In: CPAIOR, pp. 318–322 (2008)

20.

Hoda, S., van Hoeve, W.-J., Hooker, J.N.: A systematic approach to MDD-based constraint programming. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 266–280. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15396-9_23CrossRef

21.

Hooker, J.N.: Decision diagrams and dynamic programming. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 94–110. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38171-3_7CrossRef

22.

Hooker, J.N.: Job sequencing bounds from decision diagrams. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 565–578. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66158-2_36CrossRef

23.

Hooker, J.N.: Improved job sequencing bounds from decision diagrams. In: Schiex, T., de Givry, S. (eds.) CP 2019. LNCS, vol. 11802, pp. 268–283. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30048-7_16CrossRef

24.

Hooker, J.: Discrete global optimization with binary decision diagrams. In: GICOLAG 2006 (2006)

25.

Horn, M., M̃aschler, J., R̃aidl, G.R., R̃önnberg, E.: A*-based construction of decision diagrams for a prize-collecting scheduling problem. Comput. Oper. Res. 126, 105125 (2021). https://doi.org/10.1016/j.cor.2020.105125, http://www.sciencedirect.com/science/article/pii/S0305054820302422

26.

Langevin, A., Desrochers, M., Desrosiers, J., Gélinas, S., Soumis, F.: A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks 23(7), 631–640 (1993)MathSciNetCrossRef

27.

López-Ibáñez, M., Blum, C.: Benchmark instances for the travelling salesman problem with time windows. Online (2020). http://lopez-ibanez.eu/tsptw-instances

28.

Ohlmann, J.W., Thomas, B.W.: A compressed-annealing heuristic for the traveling salesman problem with time windows. INFORMS J. Comput. 19(1), 80–90 (2007)MathSciNetCrossRef

29.

Pesant, G., Gendreau, M., Potvin, J.Y., Rousseau, J.M.: An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transp. Sci. 32(1), 12–29 (1998)CrossRef

30.

Potvin, J.Y., Bengio, S.: The vehicle routing problem with time windows part ii: genetic search. INFORMS J. Comput. 8(2), 165–172 (1996)CrossRef

31.

Tjandraatmadja, C.: Decision diagram relaxations for integer programming. Ph.D. thesis, Carnegie Mellon University Tepper School of Business (2018)

32.

Tjandraatmadja, C., van Hoeve, W.J.: Target cuts from relaxed decision diagrams. INFORMS J. Comput. 31(2), 285–301 (2019). https://doi.org/10.1287/ijoc.2018.0830

Titel: Improving the Filtering of Branch-and-Bound MDD Solver
verfasst von: Xavier Gillard
Vianney Coppé
Pierre Schaus
André Augusto Cire
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-78229-0

Electronic ISBN: 978-3-030-78230-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78230-6_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner