minicp.cp

Class Factory

java.lang.Object

minicp.cp.Factory

public final class Factory
extends java.lang.Object

Factory to create Solver, IntVar, Constraint and some modeling utility methods. Example for the n-queens problem:

 
  Solver cp = Factory.makeSolver(false);
  IntVar[] q = Factory.makeIntVarArray(cp, n, n);
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      cp.post(Factory.notEqual(q[i], q[j]));
      cp.post(Factory.notEqual(q[i], q[j], j - i));
      cp.post(Factory.notEqual(q[i], q[j], i - j));
    }
  search.onSolution(() ->
    System.out.println("solution:" + Arrays.toString(q))
  );
  DFSearch search = Factory.makeDfs(cp,firstFail(q));
  SearchStatistics stats = search.solve();
 
 

Method Summary

Modifier and Type	Method and Description
static IntVar	abs(IntVar x) Computes a variable that is the absolute value of the given variable.
static Constraint	allDifferent(IntVar[] x) Returns a binary decomposition of the allDifferent constraint.
static Constraint	allDifferentDC(IntVar[] x) Returns an allDifferent constraint that enforces domain consistency.
static IntVar	element(int[][] matrix, IntVar x, IntVar y) Returns a variable representing the value in a matrix at the position specified by the two given row and column index variables This relation is enforced by the Element2D constraint posted by calling this method.
static IntVar	element(int[] array, IntVar y) Returns a variable representing the value in an array at the position specified by the given index variable This relation is enforced by the Element1D constraint posted by calling this method.
static Constraint	equal(IntVar x, int v) Returns a constraint imposing that the variable is equal to some given value.
static Constraint	equal(IntVar x, IntVar y) Returns a constraint imposing that the two different variables must take the value.
static BoolVar	isEqual(IntVar x, int c) Returns a boolean variable representing whether one variable is equal to the given constant.
static BoolVar	isLarger(IntVar x, int c) Returns a boolean variable representing whether one variable is larger than the given constant.
static BoolVar	isLargerOrEqual(IntVar x, int c) Returns a boolean variable representing whether one variable is larger or equal to the given constant.
static BoolVar	isLess(IntVar x, int c) Returns a boolean variable representing whether one variable is less than the given constant.
static BoolVar	isLessOrEqual(IntVar x, int c) Returns a boolean variable representing whether one variable is less or equal to the given constant.
static Constraint	largerOrEqual(IntVar x, IntVar y) Returns a constraint imposing that the a first variable is larger or equal to a second one.
static Constraint	lessOrEqual(IntVar x, int v) Returns a constraint imposing that the variable less or equal to some given value.
static Constraint	lessOrEqual(IntVar x, IntVar y) Returns a constraint imposing that the a first variable is less or equal to a second one.
static BoolVar	makeBoolVar(Solver cp) Creates a boolean variable.
static DFSearch	makeDfs(Solver cp, java.util.function.Supplier<Procedure[]> branching) Creates a Depth First Search with custom branching heuristic
static IntVar	makeIntVar(Solver cp, int sz) Creates a variable with a domain of specified arity.
static IntVar	makeIntVar(Solver cp, int min, int max) Creates a variable with a domain equal to the specified range.
static IntVar	makeIntVar(Solver cp, java.util.Set<java.lang.Integer> values) Creates a variable with a domain equal to the specified set of values.
static IntVar[]	makeIntVarArray(int n, java.util.function.Function<java.lang.Integer,IntVar> body) Creates an array of variables with specified lambda function
static IntVar[]	makeIntVarArray(Solver cp, int n, int sz) Creates an array of variables with specified domain size.
static IntVar[]	makeIntVarArray(Solver cp, int n, int min, int max) Creates an array of variables with specified domain bounds.
static Solver	makeSolver() Creates a constraint programming solver
static Solver	makeSolver(boolean byCopy) Creates a constraint programming solver
static IntVar	maximum(IntVar... x) Computes a variable that is the maximum of a set of variables.
static IntVar	minimum(IntVar... x) Computes a variable that is the minimum of a set of variables.
static IntVar	minus(IntVar x) A variable that is a view of -x.
static IntVar	minus(IntVar x, int v) A variable that is a view of x-v.
static IntVar	mul(IntVar x, int a) A variable that is a view of x*a.
static BoolVar	not(BoolVar b) A boolean variable that is a view of !b.
static Constraint	notEqual(IntVar x, int v) Returns a constraint imposing that the variable is different from some given value.
static Constraint	notEqual(IntVar x, IntVar y) Returns a constraint imposing that the two different variables must take different values.
static Constraint	notEqual(IntVar x, IntVar y, int c) Returns a constraint imposing that the the first variable differs from the second one minus a constant value.
static IntVar	plus(IntVar x, int v) A variable that is a view of x+v.
static Constraint	sum(int y, IntVar... x) Returns a sum constraint.
static IntVar	sum(IntVar... x) Returns a variable representing the sum of a given set of variables.
static Constraint	sum(IntVar[] x, int y) Returns a sum constraint.
static Constraint	sum(IntVar[] x, IntVar y) Returns a sum constraint.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

