    001    package ifs.model;
    002
    003    import ifs.util.*;
    004    import java.util.*;
    005    import ifs.solver.*;
    006
    007    /**
    008     * Generic model (definition of a problem).
    009     * <br><br>
    010     * It consists of variables and constraints. It has also capability of memorizing the current
    011     * and the best ever found assignment.
    012     * <br><br>
    013     * Example usage:<br><ul><code>
    014     * MyModel model = new MyModel();<br>
    015     * Variable a = new MyVariable("A");<br>
    016     * model.addVariable(a);<br>
    017     * Variable b = new MyVariable("B");<br>
    018     * model.addVariable(b);<br>
    019     * Variable c = new MyVariable("C");<br>
    020     * model.addVariable(c);<br>
    021     * Constraint constr = MyConstraint("all-different");<br>
    022     * model.addConstraint(constr);<br>
    023     * constr.addVariable(a);<br>
    024     * constr.addVariable(b);<br>
    025     * constr.addVariable(c);<br>
    026     * solver.setInitialSolution(model);
    027     * </code></ul>
    028     *
    029     * @see Variable
    030     * @see Constraint
    031     * @see ifs.solution.Solution
    032     * @see ifs.solver.Solver
    033     *
    034     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    035     * @version 1.0
    036     */
    037
    038    public class Model {
    039        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Model.class);
    040        private static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
    041
    042        private Vector iVariables = new FastVector();
    043        private Vector iConstraints = new FastVector();
    044        private Vector iUnassignedVariables = new FastVector();
    045        private Vector iAssignedVariables = new FastVector();
    046
    047        private Vector iPerturbVariables = null;
    048        private Vector iConflictVariables = null;
    049        private Vector iVariablesWithoutInitialValue = null;
    050
    051        private int iBestUnassignedVariables = -1;
    052        private int iBestPerturbations = 0;
    053
    054        /** Constructor */
    055        public Model() {
    056        }
    057
    058        /** The list of variables in the model */
    059        public Vector variables() { return iVariables; }
    060        /** The number of variables in the model */
    061        public int countVariables() { return iVariables.size(); }
    062        /** Adds a variable to the model */
    063        public void addVariable(Variable variable) {
    064            variable.setModel(this);
    065            iVariables.addElement(variable);
    066            if (variable.getAssignment()==null) iUnassignedVariables.addElement(variable);
    067            else iAssignedVariables.addElement(variable);
    068            if (variable.getAssignment()!=null) variable.assign(0L,variable.getAssignment());
    069            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    070                ((ModelListener)e.nextElement()).variableAdded(variable);
    071        }
    072        /** Removes a variable from the model */
    073        public void removeVariable(Variable variable) {
    074            variable.setModel(null);
    075            iVariables.removeElement(variable);
    076            if (iUnassignedVariables.contains(variable)) iUnassignedVariables.removeElement(variable);
    077            if (iAssignedVariables.contains(variable)) iAssignedVariables.removeElement(variable);
    078            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    079                ((ModelListener)e.nextElement()).variableRemoved(variable);
    080        }
    081
    082        /** The list of constraints in the model */
    083        public Vector constraints() { return iConstraints; }
    084        /** The number of constraints in the model */
    085        public int countConstraints() { return iConstraints.size(); }
    086        /** Adds a constraint to the model */
    087        public void addConstraint(Constraint constraint) {
    088            constraint.setModel(this);
    089            iConstraints.addElement(constraint);
    090            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    091                ((ModelListener)e.nextElement()).constraintAdded(constraint);
    092        }
    093        /** Removes a constraint from the model */
    094        public void removeConstraint(Constraint constraint) {
    095            constraint.setModel(null);
    096            iConstraints.removeElement(constraint);
    097            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    098                ((ModelListener)e.nextElement()).constraintRemoved(constraint);
    099        }
    100        /** The list of unassigned variables in the model */
    101        public Vector unassignedVariables() { return iUnassignedVariables; }
    102        /** The list of assigned variables in the model */
    103        public Vector assignedVariables() { return iAssignedVariables; }
    104        /** The list of perturbation variables in the model, i.e., the variables which has an initial value but which are not
    105         * assigned with this value.
    106         */
    107        public Vector perturbVariables() {
    108            if (iPerturbVariables!=null) return iPerturbVariables;
    109            Vector perturbances = new FastVector();
    110            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    111                Variable variable = (Variable)e.nextElement();
    112                if (variable.getInitialAssignment()!=null) {
    113                    if (variable.getAssignment()!=null) {
    114                        if (!variable.getInitialAssignment().equals(variable.getAssignment())) perturbances.addElement(variable);
    115                    } else {
    116                        boolean hasPerturbance = false;
    117                        for (Enumeration x=variable.hardConstraints().elements();!hasPerturbance && x.hasMoreElements();) {
    118                            Constraint constraint = (Constraint)x.nextElement();
    119                            if (constraint.variables().contains(variable) && constraint.inConflict(variable.getInitialAssignment()))
    120                                hasPerturbance=true;
    121                        }
    122                        if (hasPerturbance) perturbances.addElement(variable);
    123                    }
    124                }
    125            }
    126            iPerturbVariables = perturbances;
    127            return perturbances;
    128        }
    129
    130        /** Returns the set of confliction variables with this value, if it is assigned to its variable */
    131        public Set conflictValues(Value value) {
    132            HashSet conflictValues = new HashSet();
    133            for (Enumeration c=value.variable().hardConstraints().elements(); c.hasMoreElements();)
    134                ((Constraint)c.nextElement()).computeConflicts(value, conflictValues);
    135            return conflictValues;
    136        }
    137
    138        /** The list of variales without initial value */
    139        public Vector variablesWithoutInitialValue() {
    140            if (iVariablesWithoutInitialValue!=null) return iVariablesWithoutInitialValue;
    141            Vector variables = new FastVector();
    142            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    143                Variable variable = (Variable)e.nextElement();
    144                if (variable.getInitialAssignment()==null) variables.addElement(variable);
    145            }
    146            iVariablesWithoutInitialValue=variables;
    147            return variables;
    148        }
    149
    150        /** Called before a value is assigned to its variable */
    151        public void beforeAssigned(long iteration, Value value) {
    152            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    153                ((ModelListener)e.nextElement()).beforeAssigned(iteration, value);
    154        }
    155
    156        /** Called before a value is unassigned from its variable */
    157        public void beforeUnassigned(long iteration, Value value) {
    158            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    159                ((ModelListener)e.nextElement()).beforeUnassigned(iteration, value);
    160        }
    161
    162        /** Called after a value is assigned to its variable */
    163        public void afterAssigned(long iteration, Value value) {
    164            iUnassignedVariables.removeElement(value.variable());
    165            iAssignedVariables.addElement(value.variable());
    166            iPerturbVariables = null;
    167            iConflictVariables = null;
    168            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    169                ((ModelListener)e.nextElement()).afterAssigned(iteration, value);
    170        }
    171
    172        /** Called after a value is unassigned from its variable */
    173        public void afterUnassigned(long iteration, Value value) {
    174            iUnassignedVariables.addElement(value.variable());
    175            iAssignedVariables.removeElement(value.variable());
    176            iPerturbVariables = null;
    177            iConflictVariables = null;
    178            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    179                ((ModelListener)e.nextElement()).afterUnassigned(iteration, value);
    180        }
    181
    182        public String toString() {
    183            Collections.sort(variables(), new Comparator() {
    184                public int compare(Object o1, Object o2) {
    185                    Variable v1 = (Variable)o1;
    186                    Variable v2 = (Variable)o2;
    187                    return (v1!=null?v1.getName().compareTo(v2.getName()):(int)(v1.getId()-v2.getId()));
    188                }
    189            });
    190            return "Model{\n    variables="+ToolBox.col2string(variables(),2)+
    191            ",\n    constraints="+ToolBox.col2string(constraints(),2)+
    192            ",\n    #unassigned="+unassignedVariables().size()+
    193            ",\n    unassigned="+ToolBox.col2string(unassignedVariables(),2)+
    194            ",\n    #perturbations="+perturbVariables().size()+"+"+variablesWithoutInitialValue().size()+
    195            ",\n    perturbations="+ToolBox.col2string(perturbVariables(),2)+
    196            ",\n    info="+getInfo()+
    197            (variablesWithoutInitialValue().size()<variables().size()?",\n    withoutInitial="+ToolBox.col2string(variablesWithoutInitialValue(),2):"")+
    198            "\n  }";
    199        }
    200
    201        /** Returns information about the current solution. Information from all model listeners and constraints is also included.
    202         */
    203        public java.util.Hashtable getInfo() {
    204            java.util.Hashtable ret = new java.util.Hashtable();
    205            ret.put("Unassigned variables", unassignedVariables().size()+" / "+variables().size());
    206            ret.put("Perturbation variables (with + without initial value)", perturbVariables().size()+" + "+variablesWithoutInitialValue().size());
    207            ret.put("Total value", new Integer(getTotalValue()));
    208            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
    209                ((ModelListener)e.nextElement()).getInfo(ret);
    210            for (Enumeration e=iConstraints.elements();e.hasMoreElements();)
    211                ((Constraint)e.nextElement()).getInfo(ret);
    212            return ret;
    213        }
    214
    215        /** Returns the number of unassigned variables in the best ever found solution */
    216        public int getBestUnassignedVariables() { return iBestUnassignedVariables; }
    217        /** Returns the number of perturbation variables in the best ever found solution */
    218        public int getBestPerturbations() { return iBestPerturbations; }
    219        /** Save the current assignment as the best ever found assignment */
    220        public void saveBest() {
    221            iBestUnassignedVariables = unassignedVariables().size();
    222            iBestPerturbations = perturbVariables().size();
    223            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    224                Variable variable = (Variable)e.nextElement();
    225                variable.setBestAssignment(variable.getAssignment());
    226            }
    227        }
    228        /** Restore the best ever found assignment into the current assignment*/
    229        public void restoreBest() {
    230            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    231                Variable variable = (Variable)e.nextElement();
    232                variable.unassign(0);
    233            }
    234            HashSet problems = new HashSet();
    235            for (Enumeration e=ToolBox.sortEnumeration(variables().elements(), new BestAssignmentComparator());e.hasMoreElements();) {
    236                Variable variable = (Variable)e.nextElement();
    237                if (variable.getBestAssignment()!=null) {
    238                    Set confs = conflictValues(variable.getBestAssignment());
    239                    if (!confs.isEmpty()) {
    240                        sLogger.error("restore best problem: assignment "+variable.getName()+" = "+variable.getBestAssignment().getName());
    241                        for (Enumeration en=variable.hardConstraints().elements();en.hasMoreElements();) {
    242                            Constraint c=(Constraint)en.nextElement();
    243                            Set x = new HashSet();
    244                            c.computeConflicts(variable.getBestAssignment(),x);
    245                            if (!x.isEmpty()) {
    246                                sLogger.error("  constraint "+c.getName()+" causes the following conflicts "+x);
    247                            }
    248                        }
    249                        problems.add(variable.getBestAssignment());
    250                    } else variable.assign(0,variable.getBestAssignment());
    251                }
    252            }
    253            int attempt = 0;
    254            while (!problems.isEmpty() && attempt<=100) {
    255                attempt++;
    256                Value value = (Value)ToolBox.random(problems); problems.remove(value);
    257                Variable variable = value.variable();
    258                Set confs = conflictValues(value);
    259                if (!confs.isEmpty()) {
    260                    sLogger.error("restore best problem (again, att="+attempt+"): assignment "+variable.getName()+" = "+variable.getBestAssignment().getName());
    261                    for (Enumeration en=variable.hardConstraints().elements();en.hasMoreElements();) {
    262                        Constraint c=(Constraint)en.nextElement();
    263                        Set x = new HashSet();
    264                        c.computeConflicts(value,x);
    265                        if (!x.isEmpty()) sLogger.error("  constraint "+c.getName()+" causes the following conflicts "+x);
    266                    }
    267                    problems.addAll(confs);
    268                }
    269                variable.assign(0,value);
    270            }
    271        }
    272
    273        /** The list of unassigned variables in the best ever found solution*/
    274        public Vector bestUnassignedVariables() {
    275            if (iBestUnassignedVariables<0) return unassignedVariables();
    276            Vector ret = new FastVector(variables().size());
    277            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    278                Variable variable = (Variable)e.nextElement();
    279                if (variable.getBestAssignment()==null) ret.addElement(variable);
    280            }
    281            return ret;
    282        }
    283
    284        /** Value of the current solution. It is the sum of all assigned values, i.e., {@link Value#toInt()}.*/
    285        public int getTotalValue() {
    286            int valCurrent = 0;
    287            for (Enumeration e=assignedVariables().elements();e.hasMoreElements();)
    288                valCurrent += ((Variable)e.nextElement()).getAssignment().toInt();
    289            return valCurrent;
    290        }
    291
    292        private Vector iModelListeners = new FastVector();
    293        /** Adds a model listener */
    294        public void addModelListener(ModelListener listener) {
    295            iModelListeners.addElement(listener);
    296            for (Enumeration e=iConstraints.elements();e.hasMoreElements();)
    297                listener.constraintAdded((Constraint)e.nextElement());
    298            for (Enumeration e=iVariables.elements();e.hasMoreElements();)
    299                listener.variableAdded((Variable)e.nextElement());
    300        }
    301        /** Removes a model listener */
    302        public void removeModelListener(ModelListener listener) {
    303            for (Enumeration e=iVariables.elements();e.hasMoreElements();)
    304                listener.variableRemoved((Variable)e.nextElement());
    305            for (Enumeration e=iConstraints.elements();e.hasMoreElements();)
    306                listener.constraintRemoved((Constraint)e.nextElement());
    307            iModelListeners.removeElement(listener);
    308        }
    309
    310        /** Model initialization */
    311        public boolean init(Solver solver) {
    312            boolean ok = true;
    313            for (Enumeration e=iModelListeners.elements();ok && e.hasMoreElements();)
    314                ok = ((ModelListener)e.nextElement()).init(solver);
    315            return ok;
    316        }
    317        /** The list of model listeners */
    318        public Vector getModelListeners() { return iModelListeners; }
    319        /** The list of model listeners that are of the given class*/
    320        public ModelListener modelListenerOfType(Class type) {
    321            for (Enumeration e=iModelListeners.elements();e.hasMoreElements();) {
    322                ModelListener listener = (ModelListener)e.nextElement();
    323                if (listener.getClass() == type) return listener;
    324            }
    325            return null;
    326        }
    327        /** The list of constraints which are in a conflict with the given value if it is assigned to its variable.
    328         * This means the constraints, which adds a value into the set of conflicting values in {@link Constraint#computeConflicts(Value, Set)}.
    329         */
    330        public Hashtable conflictConstraints(Value value) {
    331            Hashtable conflictConstraints = new Hashtable();
    332            for (Enumeration c=value.variable().hardConstraints().elements(); c.hasMoreElements();) {
    333                Constraint constraint = (Constraint)c.nextElement();
    334                HashSet conflicts = new HashSet();
    335                constraint.computeConflicts(value, conflicts);
    336                if (conflicts!=null && !conflicts.isEmpty()) {
    337                    conflictConstraints.put(constraint,conflicts);
    338                }
    339            }
    340            return conflictConstraints;
    341        }
    342        /** The list of hard constraints which contain at least one variable that is not assigned. */
    343        public Vector unassignedHardConstraints() {
    344            Vector ret = new FastVector();
    345            for (Enumeration c=constraints().elements();c.hasMoreElements();) {
    346                Constraint constraint = (Constraint)c.nextElement();
    347                if (!constraint.isHard()) continue;
    348                boolean assigned = true;
    349                for (Enumeration v=constraint.variables().elements();assigned && v.hasMoreElements();)
    350                    if (((Variable)v.nextElement()).getAssignment()==null) assigned=false;
    351                if (!assigned)
    352                    ret.addElement(constraint);
    353            }
    354            return ret;
    355        }
    356
    357        private class BestAssignmentComparator implements Comparator {
    358            public int compare(Object o1, Object o2) {
    359                Variable v1=(Variable)o1;
    360                Variable v2=(Variable)o2;
    361                return (int)(v1.getBestAssignmentIteration()-v2.getBestAssignmentIteration());
    362            }
    363        }
    364    }