JaCoMo is a high-level, solver-independent, Java constraint model for constraint satisfaction problems in the integer domain. JaCoMo can be used to model constrain satisfaction problems and then solve them using different solver implementations. Currently, supported solvers are:
The model stores the variables and constraints to solve.
Model model = new Model();The recommended method to declare variables is by using the model as demonstrated below. These variables are automatically added to the model itself when they are declared.
It is also possible to create variables using the factory methods from the BoolVar or Intvar interfaces or the class constructors. Those variables have to be added to the model manually using the addVar method.
BoolVar b1 = model.boolVar(); // Boolean variable with generated name (_bool_0, _bool_1, etc.)
BoolVar b2 = model.boolVar("x"); // Boolean variable with given name
BoolVar b3 = model.boolVar(true); // Boolean variable with generated name and constant value
BoolVar b4 = model.boolVar("y", true); // Boolean variable with given name and constant value
BoolVar b5 = model.boolVar(b1.and(b2)); // Boolean variable with generated name and given expression
BoolVar b6 = model.boolVar("z", b3.or(b4)); // Boolean variable with given name and given expressionIntVar i1 = model.intVar(); // Integer variable with generated name (_int_0, _int_1, etc.)
IntVar i2 = model.intVar("u"); // Integer variable with given name
IntVar i3 = model.intVar(3); // Integer variable with generated name and given value
IntVar i4 = model.intVar("v", 4); // Integer variable with given name and given value
IntVar i5 = model.intVar(i1.add(i2)); // Integer variable with generated name and given expression
IntVar i6 = model.intVar("w", i3.mul(i4)); // Integer variable with given name and given expression
IntVar i7 = model.intVar(1, 7); // Integer variable with generated name and given bounds
IntVar i8 = model.intVar("x", 1, 8); // Integer variable with given name and given bounds
IntVar i9 = model.intVarLb(9); // Integer variable with generated name and given lower bound
IntVar i10 = model.intVarLb("y", 10); // Integer variable with given name and given lower bound
IntVar i11 = model.intVarUb(11); // Integer variable with generated name and given upper bound
IntVar i12 = model.intVarUb("z", 12); // Integer variable with given name and given upper boundExpressions can be used to define variables or to create constraints.
BoolExpr b7 = BoolExpr.constant(true); // Create constant
BoolExpr b8 = b1.not(); // Not expression: !b1
BoolExpr b9 = b2.and(b8); // And expression: b2 && b8
BoolExpr b10 = b8.or(b9); // Or expression: b8 || b9There are also vararg methods available to chain expressions:
BoolExpr b11 = BoolExpr.and(b7, b8, b9); // And expression: b7 && b8 && b9
BoolExpr b12 = BoolExpr.or(b7, b8, b9, b10); // Or expression: b7 || b8 || b9 || b10IntExpr i13 = IntExpr.constant(1); // Create constant
IntExpr i14 = i10.add(i13); // Add expr: i10 + i13
IntExpr i15 = i13.sub(i14); // Sub expr: i13 - i14
IntExpr i16 = i14.mul(i15); // Mul expr: i14 * i15
IntExpr i17 = i13.div(i15); // Div expr: i13 / i15
IntExpr i18 = i16.max(i17); // Max expr: max(i16, i17)
IntExpr i19 = i16.min(i17); // Min expr: min(i16, i17)There are also vararg methods available to chain expressions:
IntExpr i20 = IntExpr.add(i13, i14, i15, i16); // Add expr: i13 + i14 + i15 + i16
IntExpr i21 = IntExpr.sub(i14, i15, i16, i17); // Sub expr: ((i14 - i15) - i16) - i17
IntExpr i22 = IntExpr.mul(i13, i14, i15); // Mul expr: i13 * i14 * i15
IntExpr i23 = IntExpr.div(i17, i18, i19); // Div expr: (i17 / i18) / i19
IntExpr i24 = IntExpr.max(i15, i16, i17, i18, i19); // Max expr: max(i15, i16, i17, i18, i19)
IntExpr i25 = IntExpr.min(i14, i15, i16, i17, i18); // Min expr: min(i14, i15, i16, i17, i18)Relational expressions are expressions that compare two integers and result in a boolean expression.
BoolExpr b13 = i10.eq(i20); // Eq expr: i10 == i20
BoolExpr b14 = i11.ne(i21); // Ne expr: i11 != i21
BoolExpr b15 = i22.gt(i23); // Gt expr: i22 > i23
BoolExpr b16 = i15.ge(i21); // Ge expr: i15 >= i21
BoolExpr b17 = i17.le(i19); // Le expr: i17 <= i19
BoolExpr b18 = i18.lt(i22); // Lt expr: i18 < i22Boolean expression constraints receive a boolean expression that should always hold.
model.constraint(i1.gt(i2)); // i1 should always be greater than i2
model.constraint(b1.or(b2)); // b1 should hold or b2 should holdModels can be solved using a Solver. The Solver returns a map of variables and their solved values. Solvers can also update the variables of the model directly.
Model model = new Model();
IntVar x = model.intVarLb("x", 2); // x > 2
Intvar y = model.intVarUb("y", 10); // y < 10
model.constraint(x.add(IntExpr.constant(2).mul(y)).eq(IntExpr.constant(7))); // x + 2 * y == 7
Solver solver = new ChocoSolver() // Pick solver implementation
VarMap vars = solver.solve(model); // Solves the model and returns variable map with resulting values
IntVar x2 = vars.getVar("x"); // Get the solved variable x
x2.getValue() // 3, the solved variable x has value 3
x.getValue(); // null, the model has not been updated thus x has not been instantiated
vars.getVar("y").getValue() // 2, the solved variable y has value 2
boolean solved = solver.solveAndUpdate(model) // Solves the model and updates the variables directly
x.getValue() // 3, the variable x has been updatedWhen there is no solution the solver behaves as follows:
Model model = new Model();
BoolVar z = model.boolVar("z");
model.constraint(z);
model.constraint(z.not());
Solver solver = new ChocoSolver()
VarMap vars = solver.solve(model); // Returns null since there is no viable solution
boolean solved = solver.solveAndUpdate(model) // Solved is false since there is no viable solution,
// the model has not been updatedSee the image below for an overview of available elements and how they relate to each other. A solid arrow indicates the parent element. Dashed arrows indicate additional implemented interfaces.
Click image for larger version
Custom visitors can be added by implementing the Visitor interface. When a visitor encounters an element, it will try to call its visit implementation for that element type. If no immediate implementation is found, the visitor will traverse up the parent tree till it finds an implementation for the visited element. If no implementation is found, a NotImplementedException is thrown.
Custom elements should extend the Elem interface. When adding custom elements the Visitor interface should also be extended with corresponding visit methods for the new element types and the main visit method should be adapted as well (only for the new element types, for existing elements super.visit can be used).
Existing Visitor implementations also need to be extended to use them with the new element types. The extended visitor only needs to implement visit methods for the new element types. Existing elements will be handled by the base visitor implementation (although the implementations can be overwritten if desired).
Version 0.1 is a minimal viable product. It contains the following:
- Basic model containing variables and constraints
- Basic variables
- Boolean
- Integer
- Basic expressions
- Constants
- Boolean
- Integer
- Boolean logic
- And
- Or
- Not
- Relational expressions
- Equals
- Not equals
- Lesser than
- Lesser or equals
- Greater than
- Greater or equals
- Basic arithmetic expressions
- Addition
- Subtraction
- Multiplication
- Integer division
- Minimum
- Maximum
- Constants
- Boolean constraints
- Basic variables
- Model factory methods for creating variables
- Visitor pattern for traversing the model
- Solver implementations
- Choco-solver
- OR-tools
- Unit-test for non-trivial classes and system tests
- Getting started documentation with examples
- JavaDoc documentation
- Maven Central Repository release
Future goals are to:
- Expand the model with more operations
- Xor expression
- Real variables
- Additional types of constraints
- Add more solver implementations
- MiniZinc
- OscaR
- JaCop
- Yuck