makeSolver

public static Solver makeSolver()

Creates a constraint programming solver

Returns:

a constraint programming solver with trail-based memory management

makeSolver

public static Solver makeSolver(boolean byCopy)

Creates a constraint programming solver

Parameters:

byCopy - a value that should be true to specify copy-based state management or falso for a trail-based memory management

Returns:

a constraint programming solver

makeIntVar

public static IntVar makeIntVar(Solver cp,
                                int sz)

Creates a variable with a domain of specified arity.

Parameters:

cp - the solver in which the variable is created

sz - a positive value that is the size of the domain

Returns:

a variable with domain equal to the set {0,...,sz-1}

makeIntVar

public static IntVar makeIntVar(Solver cp,
                                int min,
                                int max)

Creates a variable with a domain equal to the specified range.

Parameters:

cp - the solver in which the variable is created

min - the lower bound of the domain (included)

max - the upper bound of the domain (included) max > min

Returns:

a variable with domain equal to the set {min,...,max}

makeIntVar

public static IntVar makeIntVar(Solver cp,
                                java.util.Set<java.lang.Integer> values)

Creates a variable with a domain equal to the specified set of values.

Parameters:

cp - the solver in which the variable is created

values - a set of values

Returns:

a variable with domain equal to the set of values

makeBoolVar

public static BoolVar makeBoolVar(Solver cp)

Creates a boolean variable.

Parameters:

cp - the solver in which the variable is created

Returns:

an uninstantiated boolean variable

makeIntVarArray

public static IntVar[] makeIntVarArray(Solver cp,
                                       int n,
                                       int sz)

Creates an array of variables with specified domain size.

Parameters:

cp - the solver in which the variables are created

n - the number of variables to create

sz - a positive value that is the size of the domain

Returns:

an array of n variables, each with domain equal to the set {0,...,sz-1}

makeIntVarArray

public static IntVar[] makeIntVarArray(Solver cp,
                                       int n,
                                       int min,
                                       int max)

Creates an array of variables with specified domain bounds.

Parameters:

cp - the solver in which the variables are created

n - the number of variables to create

min - the lower bound of the domain (included)

max - the upper bound of the domain (included) max > min

Returns:

an array of n variables each with a domain equal to the set {min,...,max}

makeIntVarArray

public static IntVar[] makeIntVarArray(int n,
                                       java.util.function.Function<java.lang.Integer,IntVar> body)

Creates an array of variables with specified lambda function

Parameters:

n - the number of variables to create

body - the function that given the index i in the array creates/map the corresponding IntVar

Returns:

an array of n variables with variable at index i generated as body.get(i)

makeDfs

public static DFSearch makeDfs(Solver cp,
                               java.util.function.Supplier<Procedure[]> branching)

Creates a Depth First Search with custom branching heuristic

 // Example of binary search: At each node it selects
 // the first free variable qi from the array q,
 // and creates two branches qi=v, qi!=v where v is the min value domain
 
 DFSearch search = Factory.makeDfs(cp, () -> {
     IntVar qi = Arrays.stream(q).reduce(null, (a, b) -> b.size() > 1 && a == null ? b : a);
     if (qi == null) {
        return return EMPTY;
     } else {
        int v = qi.min();
        Procedure left = () -> cp.post(equal(qi, v)); // left branch
        Procedure right = () -> cp.post(notEqual(qi, v)); // right branch
        return branch(left, right);
     }
 });
 
 

