    001    package ifs.model;
    002
    003    import ifs.util.*;
    004    import java.util.*;
    005
    006    /**
    007     * Generic constraint.
    008     * <br><br>
    009     * Like in other traditional Constraint Logic Programming (CLP) frameworks, the input problem consists of variables,
    010     * values and constraints. Each constraint is defined over a subset of the problem variables and it prohibits some
    011     * combinations of values which these variables can simultaneously take. In usual CSP problems, all constraints are
    012     * binary (or the problem is transformed into an equivalent problem with only binary constrains before the search is
    013     * started) since most of the consistency and filtering techniques are designed only for binary constraints.
    014     * In such a case, the procedure computing conflicting variables is rather simple and it returns an unambiguous set of
    015     * variables. It enumerates all the constraints which contain the selected variable and which are not consistent with
    016     * the selected value. It returns all the variables of such constraints, different from the selected variable.
    017     * <br><br>
    018     * On the other hand, most of real problems have plenty of multi-variable constraints, like, for instance, resource
    019     * constraint in timetabling. Such resource constraint enforces the rule that none of the variables which are using
    020     * the given resource can be overlapping in time (if the resource has capacity one) or that the amount of the resource
    021     * used at a time does not exceed its capacity. It is not very useful to replace such resource constraint by a set of
    022     * binary constraints (e.g., prohibiting two overlapping placements in time of two particular events using the same
    023     * resource), since this approach usually ends up with thousands of constraints. Also, there is usually a much more
    024     * effective consistency and/or filtering technique working with the original constraint (for instance, "cumulative"
    025     * constraint is usually used for modelling resource constraints in CLP).
    026     * <br><br>
    027     * Using multi-variable constraints, the set of conflicting variables returned by the procedure computing conflicting
    028     * variables can differ according to its implementation. For instance, we can have a constraint A+B=C where A and C
    029     * 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
    030     * unassigned to make the problem {A=3, B=3, C=5} consistent with the constraint A+B=C. Intuitively, there should be
    031     * minimal number of variables unassigned in each iteration step (we are trying to increase the number of the
    032     * assigned variables during the search). Also, for many constraints, it is possible to find inconsistencies even
    033     * when not all variables of the constraint are yet assigned. For instance, if there are two lectures using the
    034     * same room at the same time, we know that one of them needs to be unassigned even when there are unassigned lectures
    035     * which will also need to be placed in that room.
    036     * <br><br>
    037     * In the current implementation, each hard constraint needs to implement the procedure
    038     * {@link Constraint#computeConflicts(Value, Set)} which returns all the already assigned values that are incompatible we
    039     * the selected assignment (value which is to be assigned to its variable). This procedure is called for all constraints
    040     * which contain the selected variable in an ordered manner. Furthermore, this order can be changed during the search.
    041     * Moreover, the computed set of conflicting variables is passed to this {@link Constraint#computeConflicts(Value, Set)}
    042     * procedure as a parameter, so the constraint can "see" what variables are already selected for unassignment by
    043     * previously processed constraints. This way, we are not computing the very minimal set of conflicting variables,
    044     * however, we allow for computing this set in an efficient way. It can be also tuned for a particular problem by
    045     * changing the order of constraints.
    046     * <br><br>
    047     * Also note that each constraint can keep its notion about the assigned variables. For instance, the resource
    048     * constraint of a particular room can memorize a look-up table stating what lecture is assigned in what time slot(s),
    049     * so for the computation of the conflicting lectures it only looks through the appropriate fields of this table. The
    050     * implementation is based on {@link Constraint#assigned(long,Value)} and {@link Constraint#unassigned(long,Value)}
    051     * methods that are responsible to keeping the problem consistent with the constraint. Also note that this default
    052     * consistency technique is defined on a problem level and it can be changed by a more dedicated one, implemented for a
    053     * particular problem.
    054     *
    055     * @see Variable
    056     * @see Model
    057     * @see ifs.solver.Solver
    058     *
    059     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    060     * @version 1.0
    061     */
    062
    063    public abstract class Constraint {
    064        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Constraint.class);
    065        private static IdGenerator iIdGenerator = new IdGenerator();
    066
    067        private long iId = -1;
    068
    069        private Vector iVariables = new FastVector();
    070        private Vector iAssignedVariables = new FastVector();
    071        private Model iModel = null;
    072        private Vector iConstraintListeners = null;
    073
    074        /** Constructor */
    075        public Constraint() {
    076            iId = iIdGenerator.newId();
    077        }
    078
    079        /** The model which the constraint belongs to */
    080        public Model getModel() {return iModel; }
    081        /** Sets the model which the constraint belongs to */
    082        public void setModel(Model model) { iModel=model; }
    083        /** The list of variables of this constraint */
    084        public Vector variables() { return iVariables; }
    085        /** The list of variables of this constraint that are assigned */
    086        public Vector assignedVariables() { return iAssignedVariables; }
    087        /** The number of variables of this constraint */
    088        public int countVariables() { return iVariables.size(); }
    089        /** The number of variables of this constraint that are assigned */
    090        public int countAssignedVariables() { return iAssignedVariables.size(); }
    091
    092        /** Add a variable to this constraint */
    093        public void addVariable(Variable variable) {
    094            iVariables.addElement(variable);
    095            variable.addContstraint(this);
    096            if (variable.getAssignment()!=null) {
    097                this.assigned(0,variable.getAssignment());
    098                iAssignedVariables.addElement(variable);
    099            }
    100        }
    101        /** Remove a variable from this constraint */
    102        public void removeVariable(Variable variable) {
    103            variable.removeContstraint(this);
    104            iVariables.removeElement(variable);
    105            if (iAssignedVariables.contains(variable)) iAssignedVariables.removeElement(variable);
    106        }
    107
    108        /** The only method which has to be implemented by any constraint. It returns the
    109         * values which needs to be unassigned in order to make this constraint consistent
    110         * with the given value if it is assigned to its variable. The computed list of
    111         * conflicting values is added to the given set of conflicts.
    112         * @param value value to be assigned to its varaible
    113         * @param conflicts resultant set of conflicting values
    114         */
    115        public abstract void computeConflicts(Value value, Set conflicts);
    116
    117        /** Returns true if the given assignments are consistent respecting this constraint.
    118         * This method is used by MAC (see {@link ifs.extension.MacPropagation}). */
    119        public boolean isConsistent(Value value1, Value value2) {
    120            return true;
    121        }
    122
    123        /** Returns true if the given assignment is inconsistent with the existing assignments
    124         * respecting this constraint. This method is used by MAC (see {@link ifs.extension.MacPropagation}).
    125         */
    126        public boolean inConflict(Value value) {
    127            Set conflicts = new HashSet();
    128            computeConflicts(value, conflicts);
    129            return !conflicts.isEmpty();
    130        }
    131
    132        /** Given value is to be assigned to its varable. In this method, the constraint should unassigns
    133         * all varaibles which are in conflict with the given assignment because of this constraint.
    134         */
    135        public void assigned(long iteration, Value value) {
    136            HashSet conf = null;
    137            if (isHard()) {
    138                conf = new HashSet(); computeConflicts(value, conf);
    139            }
    140            if (iConstraintListeners!=null)
    141                for (Enumeration e=iConstraintListeners.elements();e.hasMoreElements();)
    142                    ((ConstraintListener)e.nextElement()).constraintBeforeAssigned(iteration, this, value, conf);
    143            if (conf!=null) {
    144                for (Iterator i=conf.iterator(); i.hasNext(); ) {
    145                    Value conflictValue = (Value)i.next();
    146                    conflictValue.variable().unassign(iteration);
    147                }
    148            }
    149            iAssignedVariables.addElement(value.variable());
    150            if (iConstraintListeners!=null)
    151                for (Enumeration e=iConstraintListeners.elements();e.hasMoreElements();)
    152                    ((ConstraintListener)e.nextElement()).constraintAfterAssigned(iteration, this, value, conf);
    153        }
    154
    155        /** Given value is unassigned from its varable.
    156         */
    157        public void unassigned(long iteration, Value value) {
    158            iAssignedVariables.removeElement(value.variable());
    159        }
    160
    161        /** Adds a constraint listener */
    162        public void addConstraintListener(ConstraintListener listener) {
    163            if (iConstraintListeners==null) iConstraintListeners=new FastVector();
    164            iConstraintListeners.addElement(listener);
    165        }
    166        /** Removes a constraint listener */
    167        public void removeConstraintListener(ConstraintListener listener) {
    168            if (iConstraintListeners==null) iConstraintListeners=new FastVector();
    169            iConstraintListeners.removeElement(listener);
    170        }
    171
    172        /** Unique id */
    173        public long getId() { return iId;}
    174        /** Constraint's name -- for printing purposes */
    175        public String getName() { return String.valueOf(iId); }
    176        /** Constraint's description -- for printing purposes */
    177        public String getDescription() { return null; }
    178        public int hashCode() { return (int)iId; }
    179        /** Returns true if the constraint is hard. Only hard constraints are allowed to
    180         * unassign a variable when there is a conflict with a value that is being assigned */
    181        public boolean isHard() { return true; }
    182        /** Adds some information into the table with information about the solution */
    183        public void getInfo(Dictionary info) {};
    184    }