Open Source Constraint Programming Solvers Written in Java
In a past life I wrote a language that would serve as a DSL to a variety of solvers. These solvers would include the Simplex based solvers, Quadratic solvers and in the most generalized form Constraint solvers. So I've had more than a passing interest in Constraint Programming (CP). Recently my interest in CP was rekindled. I was studying Javafx and found it's binding mechanism to be eerily familiar. So, I looked back at my archives and to my surprise discovered a boat load of open source projects in existence that catered to Constraint Programming. Here is the list I compiled over the years.
- Choco Solver - Choco Solver is a library for constraint satisfaction problems (CSP), constraint programming (CP) and explanation-based constraint solving (e-CP). Choco is built on a event-based propagation mechanism with backtrackable structures.
- Cream - Cream is library helping for developing intelligent programs requiring constraint satisfaction or optimization on finite domains. Cream provides a natural description of constraints. It allows extensions of constraint and satisfaction algorithms. It includes simulated Annealing and Taboo Search. It provides an interface to OpenOffice Calc (Spreadsheet).
- JSL - Java Search Library (JSL) is a framework for general searching on graphs. The standard search algorithms depth-first, breadth-first and A* are provided. JSL also allows the plug in of other search algorithms.
- JHCR - The K.U.Leuven JCHR System is an integration of Java and Constraint Handling Rules (CHR) designed with three aims in mind: user-friendliness, flexibility and efficiency. User-friendliness is achieved by providing a high-level rule-based syntax that feels familiar to both Java programmers and users of other CHR embeddings, and by full compliance to the refined operational semantics. Flexibility is the result of a well thought-out design, allowing e.g. an easy integration of built-in constraint solvers and variable types. An optimized compilation to Java code and the use of a very efficient constraint store make the performance of the K.U.Leuven JCHR System competitive with that of state of the art CHR implementations in e.g. Prolog and HAL.
- jOpt jOpt is an open source implementation of the Optimization Programming Language (OPL). OPL is a modeling language for combinatorial optimization problems that combines mathematical programming and constraint programming into a single language. Job Scheduling (JS), is the first add-on to have been released. Typically, JS problems involve assigning a set of activities to a limited number of resources with consideration given to time and ordering limitations.
- Drools Solver - Drools Solver is library to help you solve planning problems using heuristic algorithms. Examples of planning problems include: employee shifts, freight routing, supply sorting, class scheduling and the traveling salesman problem. The Drools-solver combines a search algorithm with the power of the drools rule engine. Drools Solver uses the Drools rule engine for score calculation, which greatly reduces the complexity and effort to write very scalable constraints in a declarative manner. Drools-solver supports several search algorithms to efficiently wade through the incredbly large number of possible solutions. Drools-solver implements local search, including tabu search and simulated annealing.
- JCL - Java Constraints Library (JCL) was one of the first libraries to bring constraints satisfaction problem solving to Java. JCL deals with discrete, fine domains as well as with continuous domains. Constraints can be crisp (as in the classic CSP problems) or soft.
- SAT4J - The SAT4J library provides a SATisfiability problem solver. Compared to the OpenSAT project, the SAT4J library targets first users of SAT "black boxes", willing to embed SAT technologies into their application without worrying about the details. SAT4J is an implementation in of Een and Sorenson's MiniSAT specification: An extensible SAT solver. The original implementation was in C++.
- Cassowary - Cassowary is an incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities. The library appears to be designed to support support UI applications.
- DragonBreath - The engine is built to solve search problems, i.e., problems for which you don't really know how to construct a solution but can describe what potential parts a solution can consist of and which restrictions must be satisfied by the parts / the parts' constellation. Parts can be variables as well as structural components. In addition, you can specify a preference between different solutions, i.e., solve optimization problems. Examples for such problems are scheduling, action planning and configuration.
- JaCop - JaCoP is a Java Constraint Programming solver. It provides a significant number of (global) constraints to facilitate efficient modeling.It is currently more than 90.000 lines of code, not including examples and testing code. There are more than 20.000 lines of code explaining how to model and solve diverse problems.
If you know of other projects in this area, please free to let me know.
Last modified 2010-12-10 04:04 PM