Parameters:

cp - the solver that will be used for the search

branching - a generator that is called at each node of the depth first search tree to generate an array of Procedure objects that will be used to commit to child nodes. It should return BranchingScheme.EMPTY whenever the current state is a solution.

Returns:

the depth first search object ready to execute with DFSearch.solve() or DFSearch.optimize(Objective) using the given branching scheme

See Also:

BranchingScheme.firstFail(IntVar...), BranchingScheme.branch(Procedure...)

mul

public static IntVar mul(IntVar x,
                         int a)

A variable that is a view of x*a.

Parameters:

x - a variable

a - a constant to multiply x with

Returns:

a variable that is a view of x*a

minus

public static IntVar minus(IntVar x)

A variable that is a view of -x.

Parameters:

x - a variable

Returns:

a variable that is a view of -x

plus

public static IntVar plus(IntVar x,
                          int v)

A variable that is a view of x+v.

Parameters:

x - a variable

v - a value

Returns:

a variable that is a view of x+v

minus

public static IntVar minus(IntVar x,
                           int v)

A variable that is a view of x-v.

Parameters:

x - a variable

v - a value

Returns:

a variable that is a view of x-v

not

public static BoolVar not(BoolVar b)

A boolean variable that is a view of !b.

Parameters:

b - a boolean variable

Returns:

a boolean variable that is a view of !b

abs

public static IntVar abs(IntVar x)

Computes a variable that is the absolute value of the given variable. This relation is enforced by the Absolute constraint posted by calling this method.

Parameters:

x - a variable

Returns:

a variable that represents the absolute value of x

maximum

public static IntVar maximum(IntVar... x)

Computes a variable that is the maximum of a set of variables. This relation is enforced by the Maximum constraint posted by calling this method.

Parameters:

x - the variables on which to compute the maximum

Returns:

a variable that represents the maximum on x

See Also:

minimum(IntVar...)

minimum

public static IntVar minimum(IntVar... x)

Computes a variable that is the minimum of a set of variables. This relation is enforced by the Maximum constraint posted by calling this method.

Parameters:

x - the variables on which to compute the minimum

Returns:

a variable that represents the minimum on x

See Also:

(IntVar...)

equal

public static Constraint equal(IntVar x,
                               int v)

Returns a constraint imposing that the variable is equal to some given value.

Parameters:

x - the variable to be assigned to v

v - the value that must be assigned to x

Returns:

a constraint so that x = v

lessOrEqual

public static Constraint lessOrEqual(IntVar x,
                                     int v)

Returns a constraint imposing that the variable less or equal to some given value.

Parameters:

x - the variable that is constrained bo be less or equal to v

v - the value that must be the upper bound on x

Returns:

a constraint so that x <= v

notEqual

public static Constraint notEqual(IntVar x,
                                  int v)

Returns a constraint imposing that the variable is different from some given value.

Parameters:

x - the variable that is constrained bo be different from v

v - the value that must be different from x

Returns:

a constraint so that x != y

notEqual

public static Constraint notEqual(IntVar x,
                                  IntVar y)

Returns a constraint imposing that the two different variables must take different values.

Parameters:

x - a variable

y - a variable

Returns:

a constraint so that x != y

equal

public static Constraint equal(IntVar x,
                               IntVar y)

Returns a constraint imposing that the two different variables must take the value.

Parameters:

x - a variable

y - a variable

Returns:

a constraint so that x = y

notEqual

public static Constraint notEqual(IntVar x,
                                  IntVar y,
                                  int c)

Returns a constraint imposing that the the first variable differs from the second one minus a constant value.

Parameters:

x - a variable

y - a variable

c - a constant

Returns:

a constraint so that x != y+c

isEqual

public static BoolVar isEqual(IntVar x,
                              int c)

Returns a boolean variable representing whether one variable is equal to the given constant. This relation is enforced by the IsEqual constraint posted by calling this method.

Parameters:

x - the variable

c - the constant

Returns:

a boolean variable that is true if and only if x takes the value c

