×

zbMATH — the first resource for mathematics

Lagrangian bounds from decision diagrams. (English) Zbl 1327.90116
Summary: Relaxed decision diagrams have recently been used in constraint programming to improve constraint propagation and optimization reasoning. In most applications, however, a decision diagram is compiled with respect to a single combinatorial structure. We propose to expand this representation by incorporating additional constraints in the decision diagram via a Lagrangian relaxation. With this generic approach we can obtain stronger bounds from the same decision diagram, while the associated cost-based filtering allows for further refining the relaxation. Experimental results on the traveling salesman problem with time windows show that the improved Lagrangian bounds can drastically reduce solution times.

MSC:
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akers, SB, Binary decision diagrams, IEEE Transactions on Computers, C-27, 509-516, (1978) · Zbl 0377.94038
[2] Andersen, H.R., Hadzic, T., Hooker, J.N., & Tiedemann, P. (2007). A constraint store based on multivalued decision diagrams. In Proceedings of the 13th international conference on Principles and practice of constraint programming (pp. 118-132). Springer-Verlag, Berlin, Heidelberg. · Zbl 1291.90091
[3] Becker, B., Behle, M., Eisenbrand, F., & Wimmer, R. (2005). BDDs in a branch and cut framework. In Nikoletseas, S. (Ed.), Experimental and efficient algorithms, proceedings of the 4th international workshop on Efficient and experimental algorithms (WEA 05). Lecture Notes in Computer Science (Vol. 3503, pp. 452-463). Springer. · Zbl 1121.90422
[4] Behle, M. (2007). Binary decision diagrams and integer programming. Ph.D. thesis, Max Planck Institute for Computer Science. · Zbl 1175.90324
[5] Benoist, T., Laburthe, F., & Rottembourg, B. (2001). Lagrange relaxation and constraint programming collaborative schemes for travelling tournament problems. In Proceedings of the 3rd international workshop on Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR).
[6] Bergman, D. (2013). New techniques for discrete optimization. Ph.D. thesis, Tepper School of Business, Carnegie mellon university. · Zbl 1291.90091
[7] Bergman, D; Cire, AA; van Hoeve, WJ, Mdd propagation for sequence constraints, Journal of Artificial Intelligence Research (JAIR), 50, 697-722, (2014) · Zbl 1366.68072
[8] Bergman, D., Cire, A.A., van Hoeve, W.J., & Hooker, J.N. (2012). Variable ordering for the application of bdds to the maximum independent set problem. In Proceedings of the 9th international conference on integration of AI and OR techniques in Constraint programming for combinatorial optimization problems (pp. 34-49). Springer-Verlag, Berlin, Heidelberg.
[9] Bergman, D; Cire, AA; van Hoeve, WJ; Hooker, JN, Optimization bounds from binary decision diagrams, INFORMS Journal on Computing, 26, 253-268, (2014) · Zbl 1356.90083
[10] Bergman, D; Cire, A; van Hoeve, WJ; Yunes, T, Bdd-based heuristics for binary optimization, Journal of Heuristics, 20, 211-234, (2014)
[11] Bergman, D., van Hoeve, W.J., & Hooker, J. (2011). Manipulating MDD relaxations for combinatorial optimization. In T. Achterberg & J. Beck (Eds.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, Lecture notes in computer science (Vol. 6697, pp. 20-35). Springer Berlin / Heidelberg. · Zbl 1302.90166
[12] Bryant, RE, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, C-35, 677-691, (1986) · Zbl 0593.94022
[13] Cire, AA; van Hoeve, WJ, Multivalued decision diagrams for sequencing problems, Operations Research, 61, 1411-1428, (2013) · Zbl 1291.90091
[14] Fisher, ML, The Lagrangian relaxation method for solving integer programming problems, Management Science, 50, 1861-1871, (2004)
[15] Fontaine, D., Michel, L., & Van Hentenryck, P. (2014). Constraint-based lagrangian relaxation. In B. O’Sullivan (Ed.), Principles and practice of constraint programming, Lecture notes in computer science (Vol. 8656, pp. 324-339). Springer International Publishing. · Zbl 0593.94022
[16] Hadzic, T., & Hooker, J. (2006). Postoptimality analysis for integer programming using binary decision diagrams. Tech. rep., Carnegie Mellon University.
[17] Hadzic, T., Hooker, J.N., O’Sullivan, B., & Tiedemann, P. (2008). Approximate compilation of constraints into multivalued decision diagrams. In Proceedings of the 14th international conference on principles and practice of constraint programming (pp. 448-462). Springer-Verlag, Berlin.
[18] Hoda, S., van Hoeve, W.J., & Hooker, J.N. (2010). A systematic approach to MDD-based constraint programming. In Proceedings of constraint programming (Vol. 6308, pp. 266-280). LNCS, Springer.
[19] Hooker, J.N. (2012). Integrated methods for optimization (International Series in Operations Research & Management Science), 2nd Edn. Inc., Secaucus, Springer-Verlag New York.
[20] Khemmoudj, M., Bennaceur, H., & Nagih, A. (2005). Combining arc-consistency and dual lagrangean relaxation for filtering csps. In R. Barták & M. Milano (Eds.), Integration of AI and OR techniques in Constraint programming for combinatorial optimization problems, Lecture notes in computer science (Vol. 3524, pp. 258-272). Springer Berlin Heidelberg. · Zbl 1133.90405
[21] Lee, CY, Representation of switching circuits by binary-decision programs, Bell Systems Technical Journal, 38, 985-999, (1959)
[22] Lemaréchal, C. (2001). Lagrangian relaxation. In M. Jünger & D. Naddef (Eds.), Computational combinatorial optimization, Lecture notes in computer science (Vol. 2241, pp. 112-156). Springer Berlin Heidelberg. · Zbl 1052.90065
[23] Papadimitriou, C.H., & Steiglitz, K. (1982). Combinatorial optimization: algorithms and complexity. Prentice-Hall, Inc., Upper Saddle River. · Zbl 0503.90060
[24] Rossi, F., van Beek, P., & Walsh, T. (eds.) (2006). Handbook of constraint programming. Elsevier. · Zbl 1175.90011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.