org.cpsolver.ifs.model

## Class Constraint<V extends Variable<V,T>,T extends Value<V,T>>

- java.lang.Object
- - org.cpsolver.ifs.model.Constraint<V,T>

- Type Parameters:
    `V` - Variable
    `T` - Value
  All Implemented Interfaces:
    Comparable<Constraint<V,T>>
  Direct Known Subclasses:
    BinaryConstraint, ClassLimitConstraint, ConstraintWithContext, ExamInstructor, ExamStudent, GlobalConstraint, IgnoreStudentConflictsConstraint, Job, LinkedSections.LinkedSectionsConstraint, Machine, StudentConflict

      public abstract class Constraint<V extends Variable<V,T>,T extends Value<V,T>>
      extends Object
      implements Comparable<Constraint<V,T>>

  Generic constraint.
  Like in other traditional Constraint Logic Programming (CLP) frameworks, the input problem consists of variables, values and constraints. Each constraint is defined over a subset of the problem variables and it prohibits some combinations of values which these variables can simultaneously take. In usual CSP problems, all constraints are binary (or the problem is transformed into an equivalent problem with only binary constrains before the search is started) since most of the consistency and filtering techniques are designed only for binary constraints. In such a case, the procedure computing conflicting variables is rather simple and it returns an unambiguous set of variables. It enumerates all the constraints which contain the selected variable and which are not consistent with the selected value. It returns all the variables of such constraints, different from the selected variable.
  On the other hand, most of real problems have plenty of multi-variable constraints, like, for instance, resource constraint in timetabling. Such resource constraint enforces the rule that none of the variables which are using the given resource can be overlapping in time (if the resource has capacity one) or that the amount of the resource used at a time does not exceed its capacity. It is not very useful to replace such resource constraint by a set of binary constraints (e.g., prohibiting two overlapping placements in time of two particular events using the same resource), since this approach usually ends up with thousands of constraints. Also, there is usually a much more effective consistency and/or filtering technique working with the original constraint (for instance, "cumulative" constraint is usually used for modelling resource constraints in CLP).
  Using multi-variable constraints, the set of conflicting variables returned by the procedure computing conflicting variables can differ according to its implementation. For instance, we can have a constraint A+B=C where A and C is already assigned to A=3 and C=5. Then if the assignment B=3 is selected, either A or B or both A and B can be unassigned to make the problem {A=3, B=3, C=5} consistent with the constraint A+B=C. Intuitively, there should be minimal number of variables unassigned in each iteration step (we are trying to increase the number of the assigned variables during the search). Also, for many constraints, it is possible to find inconsistencies even when not all variables of the constraint are yet assigned. For instance, if there are two lectures using the same room at the same time, we know that one of them needs to be unassigned even when there are unassigned lectures which will also need to be placed in that room.
  In the current implementation, each hard constraint needs to implement the procedure `computeConflicts(Assignment, Value, Set)` which returns all the already assigned values that are incompatible we the selected assignment (value which is to be assigned to its variable). This procedure is called for all constraints which contain the selected variable in an ordered manner. Furthermore, this order can be changed during the search. Moreover, the computed set of conflicting variables is passed to this `computeConflicts(Assignment, Value, Set)` procedure as a parameter, so the constraint can "see" what variables are already selected for unassignment by previously processed constraints. This way, we are not computing the very minimal set of conflicting variables, however, we allow for computing this set in an efficient way. It can be also tuned for a particular problem by changing the order of constraints.
  Also note that each constraint can keep its notion about the assigned variables. For instance, the resource constraint of a particular room can memorize a look-up table stating what lecture is assigned in what time slot(s), so for the computation of the conflicting lectures it only looks through the appropriate fields of this table. The implementation is based on `assigned(Assignment,long,Value)` and `unassigned(Assignment,long,Value)` methods that are responsible to keeping the problem consistent with the constraint. Also note that this default consistency technique is defined on a problem level and it can be changed by a more dedicated one, implemented for a particular problem.
  Version:
    IFS 1.3 (Iterative Forward Search)
    Copyright (C) 2006 - 2014 Tomáš Müller
    muller@unitime.org
    http://muller.unitime.org
    This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
    This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
    You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.
  Author:
    Tomáš Müller
  See Also:
    `Variable`, `Model`, `Solver`

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected List<ConstraintListener<V,T>>` | `iConstraintListeners`
    `protected long` | `iId`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Constraint()` Constructor

  - ### Method Summary

    All Methods Instance Methods Abstract Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `addConstraintListener(ConstraintListener<V,T> listener)` Adds a constraint listener
    `void` | `addVariable(V variable)` Add a variable to this constraint
    `void` | `assigned(Assignment<V,T> assignment, long iteration, T value)` Given value is to be assigned to its variable.
    `Collection<V>` | `assignedVariables(Assignment<V,T> assignment)` The list of variables of this constraint that are assigned
    `int` | `compareTo(Constraint<V,T> c)`
    `abstract void` | `computeConflicts(Assignment<V,T> assignment, T value, Set<T> conflicts)` The only method which has to be implemented by any constraint.
    `protected void` | `computeConflictsNoForwardCheck(Assignment<V,T> assignment, T value, Set<T> conflicts)` Compute conflicts method that does not do any forward checking.
    `List<ConstraintListener<V,T>>` | `constraintListeners()` Returns the list of registered constraint listeners
    `int` | `countAssignedVariables(Assignment<V,T> assignment)` The number of variables of this constraint that are assigned
    `int` | `countVariables()` The number of variables of this constraint
    `boolean` | `equals(Object o)` Compare two constraints for equality (`getId()` is used)
    `String` | `getDescription()` Constraint's description -- for printing purposes
    `long` | `getId()` Unique id
    `Model<V,T>` | `getModel()` The model which the constraint belongs to
    `String` | `getName()` Constraint's name -- for printing purposes
    `int` | `hashCode()`
    `boolean` | `inConflict(Assignment<V,T> assignment, T value)` Returns true if the given assignment is inconsistent with the existing assignments respecting this constraint.
    `boolean` | `isConsistent(T value1, T value2)` Returns true if the given assignments are consistent respecting this constraint.
    `boolean` | `isHard()` Returns true if the constraint is hard.
    `void` | `removeConstraintListener(ConstraintListener<V,T> listener)` Removes a constraint listener
    `void` | `removeVariable(V variable)` Remove a variable from this constraint
    `void` | `setModel(Model<V,T> model)` Sets the model which the constraint belongs to
    `void` | `unassigned(Assignment<V,T> assignment, long iteration, T value)` Given value is unassigned from its variable.
    `List<V>` | `variables()` The list of variables of this constraint

    - ### Methods inherited from class java.lang.Object

      `clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### iId

          protected long iId

    - #### iConstraintListeners

          protected List<ConstraintListener<V extends Variable<V,T>,T extends Value<V,T>>> iConstraintListeners

  - ### Constructor Detail

    - #### Constraint

          public Constraint()

      Constructor

  - ### Method Detail

    - #### getModel

          public Model<V,T> getModel()

      The model which the constraint belongs to
      Returns:
        problem model

    - #### setModel

          public void setModel(Model<V,T> model)

      Sets the model which the constraint belongs to
      Parameters:
        `model` - problem model

    - #### variables

          public List<V> variables()

      The list of variables of this constraint
      Returns:
        variables of this constraint

    - #### assignedVariables

          public Collection<V> assignedVariables(Assignment<V,T> assignment)

      The list of variables of this constraint that are assigned
      Parameters:
        `assignment` - current assignment
      Returns:
        assigned variables of this constraint

    - #### countVariables

          public int countVariables()

      The number of variables of this constraint
      Returns:
        number of variables of this constraint

    - #### countAssignedVariables

          public int countAssignedVariables(Assignment<V,T> assignment)

      The number of variables of this constraint that are assigned
      Parameters:
        `assignment` - current assignment
      Returns:
        number of variables of this constraint that are assigned

    - #### addVariable

          public void addVariable(V variable)

      Add a variable to this constraint
      Parameters:
        `variable` - a variable

    - #### removeVariable

          public void removeVariable(V variable)

      Remove a variable from this constraint
      Parameters:
        `variable` - a variable

    - #### computeConflicts

          public abstract void computeConflicts(Assignment<V,T> assignment,
                                                T value,
                                                Set<T> conflicts)

      The only method which has to be implemented by any constraint. It returns the values which needs to be unassigned in order to make this constraint consistent with the given value if it is assigned to its variable. The computed list of conflicting values is added to the given set of conflicts.
      Parameters:
        `assignment` - current assignment
        `value` - value to be assigned to its variable
        `conflicts` - resultant set of conflicting values

    - #### isConsistent

          public boolean isConsistent(T value1,
                                      T value2)

      Returns true if the given assignments are consistent respecting this constraint. This method is used by MAC (see `MacPropagation`).
      Parameters:
        `value1` - a value
        `value2` - a value
      Returns:
        true if the constraint is ok with the assignment

    - #### inConflict

          public boolean inConflict(Assignment<V,T> assignment,
                                    T value)

      Returns true if the given assignment is inconsistent with the existing assignments respecting this constraint. This method is used by MAC (see `MacPropagation`).
      Parameters:
        `assignment` - current assignment
        `value` - given value
      Returns:
        true if there is a conflict with other assigned variables of the constraint

    - #### assigned

          public void assigned(Assignment<V,T> assignment,
                               long iteration,
                               T value)

      Given value is to be assigned to its variable. In this method, the constraint should unassigns all variables which are in conflict with the given assignment because of this constraint.
      Parameters:
        `assignment` - current assignment
        `iteration` - current iteration
        `value` - assigned value

    - #### computeConflictsNoForwardCheck

          protected void computeConflictsNoForwardCheck(Assignment<V,T> assignment,
                                                        T value,
                                                        Set<T> conflicts)

      Compute conflicts method that does not do any forward checking. This method defaults to `computeConflicts(Assignment, Value, Set)` and it is called during assignment (from `assigned(Assignment, long, Value)`) to check for conflicting variables that need to be unassigned first.
      Parameters:
        `assignment` - current assignment
        `value` - value to be assigned to its variable
        `conflicts` - resultant set of conflicting values

    - #### unassigned

          public void unassigned(Assignment<V,T> assignment,
                                 long iteration,
                                 T value)

      Given value is unassigned from its variable.
      Parameters:
        `assignment` - current assignment
        `iteration` - current iteration
        `value` - unassigned value

    - #### addConstraintListener

          public void addConstraintListener(ConstraintListener<V,T> listener)

      Adds a constraint listener
      Parameters:
        `listener` - a constraint listener

    - #### removeConstraintListener

          public void removeConstraintListener(ConstraintListener<V,T> listener)

      Removes a constraint listener
      Parameters:
        `listener` - a constraint listener

    - #### constraintListeners

          public List<ConstraintListener<V,T>> constraintListeners()

      Returns the list of registered constraint listeners
      Returns:
        a list of currently registered constraint listeners

    - #### getId

          public long getId()

      Unique id
      Returns:
        constraint id

    - #### getName

          public String getName()

      Constraint's name -- for printing purposes
      Returns:
        constraint name

    - #### getDescription

          public String getDescription()

      Constraint's description -- for printing purposes
      Returns:
        constraint description

    - #### hashCode

          public int hashCode()

      Overrides:
        `hashCode` in class `Object`

    - #### isHard

          public boolean isHard()

      Returns true if the constraint is hard. Only hard constraints are allowed to unassign a variable when there is a conflict with a value that is being assigned
      Returns:
        true if the constraint is hard

    - #### equals

          public boolean equals(Object o)

      Compare two constraints for equality (`getId()` is used)
      Overrides:
        `equals` in class `Object`

    - #### compareTo

          public int compareTo(Constraint<V,T> c)

      Specified by:
        `compareTo` in interface `Comparable<Constraint<V extends Variable<V,T>,T extends Value<V,T>>>`