See Also:

IsEqual

isLessOrEqual

public static BoolVar isLessOrEqual(IntVar x,
                                    int c)

Returns a boolean variable representing whether one variable is less or equal to the given constant. This relation is enforced by the IsLessOrEqual constraint posted by calling this method.

Parameters:

x - the variable

c - the constant

Returns:

a boolean variable that is true if and only if x takes a value less or equal to c

isLess

public static BoolVar isLess(IntVar x,
                             int c)

Returns a boolean variable representing whether one variable is less than the given constant. This relation is enforced by the IsLessOrEqual constraint posted by calling this method.

Parameters:

x - the variable

c - the constant

Returns:

a boolean variable that is true if and only if x takes a value less than c

isLargerOrEqual

public static BoolVar isLargerOrEqual(IntVar x,
                                      int c)

Returns a boolean variable representing whether one variable is larger or equal to the given constant. This relation is enforced by the IsLessOrEqual constraint posted by calling this method.

Parameters:

x - the variable

c - the constant

Returns:

a boolean variable that is true if and only if x takes a value larger or equal to c

isLarger

public static BoolVar isLarger(IntVar x,
                               int c)

Returns a boolean variable representing whether one variable is larger than the given constant. This relation is enforced by the IsLessOrEqual constraint posted by calling this method.

Parameters:

x - the variable

c - the constant

Returns:

a boolean variable that is true if and only if x takes a value larger than c

lessOrEqual

public static Constraint lessOrEqual(IntVar x,
                                     IntVar y)

Returns a constraint imposing that the a first variable is less or equal to a second one.

Parameters:

x - a variable

y - a variable

Returns:

a constraint so that x <= y

largerOrEqual

public static Constraint largerOrEqual(IntVar x,
                                       IntVar y)

Returns a constraint imposing that the a first variable is larger or equal to a second one.

Parameters:

x - a variable

y - a variable

Returns:

a constraint so that x >= y

element

public static IntVar element(int[] array,
                             IntVar y)

Returns a variable representing the value in an array at the position specified by the given index variable This relation is enforced by the Element1D constraint posted by calling this method.

Parameters:

array - the array of values

y - the variable

Returns:

a variable equal to array[y]

element

public static IntVar element(int[][] matrix,
                             IntVar x,
                             IntVar y)

Returns a variable representing the value in a matrix at the position specified by the two given row and column index variables This relation is enforced by the Element2D constraint posted by calling this method.

Parameters:

matrix - the n x m 2D array of values

x - the row variable with domain included in 0..n-1

y - the column variable with domain included in 0..m-1

Returns:

a variable equal to matrix[x][y]

sum

public static IntVar sum(IntVar... x)

Returns a variable representing the sum of a given set of variables. This relation is enforced by the Sum constraint posted by calling this method.

Parameters:

x - the n variables to sum

Returns:

a variable equal to x[0]+x[1]+...+x[n-1]

sum

public static Constraint sum(IntVar[] x,
                             IntVar y)

Returns a sum constraint.

Parameters:

x - an array of variables

y - a variable

Returns:

a constraint so that y = x[0]+x[1]+...+x[n-1]

sum

public static Constraint sum(IntVar[] x,
                             int y)

Returns a sum constraint.

Parameters:

x - an array of variables

y - a constant

Returns:

a constraint so that y = x[0]+x[1]+...+x[n-1]

sum

public static Constraint sum(int y,
                             IntVar... x)

Returns a sum constraint.

Uses a _parameter pack_ to automatically bundle a list of IntVar as an array

Parameters:

y - the target value for the sum (a constant)

x - a parameter pack of IntVar representing an array of variables

Returns:

a constraint so that y = x[0] + ... + x[n-1]

allDifferent

public static Constraint allDifferent(IntVar[] x)

Returns a binary decomposition of the allDifferent constraint.

Parameters:

x - an array of variables

Returns:

a constraint so that x[i] != x[j] for all i < j

allDifferentDC

public static Constraint allDifferentDC(IntVar[] x)

Returns an allDifferent constraint that enforces domain consistency.

Parameters:

x - an array of variables

Returns:

a constraint so that x[i] != x[j] for all i < j