Abstract
Submodularity defines a general framework rich of important theoretical properties while accommodating numerous applications. Although the notion has been present in the literature of Combinatorial Optimization for several decades, it has been overlooked in the analysis of global constraints. The current work illustrates the potential of submodularity as a powerful tool for such an analysis. In particular, we show that the cumulative constraint, when all tasks are identical, has the submodular/supermodular representation property, i.e., it can be represented by a submodular/supermodular system of linear inequalities. Motivated by that representation, we show that the system of any two (global) constraints not necessarily of the same type, each bearing the above-mentioned property, has an integral relaxation given by the conjunction of the linear inequalities representing each individual constraint. This result is obtained through the use of the celebrated polymatroid intersection theorem.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Appa, G., Magos, D., Mourtos, I.: On the system of two all_different predicates. Inf. Process. Lett. 94, 99–105 (2005)
Aron, I.D., Leventhal, D.H., Sellmann, M.: A totally unimodular description of the consistent value polytope for binary constraint programming. In: Beck, J. C., Smith, B. M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Third International Conference, CPAIOR 2006, Cork, Ireland, May 31 - June 2, 2006, Proceedings, volume 3990 of Lecture Notes in Computer Science, p 2006
Bergman, D., Hooker, J.N.: Graph coloring inequalities from all-different systems. Constraints 19(4), 404–433 (2014)
Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Schonheim, J. (eds.) Combinatorial Structures and their Applications, pp 69–87. Gordon and Beach, New York (1970)
Edmonds, J., Giles, R.: A min-max relation for submodular functions in graphs. In: Hammer, P., Johnson, E., Korte, B. H., Newhauser, G. (eds.) Studies in Integer Programming (Workshop on Integer Programming, Bonn 1975), pp. 185–204. North-Holland, Amsterdam (1977)
Focacci, F., Lodi, A., Milano, M.: Mathematical programming techniques in constraint programming A short overview. J. Heuristics 8(1), 7–17 (2002)
Frank, A., Tardos, E.: Generalized polymatroids. Math. Program. 42, 489–563 (1988)
Hooker, J.: Logic-based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley-Interscience series in Discrete Mathematics and Optimization. John Wiley & Sons (2000)
Hooker, J.: Integrated methods for optimization, volume 100 of International series in Operations Research & Management Science. Springer, New York (2007)
Hooker, J.N.: A search-infer-and-relax framework for integrating solution methods. In: Barták, R., Milano, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Second International Conference, CPAIOR 2005, Prague, Czech Republic, May 30 - June 1, 2005 Proceedings, volume 3524 of Lecture Notes in Computer Science, p 2005
Hooker, J.N., Lama, M.A.O.: Mixed logical-linear programming. Discret. Appl. Math. 96-97, 395–442 (1999)
Hooker, J.N., Yan, H.: A relaxation of the cumulative constraint. In: Hentenryck, P. V. (ed.) Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, Proceedings, volume 2470 of Lecture Notes in Computer Science, pp 686–690. Springer (2002)
Kaya, L.G., Hooker, J.N.: Domain reduction for the circuit constraint. In: van Beek, P. (ed.) Principles and Practice of Constraint Programming - CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005, Proceedings, volume 3709 of Lecture Notes in Computer Science, p 846. Springer (2005)
Magos, D.: The constraint of difference and total dual integrality. In: Ketikidis, P. H., Margaritis, K. G., Vlahavas, I. P., Chatzigeorgiou, A., Eleftherakis, G., Stamelos, I. (eds.) Proceedings of the 17th Panhellenic Conference on Informatics, PCI Thessaloniki, Greece - September 19 - 21, 2013, pp. 188–194, ACM (2013)
Magos, D., Mourtos, I.: On the facial structure of the alldifferent system. SIAM J. Discrete Math. 25(1), 130–158 (2011)
Magos, D., Mourtos, I., Appa, G.: A polyhedral approach to the alldifferent system. Math Program. 132(1-2), 209–260 (2012)
Queyranne, M.: An introduction to set functions and optimization. Slides of IMA Seminar. Institute of Mathematics and its Applications, University of Minnesota Available online at https://www.ima.umn.edu/optimization/seminar/queyranne.pdf (2002)
Refalo, P.: Linear formulation of constraint programming models and hybrid solvers. In: Dechter, R. (ed.) Principles and Practice of Constraint Programming - CP 2000, 6th International Conference, Singapore, September 18-21, 2000, Proceedings, volume 1894 of Lecture Notes in Computer Science, pp 369–383. Springer (2000)
Schrijver, A.: Theory of linear and integer programming. John Willey & Sons, New York (1986)
Schrijver, A.: Combinatorial Optimization, polyhedra and efficiency. Springer, Berlin (2004)
Sellmann, M., Mercier, L., Leventhal, D.: The linear programming polytope of binary constraint problems with bounded tree-width. In: Hentenryck, P. V., Wolsey, L. (eds.) Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization problems. 4th International Conference CPAIOR 2007, volume 4510 of Lecture Notes in Computer Science, pp 275–287. Springer (2007)
Williams, H.P., Yan, H.: Representations of the all_different predicate of constraint satisfaction in integer programming. INFORMS J. on Computing 13(2), 96–103 (2001)
Yan, H., Hooker, J.: Tight representation of logical constraints as cardinality rules. Math. Program. 85, 363–377 (1999)
Yunes, T.H.: On the sum constraint: Relaxation and applications. In: Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, CP ’02, pp 80–92. Springer-Verlag (2002)
Yunes, T.H., Aron, I.D., Hooker, J.N.: An integrated solver for optimization problems. Oper. Res. 58(2), 342–356 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been co-financed by the European Union (European Social Fund ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: Thales. Investing in knowledge society through the European Social Fund.
Rights and permissions
About this article
Cite this article
Magos, D., Mourtos, I. Submodularity and its application to some global constraints. Ann Math Artif Intell 79, 267–289 (2017). https://doi.org/10.1007/s10472-016-9522-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-016-9522-x