    001package org.cpsolver.ifs.model;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashSet;
    006import java.util.List;
    007import java.util.Set;
    008
    009import org.cpsolver.ifs.assignment.Assignment;
    010import org.cpsolver.ifs.util.IdGenerator;
    011
    012
    013/**
    014 * Generic constraint. <br>
    015 * <br>
    016 * Like in other traditional Constraint Logic Programming (CLP) frameworks, the
    017 * input problem consists of variables, values and constraints. Each constraint
    018 * is defined over a subset of the problem variables and it prohibits some
    019 * combinations of values which these variables can simultaneously take. In
    020 * usual CSP problems, all constraints are binary (or the problem is transformed
    021 * into an equivalent problem with only binary constrains before the search is
    022 * started) since most of the consistency and filtering techniques are designed
    023 * only for binary constraints. In such a case, the procedure computing
    024 * conflicting variables is rather simple and it returns an unambiguous set of
    025 * variables. It enumerates all the constraints which contain the selected
    026 * variable and which are not consistent with the selected value. It returns all
    027 * the variables of such constraints, different from the selected variable. <br>
    028 * <br>
    029 * On the other hand, most of real problems have plenty of multi-variable
    030 * constraints, like, for instance, resource constraint in timetabling. Such
    031 * resource constraint enforces the rule that none of the variables which are
    032 * using the given resource can be overlapping in time (if the resource has
    033 * capacity one) or that the amount of the resource used at a time does not
    034 * exceed its capacity. It is not very useful to replace such resource
    035 * constraint by a set of binary constraints (e.g., prohibiting two overlapping
    036 * placements in time of two particular events using the same resource), since
    037 * this approach usually ends up with thousands of constraints. Also, there is
    038 * usually a much more effective consistency and/or filtering technique working
    039 * with the original constraint (for instance, "cumulative" constraint is
    040 * usually used for modelling resource constraints in CLP). <br>
    041 * <br>
    042 * Using multi-variable constraints, the set of conflicting variables returned
    043 * by the procedure computing conflicting variables can differ according to its
    044 * implementation. For instance, we can have a constraint A+B=C where A and C is
    045 * already assigned to A=3 and C=5. Then if the assignment B=3 is selected,
    046 * either A or B or both A and B can be unassigned to make the problem {A=3,
    047 * B=3, C=5} consistent with the constraint A+B=C. Intuitively, there should be
    048 * minimal number of variables unassigned in each iteration step (we are trying
    049 * to increase the number of the assigned variables during the search). Also,
    050 * for many constraints, it is possible to find inconsistencies even when not
    051 * all variables of the constraint are yet assigned. For instance, if there are
    052 * two lectures using the same room at the same time, we know that one of them
    053 * needs to be unassigned even when there are unassigned lectures which will
    054 * also need to be placed in that room. <br>
    055 * <br>
    056 * In the current implementation, each hard constraint needs to implement the
    057 * procedure {@link Constraint#computeConflicts(Assignment, Value, Set)} which returns all
    058 * the already assigned values that are incompatible we the selected assignment
    059 * (value which is to be assigned to its variable). This procedure is called for
    060 * all constraints which contain the selected variable in an ordered manner.
    061 * Furthermore, this order can be changed during the search. Moreover, the
    062 * computed set of conflicting variables is passed to this
    063 * {@link Constraint#computeConflicts(Assignment, Value, Set)} procedure as a parameter, so
    064 * the constraint can "see" what variables are already selected for unassignment
    065 * by previously processed constraints. This way, we are not computing the very
    066 * minimal set of conflicting variables, however, we allow for computing this
    067 * set in an efficient way. It can be also tuned for a particular problem by
    068 * changing the order of constraints. <br>
    069 * <br>
    070 * Also note that each constraint can keep its notion about the assigned
    071 * variables. For instance, the resource constraint of a particular room can
    072 * memorize a look-up table stating what lecture is assigned in what time
    073 * slot(s), so for the computation of the conflicting lectures it only looks
    074 * through the appropriate fields of this table. The implementation is based on
    075 * {@link Constraint#assigned(Assignment,long,Value)} and
    076 * {@link Constraint#unassigned(Assignment,long,Value)} methods that are responsible to
    077 * keeping the problem consistent with the constraint. Also note that this
    078 * default consistency technique is defined on a problem level and it can be
    079 * changed by a more dedicated one, implemented for a particular problem.
    080 *
    081 * @see Variable
    082 * @see Model
    083 * @see org.cpsolver.ifs.solver.Solver
    084 *
    085 * @author  Tomáš Müller
    086 * @version IFS 1.3 (Iterative Forward Search)<br>
    087 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    088 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    089 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    090 * <br>
    091 *          This library is free software; you can redistribute it and/or modify
    092 *          it under the terms of the GNU Lesser General Public License as
    093 *          published by the Free Software Foundation; either version 3 of the
    094 *          License, or (at your option) any later version. <br>
    095 * <br>
    096 *          This library is distributed in the hope that it will be useful, but
    097 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    098 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    099 *          Lesser General Public License for more details. <br>
    100 * <br>
    101 *          You should have received a copy of the GNU Lesser General Public
    102 *          License along with this library; if not see
    103 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    104 * @param <V> Variable
    105 * @param <T> Value
    106 */
    107
    108public abstract class Constraint<V extends Variable<V, T>, T extends Value<V, T>> implements Comparable<Constraint<V, T>> {
    109    private static IdGenerator iIdGenerator = new IdGenerator();
    110
    111    protected long iId = -1;
    112
    113    private List<V> iVariables = new ArrayList<V>();
    114    private Model<V, T> iModel = null;
    115    protected List<ConstraintListener<V, T>> iConstraintListeners = null;
    116
    117    /** Constructor */
    118    public Constraint() {
    119        iId = iIdGenerator.newId();
    120    }
    121
    122    /** The model which the constraint belongs to
    123     * @return problem model
    124     **/
    125    public Model<V, T> getModel() {
    126        return iModel;
    127    }
    128
    129    /** Sets the model which the constraint belongs to
    130     * @param model problem model
    131     **/
    132    public void setModel(Model<V, T> model) {
    133        iModel = model;
    134    }
    135
    136    /** The list of variables of this constraint
    137     * @return variables of this constraint
    138     **/
    139    public List<V> variables() {
    140        return iVariables;
    141    }
    142
    143    /** The list of variables of this constraint that are assigned
    144     * @param assignment current assignment
    145     * @return assigned variables of this constraint
    146     **/
    147    public Collection<V> assignedVariables(Assignment<V, T> assignment) {
    148        List<V> assigned = new ArrayList<V>();
    149        for (V v: variables())
    150            if (assignment.getValue(v) != null)
    151                assigned.add(v);
    152        return assigned;
    153    }
    154
    155    /** The number of variables of this constraint
    156     * @return number of variables of this constraint
    157     **/
    158    public int countVariables() {
    159        return variables().size();
    160    }
    161
    162    /** The number of variables of this constraint that are assigned
    163     * @param assignment current assignment
    164     * @return number of variables of this constraint that are assigned
    165     **/
    166    public int countAssignedVariables(Assignment<V, T> assignment) {
    167        return assignedVariables(assignment).size();
    168    }
    169
    170    /** Add a variable to this constraint
    171     * @param variable a variable
    172     **/
    173    public void addVariable(V variable) {
    174        iVariables.add(variable);
    175        variable.addContstraint(this);
    176    }
    177
    178    /** Remove a variable from this constraint
    179     * @param variable a variable
    180     **/
    181    public void removeVariable(V variable) {
    182        variable.removeContstraint(this);
    183        iVariables.remove(variable);
    184    }
    185
    186    /**
    187     * The only method which has to be implemented by any constraint. It returns
    188     * the values which needs to be unassigned in order to make this constraint
    189     * consistent with the given value if it is assigned to its variable. The
    190     * computed list of conflicting values is added to the given set of
    191     * conflicts.
    192     * @param assignment current assignment
    193     * @param value value to be assigned to its variable
    194     * @param conflicts resultant set of conflicting values
    195     */
    196    public abstract void computeConflicts(Assignment<V, T> assignment, T value, Set<T> conflicts);
    197
    198    /**
    199     * Returns true if the given assignments are consistent respecting this
    200     * constraint. This method is used by MAC (see
    201     * {@link org.cpsolver.ifs.extension.MacPropagation}).
    202     * @param value1 a value
    203     * @param value2 a value
    204     * @return true if the constraint is ok with the assignment
    205     */
    206    public boolean isConsistent(T value1, T value2) {
    207        return true;
    208    }
    209
    210    /**
    211     * Returns true if the given assignment is inconsistent with the existing
    212     * assignments respecting this constraint. This method is used by MAC (see
    213     * {@link org.cpsolver.ifs.extension.MacPropagation}).
    214     * @param assignment current assignment
    215     * @param value given value
    216     * @return true if there is a conflict with other assigned variables of the constraint
    217     */
    218    public boolean inConflict(Assignment<V, T> assignment, T value) {
    219        Set<T> conflicts = new HashSet<T>();
    220        computeConflicts(assignment, value, conflicts);
    221        return !conflicts.isEmpty();
    222    }
    223
    224    /**
    225     * Given value is to be assigned to its variable. In this method, the
    226     * constraint should unassigns all variables which are in conflict with the
    227     * given assignment because of this constraint.
    228     * @param assignment current assignment
    229     * @param iteration current iteration
    230     * @param value assigned value
    231     */
    232    public void assigned(Assignment<V, T> assignment, long iteration, T value) {
    233        Set<T> conf = null;
    234        if (isHard()) {
    235            conf = new HashSet<T>();
    236            computeConflictsNoForwardCheck(assignment, value, conf);
    237        }
    238        if (iConstraintListeners != null)
    239            for (ConstraintListener<V, T> listener : iConstraintListeners)
    240                listener.constraintBeforeAssigned(assignment, iteration, this, value, conf);
    241        if (conf != null) {
    242            for (T conflictValue : conf) {
    243                if (!conflictValue.equals(value))
    244                    assignment.unassign(iteration, conflictValue.variable());
    245            }
    246        }
    247        if (iConstraintListeners != null)
    248            for (ConstraintListener<V, T> listener : iConstraintListeners)
    249                listener.constraintAfterAssigned(assignment, iteration, this, value, conf);
    250    }
    251
    252    /**
    253     * Compute conflicts method that does not do any forward checking. This method defaults to {@link Constraint#computeConflicts(Assignment, Value, Set)}
    254     * and it is called during assignment (from {@link Constraint#assigned(Assignment, long, Value)}) to check for conflicting variables that need to be
    255     * unassigned first.
    256     * @param assignment current assignment
    257     * @param value value to be assigned to its variable
    258     * @param conflicts resultant set of conflicting values
    259     */
    260    protected void computeConflictsNoForwardCheck(Assignment<V, T> assignment, T value, Set<T> conflicts) {
    261        computeConflicts(assignment, value, conflicts);
    262    }
    263
    264    /**
    265     * Given value is unassigned from its variable.
    266     * @param assignment current assignment
    267     * @param iteration current iteration
    268     * @param value unassigned value
    269     */
    270    public void unassigned(Assignment<V, T> assignment, long iteration, T value) {
    271    }
    272
    273    /** Adds a constraint listener
    274     * @param listener a constraint listener
    275     **/
    276    public void addConstraintListener(ConstraintListener<V, T> listener) {
    277        if (iConstraintListeners == null)
    278            iConstraintListeners = new ArrayList<ConstraintListener<V, T>>();
    279        iConstraintListeners.add(listener);
    280    }
    281
    282    /** Removes a constraint listener
    283     * @param listener a constraint listener
    284     **/
    285    public void removeConstraintListener(ConstraintListener<V, T> listener) {
    286        if (iConstraintListeners != null)
    287            iConstraintListeners.remove(listener);
    288    }
    289
    290    /** Returns the list of registered constraint listeners
    291     * @return a list of currently registered constraint listeners
    292     **/
    293    public List<ConstraintListener<V, T>> constraintListeners() {
    294        return iConstraintListeners;
    295    }
    296
    297    /** Unique id
    298     * @return constraint id
    299     **/
    300    public long getId() {
    301        return iId;
    302    }
    303
    304    /** Constraint's name -- for printing purposes
    305     * @return constraint name
    306     **/
    307    public String getName() {
    308        return String.valueOf(iId);
    309    }
    310
    311    /** Constraint's description -- for printing purposes
    312     * @return constraint description
    313     **/
    314    public String getDescription() {
    315        return null;
    316    }
    317
    318    @Override
    319    public int hashCode() {
    320        return (int) iId;
    321    }
    322
    323    /**
    324     * Returns true if the constraint is hard. Only hard constraints are allowed
    325     * to unassign a variable when there is a conflict with a value that is
    326     * being assigned
    327     * @return true if the constraint is hard
    328     */
    329    public boolean isHard() {
    330        return true;
    331    }
    332
    333    /**
    334     * Compare two constraints for equality ({@link Constraint#getId()} is used)
    335     */
    336    @Override
    337    public boolean equals(Object o) {
    338        if (o == null || !(o instanceof Constraint<?, ?>))
    339            return false;
    340        return getId() == ((Constraint<?, ?>) o).getId();
    341    }
    342
    343    @Override
    344    public int compareTo(Constraint<V, T> c) {
    345        return (getId() < c.getId() ? -1 : getId() == c.getId() ? 0 : 1);
    346    }
    347}