×

zbMATH — the first resource for mathematics

MiniBrass: soft constraints for MiniZinc. (English) Zbl 1430.90525
Summary: Over-constrained problems are ubiquitous in real-world decision and optimization problems. Plenty of modeling formalisms for various problem domains involving soft constraints have been proposed, such as weighted, fuzzy, or probabilistic constraints. All of them were shown to be instances of algebraic structures. In terms of modeling languages, however, the field of soft constraints lags behind the state of the art in classical constraint optimization. We introduce MiniBrass, a versatile soft constraint modeling language building on the unifying algebraic framework of partially ordered valuation structures (PVS) that is implemented as an extension of MiniZinc and MiniSearch. We first demonstrate the adequacy of PVS to naturally augment partial orders with a combination operation as used in soft constraints. Moreover, we provide the most general construction of a c-semiring from an arbitrary PVS. Both arguments draw upon elements from category theory. MiniBrass turns these theoretical considerations into practice: It offers a generic extensible PVS type system, reusable implementations of specific soft constraint formalisms as PVS types, operators for complex PVS products, and morphisms to transform PVS. MiniBrass models are compiled into MiniZinc to benefit from the wide range of solvers supporting FlatZinc. We evaluated MiniBrass on 28 “softened” MiniZinc benchmark problems with six different solvers. The results demonstrate the feasibility of our approach.
MSC:
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, T.E., Chen, M., Goldsmith, J., Mattei, N., Popova, A., Regenwetter, M., Rossi, F., Zwilling, C. (2015). Beyond theory and data in preference modeling: bringing humans into the loop. In T. Walsh (Ed.) Proceedings of the 4th international conference on algorithmic decision theory (ADT’15). Lecture notes in computer science (Vol. 9346, pp. 3-18). Berlin: Springer. · Zbl 1405.91134
[2] Allouche, D, de Givry, S., Schiex, T. (2010). Toulbar2, an open-source exact cost function network solver. Tech. rep., INRIA.
[3] Allouche, D, de Givry, S., Katsirelos, G., Schiex, T., Zytnicki, M. (2015). Anytime hybrid best-first search with tree decomposition for weighted CSP. In G. Pesant (Ed.) Proceedings of the 21st international conference on principles and practice of constraint programming (CP’15). Lecture notes in computer science (Vol. 9255, pp. 12-29). Berlin: Springer.
[4] Amadio, R.M., & Curien, P.L. (1998). Domains and Lambda-Calculi. Cambridge Tracts in Theoretical Computer Science 46. Cambridge: Cambridge University Press.
[5] Ansótegui, C., Bofill, M., Palahí, M., Suy, J., Villaret, M. (2011). W-minizinc: a proposal for modeling weighted CSPs with MiniZinc. In Proceedings of the 1st international workshop on MiniZinc (MZN’11).
[6] Ansótegui, C.; Bofill, M.; Palahí, M.; Suy, J.; Villaret, M., Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories, Constraints, 18, 236-268, (2013) · Zbl 1309.90083
[7] Awodey, S. (2010). Category theory. Oxford: Oxford University Press. · Zbl 1194.18001
[8] Barr, M., & Wells, C. (1990). Category theory for computing science. Englewood Cliffs: Prentice Hall. · Zbl 0714.18001
[9] Beldiceanu, N.; Carlsson, M.; Flener, P.; Pearson, J., On the reification of global constraints, Constraints, 18, 1-6, (2013) · Zbl 1328.68192
[10] Bertele, U.; Brioschi, F., On non-serial dynamic programming, Journal of Combinatorial Theory Series A, 14, 137-148, (1973) · Zbl 0264.49021
[11] Bistarelli, S. (2004). Semirings for soft constraint solving and programming. Lecture notes in computer science Vol. 2962. Berlin: Springer.
[12] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint satisfaction and optimization, Journal of the ACM, 44, 201-236, (1997) · Zbl 0890.68032
[13] Bistarelli, S.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G.; Fargier, H., Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison, Constraints, 4, 199-240, (1999) · Zbl 0946.68143
[14] Bistarelli, S., Fung, S.K.L., Lee, J.H.M., Leung, H. (2003). A local search framework for semiring-based constraint satisfaction problems. In Proceedings of the workshop on soft constraints (Soft’03).
[15] Borning, A.; Freeman-Benson, B.; Wilson, M., Constraint hierarchies, LISP and Symbolic Computation, 5, 223-270, (1992) · Zbl 0942.68515
[16] Boutilier, C.; Brafman, RI; Domshlak, C.; Hoos, HH; Poole, D., CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements, Journal of Artificial Intelligence Research, 21, 135-191, (2004) · Zbl 1080.68685
[17] Brandt, F., Conitzer, V., Endriss, U. (2013). Computational social choice. In G. Weiß (Ed.) Multiagent systems, 2nd edn, chapter 6 (pp. 213-283). MIT Press.
[18] Cooper, MC; Schiex, T., Arc consistency for soft constraints, Artificial Intelligence, 154, 199-227, (2004) · Zbl 1085.68672
[19] Cooper, MC; Givry, S.; Sánchez, M.; Schiex, T.; Zytnicki, M.; Werner, T., Soft arc consistency revisited, Artificial Intelligence, 174, 449-478, (2010) · Zbl 1213.68580
[20] Dalla Pozza, G., Pini, M.S., Rossi, F., Venable, K.B. (2011). Multi-agent soft constraint aggregation via sequential voting. In T. Walsh (Ed.) Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI’11). IJCAI/AAAI (pp. 172-177).
[21] Dechter, R., Bucket elimination: a unifying framework for reasoning, Artificial Intelligence, 113, 41-85, (1999) · Zbl 0939.68847
[22] Dechter, R. (2003). Constraint processing. San Mateo: Morgan Kaufmann. · Zbl 1057.68114
[23] Diaconescu, R. (1994). Category-based semantics for equational and constraint logic programming. Ph.D. thesis, Oxford University, Oxford.
[24] Fargier, H., & Lang, J. (1993). Uncertainty in constraint satisfaction problems: a probabilistic approach. In M. Clarke, R. Kruse, S. Moral (Eds.) Proceedings of the european conference symbolic and quantitative approaches to reasoning and uncertainty . Lecture notes in computer science (Vol. 747, pp. 97-104). Berlin: Springer.
[25] Fioretto, F., Pontelli, E., Yeoh, W. (2016). Distributed constraint optimization problems and applications: a survey. CoRR arXiv:1602.06347. · Zbl 1440.68307
[26] Fleming, PJ; Wallace, JJ, How not to lie with statistics: the correct way to summarize benchmark results, Communications of the ACM, 29, 218-221, (1986)
[27] Freuder, EC; Wallace, RJ, Partial constraint satisfaction, Artificial Intelligence, 58, 21-70, (1992)
[28] Frisch, AM; Harvey, W.; Jefferson, C.; Martínez-Hernández, B.; Miguel, I., Essence: a constraint language for specifying combinatorial problems, Constraints, 13, 268-306, (2008) · Zbl 1147.68424
[29] Gadducci, F., Hölzl, M., Monreale, G.V., Wirsing, M. (2013). Soft constraints for lexicographic orders. In F. Castro, A. Gelbukh, M. González (Eds.) Proceedings of the 12th Mexican international conference on artificial intelligence (MICAI’2013). Lecture notes in computer science (Vol. 8265, pp. 68-79). Berlin: Springer.
[30] Google optimization tools. https://developers.google.com/optimization. [Online, Accessed: 29 June 2017.
[31] Guns, T.; Dries, A.; Nijssen, S.; Tack, G.; De Raedt, L., MiningZinc: a declarative framework for constraint-based mining, Artificial Intelligence, 244, 6-29, (2017) · Zbl 1404.68106
[32] Hebrard, E., O’Mahony, E., O’Sullivan, B. (2010). Constraint programming and combinatorial optimisation in Numberjack. In A. Lodi, M. Milano, P. Toth (Eds.) Proceedings of the 7th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR’10). Lecture notes in computer science (Vol. 6140, pp. 181-185). Berlin: Springer.
[33] Hosobe, H. (2009). Constraint hierarchies as semiring-based CSPs. In Proceedings of the 21st international conference on tools with artificial intelligence (ICTAI’2009) (pp. 176-183).
[34] Hurley, B.; O’Sullivan, B.; Allouche, D.; Katsirelos, G.; Schiex, T.; Zytnicki, M.; Givry, S., Multi-language evaluation of exact solvers in graphical model discrete optimization, Constraints, 21, 413-434, (2016) · Zbl 1368.90107
[35] Junker, U. (2009). Outer branching: how to optimize under partial orders? In V. Barichard, M. Ehrgott, X. Gandibleux, V. T’Kindt (Eds.) Proceedings of the 7th international conference on multiobjective programming and goal programming (MOPGP’06). Lecture notes in economics and mathematical systems (Vol. 618, pp. 99-109). Berlin: Springer. · Zbl 1176.90520
[36] Jussien, N., Rochart, G., Lorca, X. (2008). Choco: an open-source Java constraint programming library. In Proceedings of the workshop on open-source software for integer and constraint programming (OSSICP’08) (pp. 1-10).
[37] Kaci, S. (2011). Working with preferences: less is more. Berlin: Springer. · Zbl 1239.68002
[38] Kießling, W., & Köstler, G. (2002). Preference SQL: design, implementation, experiences. In Proceedings of the 28th international conference on very large data bases (VLDB’02) (pp. 990-1001). San Mateo: Morgan Kaufmann.
[39] Knapp, A., Schiendorfer, A., Reif, W. (2014). Quality over quantity in soft constraints. In Proceedings of the 26th international conference on tools with artificial intelligence (ICTAI’2014) (pp. 453-460).
[40] Kuchcinski, K., & Szymanek, R. (2013). JaCoP—Java constraint programming solver. In Proceedings of the workshop on CP solvers: modeling, applications, integration, and standardization.
[41] Leenen, L., Anbulagan, A, Meyer, T., Ghose, A.K. (2007). Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT. In M.A. Orgun, & J. Thornton (Eds.) Proceedings of the 20th Australian joint conference on artificial intelligence. Lecture Notes in Computer Science (Vol. 4830, pp. 202-212). Berlin: Springer.
[42] Mears, C., Schutt, A., Stuckey, P.J., Tack, G., Marriott, K., Wallace, M. (2014). Modelling with option types in MiniZinc. In H. Simonis (Ed.) Proceedings of the 11th international conference on integration of artificial intelligence and operations research techniques in constraint programming (CPAIOR’14), Lecture notes in computer science (Vol. 8451, pp. 88-103). Berlin: Springer. · Zbl 1407.68458
[43] Meseguer, P., Rossi, F., Schiex, T. (2006). Soft constraints. In F. Rossi, P. van Beek, T. Walsh (Eds.) Handbook of constraint programming, chap. 9. Amsterdam: Elsevier.
[44] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G. (2007). MiniZinc: towards a standard CP modelling language. In C. Bessière (Ed.) Proceedings of the 13th international conference on principles and practice of constraint programming (CP’07). Lecture notes in computer science (Vol. 4741, pp. 529-543). Berlin: Springer.
[45] Nisan, N., & Ronen, A. (1999). Algorithmic mechanism design. In J.S. Vitter, L.L. Larmore, F.T. Leighton (Eds.) Proceedings of the 31st annual ACM symposium on theory of computing (STACS’99) (pp. 129-140). ACM. · Zbl 1346.68246
[46] Petit, T., Régin, J.C., Bessière, C. (2000). Meta-constraints on violations for over constrained problems. In Proceedings of the 12th international conference on tools with artificial intelligence (ICTAI’00) (pp. 358-365).
[47] Pierce, B.C. (1991). Basic category theory for computer scientists. Cambridge: MIT Press. · Zbl 0875.18001
[48] Rendl, A., Tack, G., Stuckey, P.J. (2014). Stochastic MiniZinc. In B. O’Sullivan (Ed.) Proceedings of the 20th international conference on principles and practice of constraint programming (CP’14), Lecture Notes in Computer Science (Vol. 8656, pp. 636-645). Berlin: Springer.
[49] Rendl, A., Guns, T., Stuckey, P.J., Tack, G. (2015). MiniSearch: a solver-independent meta-search language for MiniZinc. In G. Pesant (Ed.) Proceedings of the 21st international conference on constraint programming (CP’15), Lecture Notes in Computer Science (Vol. 9255, pp. 376-392).
[50] Rollón, E. (2008). Multi-objective optimization in graphical models. Ph.D. thesis, Universitat Politècnica de Catalunya, Barcelona.
[51] Rossi, F., & Pilan, I. (2003). Abstracting soft constraints: Some experimental results on fuzzy CSPs. In K.R. Apt, F. Fages, F. Rossi, P. Szeredi, J. Váncza (Eds.) Selected papers joint ERCIM/CologNET international workshop on constraint solving and constraint logic programming (CSCLP’03). Lecture notes in computer science (Vol. 3010, pp. 107-123). Berlin: Springer.
[52] Ruttkay, Z. (1994). Fuzzy constraint satisfaction. In Proceedings of the 3rd IEEE international fuzzy systems conference (pp. 1263-1268). IEEE.
[53] Sánchez, M., Allouche, D, de Givry, S., Schiex, T. (2009). Russian doll search with tree decomposition. In C. Boutilier (Ed.) Proceedings of the 21st international joint conference on artificial intelligence (IJCAI’09) (pp. 603-608).
[54] Sannella, D., & Tarlecki, A. (2012). Foundations of algebraic specification and formal software development. EATCS monographs in theoretical computer science. Berlin: Springer. · Zbl 1237.68129
[55] Schiendorfer, A., Steghöfer, J.P., Knapp, A., Nafz, F., Reif, W. (2013). Constraint relationships for soft constraints. In M. Bramer, & M. Petridis (Eds.) Proceedings of the 33rd SGAI international conference on innovative techniques and applications of artificial intelligence (AI’13) (pp. 241-255). Berlin: Springer.
[56] Schiendorfer, A., Steghöfer, J.P., Reif, W. (2014). Synthesis and abstraction of constraint models for hierarchical resource allocation problems. In Proceedings of the 6th international conference on agents and artificial intelligence (ICAART’14) (Vol. 2, pp. 15-27). SciTePress.
[57] Schiendorfer, A., Knapp, A., Steghöfer, J.P., Anders, G., Siefert, F., Reif, W. (2015). Partial valuation structures for qualitative soft constraints. In R.D. Nicola, & R. Hennicker (Eds.) Software, services and systems—essays dedicated to Martin Wirsing on the occasion of his emeritation, Lecture Notes in Computer Science (Vol. 8950, pp. 115-133). Berlin: Springer.
[58] Schiex, T., Fargier, H., Verfaillie, G. (1995). Valued constraint satisfaction problems: hard and easy problems. In Proceedings of the 14th international conference on artificial intelligence (IJCAI’95) (Vol. 1, pp. 631-639). San Mateo: Morgan Kaufmann.
[59] Schulte, C., Lagerkvist, M.Z., Tack, G. (2006). Gecode: generic constraint development environment. In INFORMS annual meeting.
[60] Shapiro, LG; Haralick, RM, Structural descriptions and inexact matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, 3, 504-519, (1981)
[61] Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In M.J. Maher, & J.F. Puget (Eds.) Proceedings of the 4th international conference on principles and practice of constraint programming (CP’98). lecture notes in computer science (Vol. 1520, pp. 417-431). Berlin: Springer.
[62] Shoham, Y., & Leyton-Brown, K. (2008). Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge: Cambridge University Press. · Zbl 1163.91006
[63] Stuckey, P.J., & Tack, G. (2013). MiniZinc with functions. In C.P. Gomes, & M. Sellmann (Eds.) Proceedings of the 10th international conference on integration of artificial intelligence and operations research techniques in constraint programming (CPAIOR’13). Lecture Notes in Computer Science (Vol. 7874, pp. 268-283). Berlin: Springer. · Zbl 1382.68234
[64] Stuckey, P.J, de la Banda, M.G., Maher, M., Marriott, K., Slaney, J., Somogyi, Z., Wallace, M., Walsh, T. (2005). The G12 project: mapping solver independent models to efficient solutions. In P. van Beek (Ed.) Proceedings of the 11th international conference on principles and practice of constraint programming (CP’05), Lecture Notes in Computer Science (Vol. 3709, pp. 13-16). Berlin: Springer. · Zbl 1165.68517
[65] Stuckey, PJ; Feydy, T.; Schutt, A.; Tack, G.; Fischer, J., The MiniZinc challenge 2008-2013, AI Magazine, 35, 55-60, (2014)
[66] van Hentenryck, P. (1999). The OPL optimization programming language. Cambridge: MIT Press.
[67] van Hoeve, W.J. (2011). Over-constrained problems. In M. Milano, & P. van Hentenryck (Eds.) Hybrid optimization, optimization and its applications (Vol. 45, pp. 191-225). Berlin: Springer. · Zbl 1206.90184
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.