cc(FD) swMATH ID: 21237 Software Authors: Van Hentenryck, Pascal; Saraswat, Vijay; Deville, Yves Description: Design, implementation, and evaluation of the constraint language cc(FD). This paper describes the design, implementation, and applications of the constraint logic language cc(FD). cc(FD) is a declarative nondeterministic constraint logic language over finite domains based on the cc framework [33], an extension of the Constraint Logic Programming (CLP) scheme [21]. Its constraint solver includes (nonlinear) arithmetic constraints over natural numbers which are approximated using domain and interval consistency. The main novelty of cc(FD) is the inclusion of a number of general-purpose combinators, in particular cardinality, constructive disjunction, and blocking implication, in conjunction with new constraint operations such as constraint entailment and generalization. These combinators significantly improve the operational expressiveness, extensibility, and flexibility of CLP languages and allow issues such as the definition of nonprimitive constraints and disjunctions to be tackled at the language level. The implementation of cc(FD) (about 40,000 lines of C) includes a WAM-based engine [44], optimal arc-consistency algorithms based on AC-5 [40], and incremental implementation of the combinators. Results on numerous problems, including scheduling, resource allocation, sequencing, packing, and hamiltonian paths are reported and indicate that cc(FD) comes close to procedural languages on a number of combinatorial problems. In addition, a small cc(FD) program was able to find the optimal solution and prove optimality to a famous 10/10 disjunctive scheduling problem [29], which was left open for more than 20 years and finally solved in 1986 Homepage: http://www.sciencedirect.com/science/article/pii/S0743106698100067 Keywords: constraint logic language; cc(FD) Related Software: CPLEX; Choco; COMET; MINION; Oz; Gecode; SICStus; ILOG SCHEDULE; OR-tools; Numerica; Chaff; CHIP; MiniSat; MiniCP; Mistral; OscaR; JaCoP; CBack; MiniZinc; SALSA Cited in: 17 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Design, implementation, and evaluation of the constraint language \(cc(FD)\). Zbl 0920.68026Van Hentenryck, Pascal; Saraswat, Vijay; Deville, Yves 1998 all top 5 Cited by 40 Authors 4 Van Hentenryck, Pascal 2 Bessiere, Christian 2 Deville, Yves 2 Hnich, Brahim 2 Michel, Laurent 2 Walsh, Toby 1 Abdallah, Areski Nait 1 Beldiceanu, Nicolas 1 Codish, Michael 1 Cortesi, Agostino 1 De Raedt, Luc 1 Debruyne, Romuald 1 del Vado Vírseda, Rafael 1 Frisch, Alan M. 1 Guns, Tias 1 Gutierrez, Julian 1 Hebrard, Emmanuel 1 Kaneko, Sosuke 1 Kiziltan, Zeynep 1 López-Fraguas, Francisco Javier 1 Mairy, Jean-Baptiste 1 Miguel, Ian 1 Nijssen, Siegfried 1 Ohrimenko, Olga 1 Pérez, Jorge A. 1 Petit, Thierry 1 Régin, Jean-Charles 1 Rochart, Guillaume 1 Rodríguez-Artalejo, Mario 1 Rueda, Camilo 1 Rueher, Michel 1 Saraswat, Vijay A. 1 Schaus, Pierre 1 Schulte, Christian 1 Stuckey, Peter James 1 Tack, Guido 1 Valencia, Frank D. 1 van Emden, Maarten H. 1 Zanioli, Matteo 1 Zhou, Neng-Fa all top 5 Cited in 7 Serials 5 Constraints 4 Artificial Intelligence 2 RAIRO. Operations Research 1 The Journal of Logic Programming 1 Higher-Order and Symbolic Computation 1 Computer Languages, Systems & Structures 1 Mathematical Programming Computation Cited in 5 Fields 13 Computer science (68-XX) 4 Operations research, mathematical programming (90-XX) 1 Combinatorics (05-XX) 1 Numerical analysis (65-XX) 1 Biology and other natural sciences (92-XX) Citations by Year