001package org.cpsolver.ifs.model;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.Collections;
006import java.util.Comparator;
007import java.util.HashSet;
008import java.util.HashMap;
009import java.util.List;
010import java.util.Locale;
011import java.util.Map;
012import java.util.Set;
013import java.util.TreeSet;
014import java.util.concurrent.locks.ReentrantReadWriteLock;
015
016import org.cpsolver.coursett.criteria.TimetablingCriterion;
017import org.cpsolver.ifs.assignment.Assignment;
018import org.cpsolver.ifs.assignment.DefaultInheritedAssignment;
019import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
020import org.cpsolver.ifs.assignment.EmptyAssignment;
021import org.cpsolver.ifs.assignment.InheritedAssignment;
022import org.cpsolver.ifs.assignment.context.AssignmentContext;
023import org.cpsolver.ifs.assignment.context.AssignmentContextReference;
024import org.cpsolver.ifs.assignment.context.HasAssignmentContext;
025import org.cpsolver.ifs.criteria.Criterion;
026import org.cpsolver.ifs.solution.Solution;
027import org.cpsolver.ifs.solver.Solver;
028import org.cpsolver.ifs.util.ToolBox;
029
030
031/**
032 * Generic model (definition of a problem). <br>
033 * <br>
034 * It consists of variables and constraints. It has also capability of
035 * memorizing the current and the best ever found assignment. <br>
036 * <br>
037 * Example usage:<br>
038 * <pre>
039 * <code>
040 * MyModel model = new MyModel();
041 * Variable a = new MyVariable("A");
042 * model.addVariable(a);
043 * Variable b = new MyVariable("B");
044 * model.addVariable(b);
045 * Variable c = new MyVariable("C");
046 * model.addVariable(c);
047 * Constraint constr = MyConstraint("all-different");
048 * model.addConstraint(constr);
049 * constr.addVariable(a);
050 * constr.addVariable(b);
051 * constr.addVariable(c);
052 * solver.setInitialSolution(model);
053 * </code>
054 * </pre>
055 * 
056 * @see Variable
057 * @see Constraint
058 * @see org.cpsolver.ifs.solution.Solution
059 * @see org.cpsolver.ifs.solver.Solver
060 * 
061 * @version IFS 1.3 (Iterative Forward Search)<br>
062 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
063 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
064 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
065 * <br>
066 *          This library is free software; you can redistribute it and/or modify
067 *          it under the terms of the GNU Lesser General Public License as
068 *          published by the Free Software Foundation; either version 3 of the
069 *          License, or (at your option) any later version. <br>
070 * <br>
071 *          This library is distributed in the hope that it will be useful, but
072 *          WITHOUT ANY WARRANTY; without even the implied warranty of
073 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
074 *          Lesser General Public License for more details. <br>
075 * <br>
076 *          You should have received a copy of the GNU Lesser General Public
077 *          License along with this library; if not see
078 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
079 * 
080 * @param <V> Variable 
081 * @param <T> Value
082 */
083public class Model<V extends Variable<V, T>, T extends Value<V, T>> {
084    private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(Model.class);
085    protected static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00",
086            new java.text.DecimalFormatSymbols(Locale.US));
087    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
088            new java.text.DecimalFormatSymbols(Locale.US));
089    protected static java.text.DecimalFormat sPercentageFormat = new java.text.DecimalFormat("0.00",
090            new java.text.DecimalFormatSymbols(Locale.US));
091
092    private List<V> iVariables = new ArrayList<V>();
093    private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>();
094    private List<GlobalConstraint<V, T>> iGlobalConstraints = new ArrayList<GlobalConstraint<V, T>>();
095    private Collection<V> iVariablesWithInitialValueCache = null;
096    private final ReentrantReadWriteLock iVariablesWithInitialValueLock = new ReentrantReadWriteLock();
097
098    private List<ModelListener<V, T>> iModelListeners = new ArrayList<ModelListener<V, T>>();
099    private List<InfoProvider<V, T>> iInfoProviders = new ArrayList<InfoProvider<V, T>>();
100    private HashMap<String, Criterion<V, T>> iCriteria = new HashMap<String, Criterion<V,T>>();
101
102    private int iBestUnassignedVariables = -1;
103    private int iBestPerturbations = 0;
104    private double iBestValue = 0.0;
105    private int iNextReferenceId = 0;
106    private int iNextVariableIndex = 0;
107    @Deprecated
108    private Assignment<V, T> iAssignment = null;
109    private Assignment<V, T> iEmptyAssignment = null;
110    private Map<Integer, AssignmentContextReference<V, T, ? extends AssignmentContext>> iAssignmentContextReferences = new HashMap<Integer, AssignmentContextReference<V, T, ? extends AssignmentContext>>();
111    
112    /** Constructor */
113    public Model() {
114    }
115
116    /** The list of variables in the model 
117     * @return list of variables in the model
118     **/
119    public List<V> variables() {
120        return iVariables;
121    }
122
123    /** The number of variables in the model
124     * @return number of variables in the model
125     **/
126    public int countVariables() {
127        return iVariables.size();
128    }
129
130    /** Adds a variable to the model
131     * @param variable a variable
132     **/
133    @SuppressWarnings("unchecked")
134    public void addVariable(V variable) {
135        variable.setModel(this);
136        variable.setIndex(iNextVariableIndex++);
137        iVariables.add(variable);
138        if (variable instanceof InfoProvider<?, ?>)
139            iInfoProviders.add((InfoProvider<V, T>) variable);
140        for (ModelListener<V, T> listener : iModelListeners)
141            listener.variableAdded(variable);
142        invalidateVariablesWithInitialValueCache();
143    }
144
145    /** Removes a variable from the model
146     * @param variable a variable
147     **/
148    @SuppressWarnings("unchecked")
149    public void removeVariable(V variable) {
150        variable.setModel(null);
151        iVariables.remove(variable);
152        if (variable instanceof InfoProvider<?, ?>)
153            iInfoProviders.remove((InfoProvider<?, ?>)variable);
154        for (ModelListener<V, T> listener : iModelListeners)
155            listener.variableRemoved(variable);
156        invalidateVariablesWithInitialValueCache();
157        if (variable instanceof HasAssignmentContext)
158            removeReference((HasAssignmentContext<V, T, ?>)variable);
159    }
160
161    /** The list of constraints in the model
162     * @return list of constraints in the model
163     **/
164    public List<Constraint<V, T>> constraints() {
165        return iConstraints;
166    }
167
168    /** The number of constraints in the model
169     * @return number of constraints in the model
170     **/
171    public int countConstraints() {
172        return iConstraints.size();
173    }
174
175    /** Adds a constraint to the model
176     * @param constraint a constraint 
177     **/
178    @SuppressWarnings("unchecked")
179    public void addConstraint(Constraint<V, T> constraint) {
180        constraint.setModel(this);
181        iConstraints.add(constraint);
182        if (constraint instanceof InfoProvider<?, ?>)
183            iInfoProviders.add((InfoProvider<V, T>) constraint);
184        for (ModelListener<V, T> listener : iModelListeners)
185            listener.constraintAdded(constraint);
186    }
187
188    /** Removes a constraint from the model
189     * @param constraint a constraint
190     **/
191    @SuppressWarnings("unchecked")
192    public void removeConstraint(Constraint<V, T> constraint) {
193        constraint.setModel(null);
194        iConstraints.remove(constraint);
195        if (constraint instanceof InfoProvider<?, ?>)
196            iInfoProviders.remove((InfoProvider<?, ?>)constraint);
197        for (ModelListener<V, T> listener : iModelListeners)
198            listener.constraintRemoved(constraint);
199        if (constraint instanceof HasAssignmentContext)
200            removeReference((HasAssignmentContext<V, T, ?>)constraint);
201    }
202
203    /** The list of global constraints in the model
204     * @return  list of global constraints in the model
205     **/
206    public List<GlobalConstraint<V, T>> globalConstraints() {
207        return iGlobalConstraints;
208    }
209
210    /** The number of global constraints in the model
211     * @return number of global constraints in the model
212     **/
213    public int countGlobalConstraints() {
214        return iGlobalConstraints.size();
215    }
216
217    /** Adds a global constraint to the model
218     * @param constraint a global constraint
219     **/
220    @SuppressWarnings("unchecked")
221    public void addGlobalConstraint(GlobalConstraint<V, T> constraint) {
222        constraint.setModel(this);
223        iGlobalConstraints.add(constraint);
224        if (constraint instanceof InfoProvider<?, ?>)
225            iInfoProviders.add((InfoProvider<V, T>) constraint);
226        for (ModelListener<V, T> listener : iModelListeners)
227            listener.constraintAdded(constraint);
228        if (constraint instanceof ModelListener<?, ?>)
229            iModelListeners.add((ModelListener<V, T>) constraint);
230    }
231
232    /** Removes a global constraint from the model
233     * @param constraint a global constraint 
234     **/
235    @SuppressWarnings("unchecked")
236    public void removeGlobalConstraint(GlobalConstraint<V, T> constraint) {
237        constraint.setModel(null);
238        iGlobalConstraints.remove(constraint);
239        if (constraint instanceof InfoProvider<?, ?>)
240            iInfoProviders.remove((InfoProvider<?, ?>) constraint);
241        if (constraint instanceof ModelListener<?, ?>)
242            iModelListeners.remove((ModelListener<V, T>) constraint);
243        for (ModelListener<V, T> listener : iModelListeners)
244            listener.constraintRemoved(constraint);
245        if (constraint instanceof HasAssignmentContext)
246            removeReference((HasAssignmentContext<V, T, ?>)constraint);
247    }
248
249    /**
250     * The list of unassigned variables in the model.
251     * Use {@link Model#unassignedVariables(Assignment)} or {@link Assignment#unassignedVariables(Model)} instead.
252     * @return list of unassigned variables in the model
253     **/
254    @Deprecated
255    public Collection<V> unassignedVariables() {
256        return unassignedVariables(getDefaultAssignment());
257    }
258
259    /** The list of unassigned variables in the model
260     * @param assignment current assignment
261     * @return list of unassigned variables in the model
262     **/
263    public Collection<V> unassignedVariables(Assignment<V, T> assignment) {
264        return assignment.unassignedVariables(this);
265    }
266
267    /**
268     * Number of unassigned variables.
269     * Use {@link Model#nrUnassignedVariables(Assignment)} or {@link Assignment#nrUnassignedVariables(Model)} instead.
270     * @return number of unassigned variables in the model
271     **/
272    @Deprecated
273    public int nrUnassignedVariables() {
274        return nrUnassignedVariables(getDefaultAssignment());
275    }
276
277    /** Number of unassigned variables
278     * @param assignment current assignment
279     * @return number of unassigned variables in the model
280     **/
281    public int nrUnassignedVariables(Assignment<V, T> assignment) {
282        return assignment.nrUnassignedVariables(this);
283    }
284
285    /**
286     * The list of assigned variables in the model.
287     * Use {@link Model#assignedVariables(Assignment)} or {@link Assignment#assignedVariables()} instead.
288     * @return list of assigned variables in the model
289     **/
290    @Deprecated
291    public Collection<V> assignedVariables() {
292        return assignedVariables(getDefaultAssignment());
293    }
294    
295    /** The list of assigned variables in the model
296     * @param assignment current assignment
297     * @return list of assigned variables in the model
298     **/
299    public Collection<V> assignedVariables(Assignment<V, T> assignment) {
300        return assignment.assignedVariables();
301    }
302
303    /**
304     * Number of assigned variables.
305     * Use {@link Model#nrAssignedVariables(Assignment)} or {@link Assignment#nrAssignedVariables()} instead.
306     * @return number of assigned variables in the model
307     **/
308    @Deprecated
309    public int nrAssignedVariables() {
310        return nrAssignedVariables(getDefaultAssignment());
311    }
312    
313    /** Number of assigned variables
314     * @param assignment current assignment
315     * @return number of assigned variables in the model
316     **/
317    public int nrAssignedVariables(Assignment<V, T> assignment) {
318        return assignment.nrAssignedVariables();
319    }
320
321    /**
322     * The list of perturbation variables in the model, i.e., the variables
323     * which has an initial value but which are not assigned with this value.
324     * Use {@link Model#perturbVariables(Assignment)} instead.
325     * @return list of perturbation variables in the model
326     */
327    @Deprecated
328    public Collection<V> perturbVariables() {
329        return perturbVariables(getDefaultAssignment(), variablesWithInitialValue());
330    }
331    
332    /**
333     * The list of perturbation variables in the model, i.e., the variables
334     * which has an initial value but which are not assigned with this value.
335     * @param assignment current assignment
336     * @return list of perturbation variables in the model
337     */
338    public Collection<V> perturbVariables(Assignment<V, T> assignment) {
339        return perturbVariables(assignment, variablesWithInitialValue());
340    }
341    
342    /**
343     * The list of perturbation variables in the model, i.e., the variables
344     * which has an initial value but which are not assigned with this value.
345     * Only variables from the given set are considered.
346     * Use {@link Model#perturbVariables(Assignment, Collection)} instead.
347     * @param variables sub-problem
348     * @return list of perturbation variables in the sub-problem
349     */
350    @Deprecated
351    public List<V> perturbVariables(Collection<V> variables) {
352        return perturbVariables(getDefaultAssignment(), variables);
353    }
354
355    /**
356     * The list of perturbation variables in the model, i.e., the variables
357     * which has an initial value but which are not assigned with this value.
358     * Only variables from the given set are considered.
359     * @param assignment current assignment
360     * @param variables sub-problem
361     * @return list of perturbation variables in the sub-problem
362     */
363    public List<V> perturbVariables(Assignment<V, T> assignment, Collection<V> variables) {
364        return perturbVariables(assignment, variables, true);
365    }
366
367    /**
368     * The list of perturbation variables in the model, i.e., the variables
369     * which has an initial value but which are not assigned with this value.
370     * Only variables from the given set are considered.
371     * @param assignment current assignment
372     * @param variables sub-problem
373     * @param includeNotAssigned when true, include not assigned variables with a hard conflict (that cannot be assigned)
374     * @return list of perturbation variables in the sub-problem
375     */
376    public List<V> perturbVariables(Assignment<V, T> assignment, Collection<V> variables, boolean includeNotAssigned) {
377        List<V> perturbances = new ArrayList<V>();
378        for (V variable : variables) {
379            if (variable.getInitialAssignment() == null)
380                continue;
381            T value = assignment.getValue(variable);
382            if (value != null) {
383                if (!variable.getInitialAssignment().equals(value))
384                    perturbances.add(variable);
385            } else if (includeNotAssigned) {
386                boolean hasPerturbance = false;
387                for (Constraint<V, T> constraint : variable.hardConstraints()) {
388                    if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
389                        hasPerturbance = true;
390                        break;
391                    }
392                }
393                if (!hasPerturbance)
394                    for (GlobalConstraint<V, T> constraint : globalConstraints()) {
395                        if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
396                            hasPerturbance = true;
397                            break;
398                        }
399                    }
400                if (hasPerturbance)
401                    perturbances.add(variable);
402            }
403        }
404        return perturbances;
405    }
406
407    /**
408     * Returns the set of conflicting variables with this value, if it is
409     * assigned to its variable
410     * Use {@link Model#conflictValues(Assignment, Value)} instead.
411     * @param value a value to be assigned
412     * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable
413     */
414    @Deprecated
415    public Set<T> conflictValues(T value) {
416        return conflictValues(getDefaultAssignment(), value);
417    }
418    
419    /**
420     * Returns the set of conflicting variables with this value, if it is
421     * assigned to its variable
422     * @param assignment current assignment
423     * @param value a value to be assigned
424     * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable
425     */
426    public Set<T> conflictValues(Assignment<V, T> assignment, T value) {
427        Set<T> conflictValues = new HashSet<T>();
428        for (Constraint<V, T> constraint : value.variable().hardConstraints())
429            constraint.computeConflicts(assignment, value, conflictValues);
430        for (GlobalConstraint<V, T> constraint : globalConstraints())
431            constraint.computeConflicts(assignment, value, conflictValues);
432        return conflictValues;
433    }
434
435    /**
436     * Return true if the given value is in conflict with a hard constraint
437     * Use {@link Model#inConflict(Assignment, Value)} instead.
438     * @param value a value in question
439     * @return true if there is a conflict, i.e., there is at least one value that would have to be unassigned if the given value is assigned to its variable
440     **/
441    @Deprecated
442    public boolean inConflict(T value) {
443        return inConflict(getDefaultAssignment(), value);
444    }
445
446    /** Return true if the given value is in conflict with a hard constraint
447     * @param assignment current assignment
448     * @param value a value in question
449     * @return true if there is a conflict, i.e., there is at least one value that would have to be unassigned if the given value is assigned to its variable
450     **/
451    public boolean inConflict(Assignment<V, T> assignment, T value) {
452        for (Constraint<V, T> constraint : value.variable().hardConstraints())
453            if (constraint.inConflict(assignment, value))
454                return true;
455        for (GlobalConstraint<V, T> constraint : globalConstraints())
456            if (constraint.inConflict(assignment, value))
457                return true;
458        return false;
459    }
460
461    /** The list of variables with an initial value (i.e., variables with {@link Variable#getInitialAssignment()} not null)
462     * @return list of variables with an initial value 
463     **/
464    public Collection<V> variablesWithInitialValue() {
465        iVariablesWithInitialValueLock.readLock().lock();
466        try {
467            if (iVariablesWithInitialValueCache != null)
468                return iVariablesWithInitialValueCache;
469        } finally {
470            iVariablesWithInitialValueLock.readLock().unlock();
471        }
472        iVariablesWithInitialValueLock.writeLock().lock();
473        try {
474            if (iVariablesWithInitialValueCache != null)
475                return iVariablesWithInitialValueCache;
476            iVariablesWithInitialValueCache = new ArrayList<V>();
477            for (V variable : iVariables) {
478                if (variable.getInitialAssignment() != null)
479                    iVariablesWithInitialValueCache.add(variable);
480            }
481            return iVariablesWithInitialValueCache;
482        } finally {
483            iVariablesWithInitialValueLock.writeLock().unlock();
484        }
485    }
486
487    /** Invalidates cache containing all variables that possess an initial value */
488    protected void invalidateVariablesWithInitialValueCache() {
489        iVariablesWithInitialValueLock.writeLock().lock();
490        iVariablesWithInitialValueCache = null;
491        iVariablesWithInitialValueLock.writeLock().unlock();
492    }
493    
494    /** Called before a value is assigned to its variable
495     * @param iteration current iteration
496     * @param value a value to be assigned
497     **/
498    @Deprecated
499    public void beforeAssigned(long iteration, T value) {
500    }
501
502    /** Called before a value is assigned to its variable
503     * @param assignment current assignment
504     * @param iteration current iteration
505     * @param value a value to be assigned
506     **/
507    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
508        beforeAssigned(iteration, value);
509        for (ModelListener<V, T> listener : iModelListeners)
510            listener.beforeAssigned(assignment, iteration, value);
511    }
512
513    /** Called before a value is unassigned from its variable 
514     * @param iteration current iteration
515     * @param value a value to be unassigned
516     **/
517    @Deprecated
518    public void beforeUnassigned(long iteration, T value) {
519    }
520
521    /** Called before a value is unassigned from its variable
522     * @param assignment current assignment
523     * @param iteration current iteration
524     * @param value a value to be unassigned
525     **/
526    public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) {
527        beforeUnassigned(iteration, value);
528        for (ModelListener<V, T> listener : iModelListeners)
529            listener.beforeUnassigned(assignment, iteration, value);
530    }
531
532    /** Called after a value is assigned to its variable
533     * @param iteration current iteration
534     * @param value a value that was assigned
535     **/
536    @Deprecated
537    public void afterAssigned(long iteration, T value) {
538    }
539
540    /** Called after a value is assigned to its variable
541     * @param assignment current assignment
542     * @param iteration current iteration
543     * @param value a value that was assigned
544     **/
545    public void afterAssigned(Assignment<V, T> assignment,  long iteration, T value) {
546        afterAssigned(iteration, value);
547        for (ModelListener<V, T> listener : iModelListeners)
548            listener.afterAssigned(assignment, iteration, value);
549    }
550    
551    /** Called after a value is unassigned from its variable
552     * @param iteration current iteration
553     * @param value a value that was unassigned
554     **/
555    @Deprecated
556    public void afterUnassigned(long iteration, T value) {
557    }
558
559    /** Called after a value is unassigned from its variable
560     * @param assignment current assignment
561     * @param iteration current iteration
562     * @param value a value that was unassigned
563     **/
564    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
565        afterUnassigned(iteration, value);
566        for (ModelListener<V, T> listener : iModelListeners)
567            listener.afterUnassigned(assignment, iteration, value);
568    }
569
570    @Override
571    public String toString() {
572        return "Model{\n    variables=" + ToolBox.col2string(variables(), 2) + ",\n    constraints=" + ToolBox.col2string(constraints(), 2) + ",\n  }";
573    }
574    
575    /**
576     * String representation -- returns a list of values of objective criteria
577     * @param assignment current assignment
578     * @return comma separated string of {@link TimetablingCriterion#toString(Assignment)}
579     */
580    public String toString(Assignment<V, T> assignment) {
581        List<Criterion<V, T>> criteria = new ArrayList<Criterion<V,T>>(getCriteria());
582        Collections.sort(criteria, new Comparator<Criterion<V, T>>() {
583            @Override
584            public int compare(Criterion<V, T> c1, Criterion<V, T> c2) {
585                int cmp = -Double.compare(c1.getWeight(), c2.getWeight());
586                if (cmp != 0) return cmp;
587                return c1.getName().compareTo(c2.getName());
588            }
589        });
590        String ret = "";
591        for (Criterion<V, T> criterion: criteria) {
592            String val = criterion.toString(assignment);
593            if (val != null && !val.isEmpty())
594                ret += ", " + val;
595        }
596        return (nrUnassignedVariables(assignment) == 0 ? "" : "V:" + nrAssignedVariables(assignment) + "/" + variables().size() + ", ") + "T:" + sDoubleFormat.format(getTotalValue(assignment)) + ret;
597    }
598
599    protected String getPerc(double value, double min, double max) {
600        if (max == min)
601            return sPercentageFormat.format(100.0);
602        return sPercentageFormat.format(100.0 - 100.0 * (value - min) / (max - min));
603    }
604
605    protected String getPercRev(double value, double min, double max) {
606        if (max == min)
607            return sPercentageFormat.format(0.0);
608        return sPercentageFormat.format(100.0 * (value - min) / (max - min));
609    }
610    
611    /**
612     * Returns information about the current solution. Information from all
613     * model listeners and constraints is also included.
614     * Use {@link Model#getInfo(Assignment)} instead.
615     * @return info table
616     */
617    @Deprecated
618    public Map<String, String> getInfo() {
619        return getInfo(getDefaultAssignment());
620    }
621
622    /**
623     * Returns information about the current solution. Information from all
624     * model listeners and constraints is also included.
625     * @param assignment current assignment
626     * @return info table
627     */
628    public Map<String, String> getInfo(Assignment<V, T> assignment) {
629        Map<String, String> ret = new HashMap<String, String>();
630        ret.put("Assigned variables", getPercRev(assignment.nrAssignedVariables(), 0, variables().size()) + "% (" + assignment.nrAssignedVariables() + "/" + variables().size() + ")");
631        Collection<V> varsWithInitialValue = variablesWithInitialValue();
632        int nrVarsWithInitialValue = varsWithInitialValue.size();
633        if (nrVarsWithInitialValue > 0) {
634            Collection<V> pv = perturbVariables(assignment, varsWithInitialValue, false);
635            ret.put("Perturbation variables", getPercRev(pv.size(), 0, nrVarsWithInitialValue) + "% (" + pv.size() + " + " + (variables().size() - nrVarsWithInitialValue) + ")");
636        }
637        ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment)));
638        for (InfoProvider<V, T> provider : iInfoProviders)
639            provider.getInfo(assignment, ret);
640        return ret;
641    }
642    
643    /**
644     * Extended information about current solution. Similar to
645     * {@link Model#getInfo(Assignment)}, but some more information (that is more
646     * expensive to compute) might be added.
647     * Use {@link Model#getExtendedInfo(Assignment)} instead.
648     * @return extended info table
649     */
650    @Deprecated
651    public Map<String, String> getExtendedInfo() {
652        return getExtendedInfo(getDefaultAssignment());
653    }
654
655    /**
656     * Extended information about current solution. Similar to
657     * {@link Model#getInfo(Assignment)}, but some more information (that is more
658     * expensive to compute) might be added.
659     * @param assignment current assignment
660     * @return extended info table
661     */
662    public Map<String, String> getExtendedInfo(Assignment<V, T> assignment) {
663        Map<String, String> ret = getInfo(assignment);
664        for (InfoProvider<V, T> provider : iInfoProviders)
665            if (provider instanceof ExtendedInfoProvider)
666                ((ExtendedInfoProvider<V, T>)provider).getExtendedInfo(assignment, ret);
667        return ret;
668    }
669    
670    /**
671     * Returns information about the current solution. Information from all
672     * model listeners and constraints is also included. Only variables from the
673     * given set are considered.
674     * Use {@link Model#getInfo(Assignment, Collection)} instead.
675     * @param variables sub-problem 
676     * @return info table
677     **/
678    @Deprecated
679    public Map<String, String> getInfo(Collection<V> variables) {
680        return getInfo(getDefaultAssignment(), variables);
681    }
682
683    /**
684     * Returns information about the current solution. Information from all
685     * model listeners and constraints is also included. Only variables from the
686     * given set are considered.
687     * @param assignment current assignment
688     * @param variables sub-problem 
689     * @return info table
690     */
691    public Map<String, String> getInfo(Assignment<V, T> assignment, Collection<V> variables) {
692        Map<String, String> ret = new HashMap<String, String>();
693        int assigned = 0, perturb = 0, nrVarsWithInitialValue = 0;
694        for (V variable : variables) {
695            T value = assignment.getValue(variable);
696            if (value != null)
697                assigned++;
698            if (variable.getInitialAssignment() != null) {
699                nrVarsWithInitialValue++;
700                if (value != null) {
701                    if (!variable.getInitialAssignment().equals(value))
702                        perturb++;
703                } else {
704                    boolean hasPerturbance = false;
705                    for (Constraint<V, T> constraint : variable.hardConstraints()) {
706                        if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
707                            hasPerturbance = true;
708                            break;
709                        }
710                    }
711                    if (!hasPerturbance)
712                        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
713                            if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
714                                hasPerturbance = true;
715                                break;
716                            }
717                        }
718                    if (hasPerturbance)
719                        perturb++;
720                }
721            }
722        }
723        ret.put("Assigned variables", getPercRev(assigned, 0, variables.size()) + "% (" + assigned + "/" + variables.size() + ")");
724        if (nrVarsWithInitialValue > 0) {
725            ret.put("Perturbation variables", getPercRev(perturb, 0, nrVarsWithInitialValue) + "% (" + perturb + " + " + (variables.size() - nrVarsWithInitialValue) + ")");
726        }
727        ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment, variables)));
728        for (InfoProvider<V, T> provider : iInfoProviders)
729            provider.getInfo(assignment, ret, variables);
730        return ret;
731    }
732
733    /**
734     * Returns the number of unassigned variables in the best ever found
735     * solution
736     * @return number of unassigned variables in the best solution
737     */
738    public int getBestUnassignedVariables() {
739        return iBestUnassignedVariables;
740    }
741
742    /**
743     * Returns the number of perturbation variables in the best ever found
744     * solution
745     * @return number of perturbation variables in the best solution
746     */
747    public int getBestPerturbations() {
748        return iBestPerturbations;
749    }
750    
751    /**
752     * Total value of the best ever found solution -- sum of all assigned values
753     * (see {@link Value#toDouble(Assignment)}).
754     * @return value of the best solution
755     */
756    public double getBestValue() {
757        return iBestValue;
758    }
759
760    /** Set total value of the best ever found solution 
761     * @param bestValue value of the best solution
762     **/
763    public void setBestValue(double bestValue) {
764        iBestValue = bestValue;
765    }
766    
767    /**
768     * Save the current assignment as the best ever found assignment
769     * Use {@link Model#saveBest(Assignment)} instead.
770     **/
771    @Deprecated
772    public void saveBest() {
773        saveBest(getDefaultAssignment());
774    }
775
776    /** Save the current assignment as the best ever found assignment 
777     * @param assignment current assignment 
778     **/
779    public void saveBest(Assignment<V, T> assignment) {
780        iBestUnassignedVariables = iVariables.size() - assignment.nrAssignedVariables();
781        iBestPerturbations = perturbVariables(assignment).size();
782        iBestValue = getTotalValue(assignment);
783        for (V variable : iVariables) {
784            variable.setBestAssignment(assignment.getValue(variable), assignment.getIteration(variable));
785        }
786        for (Criterion<V, T> criterion: getCriteria()) {
787            criterion.bestSaved(assignment);
788        }
789    }
790
791    /** Clear the best ever found assignment */
792    public void clearBest() {
793        iBestUnassignedVariables = -1;
794        iBestPerturbations = 0;
795        iBestValue = 0;
796        for (V variable : iVariables) {
797            variable.setBestAssignment(null, 0);
798        }
799    }
800
801    /**
802     * Restore the best ever found assignment into the current assignment
803     * Use {@link Model#restoreBest(Assignment)} instead.
804     **/
805    @Deprecated
806    protected void restoreBest() {
807        restoreBest(getDefaultAssignment());
808    }
809
810    /** Restore the best ever found assignment into the current assignment
811     * @param assignment current assignment
812     * @param assignmentOrder assignment order of the variables 
813     **/
814    @SuppressWarnings("unchecked")
815    protected void restoreBest(Assignment<V, T> assignment, Comparator<V> assignmentOrder) {
816        TreeSet<V> sortedVariables = new TreeSet<V>(assignmentOrder);
817        for (V variable : iVariables) {
818            T value = assignment.getValue(variable);
819            if (value == null) {
820                if (variable.getBestAssignment() != null)
821                    sortedVariables.add(variable);
822            } else if (!value.equals(variable.getBestAssignment())) {
823                assignment.unassign(0, variable);
824                if (variable.getBestAssignment() != null)
825                    sortedVariables.add(variable);
826            }
827        }
828        Set<T> problems = new HashSet<T>();
829        for (V variable : sortedVariables) {
830            Set<T> confs = conflictValues(assignment, variable.getBestAssignment());
831            if (!confs.isEmpty()) {
832                sLogger.error("restore best problem: assignment " + variable.getName() + " = " + variable.getBestAssignment().getName());
833                boolean weakened = false;
834                for (Constraint<V, T> c : variable.hardConstraints()) {
835                    Set<T> x = new HashSet<T>();
836                    c.computeConflicts(assignment, variable.getBestAssignment(), x);
837                    if (!x.isEmpty()) {
838                        if (c instanceof WeakeningConstraint) {
839                            ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment());
840                            sLogger.info("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened");
841                            weakened = true;
842                        } else {
843                            sLogger.error("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
844                        }
845                    }
846                }
847                for (GlobalConstraint<V, T> c : globalConstraints()) {
848                    Set<T> x = new HashSet<T>();
849                    c.computeConflicts(assignment, variable.getBestAssignment(), x);
850                    if (!x.isEmpty()) {
851                        if (c instanceof WeakeningConstraint) {
852                            ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment());
853                            sLogger.info("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened");
854                            weakened = true;
855                        } else {
856                            sLogger.error("  global constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
857                        }
858                    }
859                }
860                if (weakened && conflictValues(assignment, variable.getBestAssignment()).isEmpty())
861                    assignment.assign(0, variable.getBestAssignment());
862                else
863                    problems.add(variable.getBestAssignment());
864            } else
865                assignment.assign(0, variable.getBestAssignment());
866        }
867        int attempt = 0, maxAttempts = 3 * problems.size();
868        while (!problems.isEmpty() && attempt <= maxAttempts) {
869            attempt++;
870            T value = ToolBox.random(problems);
871            problems.remove(value);
872            V variable = value.variable();
873            Set<T> confs = conflictValues(assignment, value);
874            if (!confs.isEmpty()) {
875                sLogger.error("restore best problem (again, att=" + attempt + "): assignment " + variable.getName() + " = " + value.getName());
876                for (Constraint<V, T> c : variable.hardConstraints()) {
877                    Set<T> x = new HashSet<T>();
878                    c.computeConflicts(assignment, value, x);
879                    if (!x.isEmpty())
880                        sLogger.error("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
881                }
882                for (GlobalConstraint<V, T> c : globalConstraints()) {
883                    Set<T> x = new HashSet<T>();
884                    c.computeConflicts(assignment, value, x);
885                    if (!x.isEmpty())
886                        sLogger.error("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
887                }
888                for (T conf : confs)
889                    assignment.unassign(0, conf.variable());
890                problems.addAll(confs);
891            }
892            assignment.assign(0, value);
893        }
894        for (Criterion<V, T> criterion: getCriteria()) {
895            criterion.bestRestored(assignment);
896        }
897    }
898    
899    /** Restore the best ever found assignment into the current assignment
900     * @param assignment current assignment
901     **/
902    public void restoreBest(Assignment<V, T> assignment) {
903        restoreBest(assignment, new Comparator<V>() {
904            @Override
905            public int compare(V v1, V v2) {
906                if (v1.getBestAssignmentIteration() < v2.getBestAssignmentIteration()) return -1;
907                if (v1.getBestAssignmentIteration() > v2.getBestAssignmentIteration()) return 1;
908                return v1.compareTo(v2);
909            }
910        });
911    }
912    
913    /**
914     * The list of unassigned variables in the best ever found solution.
915     * Use {@link Model#bestUnassignedVariables(Assignment)} instead.
916     * @return variables list of unassigned variables in the best solution
917     **/
918    @Deprecated
919    public Collection<V> bestUnassignedVariables() {
920        return bestUnassignedVariables(getDefaultAssignment());
921    }
922    
923    /** The list of unassigned variables in the best ever found solution
924     * @param assignment current assignment
925     * @return variables list of unassigned variables in the best solution
926     **/
927    public Collection<V> bestUnassignedVariables(Assignment<V, T> assignment) {
928        Collection<V> ret = new ArrayList<V>(variables().size());
929        if (iBestUnassignedVariables < 0) {
930            for (V variable : variables()) {
931                if (assignment.getValue(variable) == null)
932                    ret.add(variable);
933            }
934        } else {
935            for (V variable : variables()) {
936                if (variable.getBestAssignment() == null)
937                    ret.add(variable);
938            }
939        }
940        return ret;
941    }
942
943    /**
944     * Value of the current solution. It is the sum of all assigned values,
945     * i.e., {@link Value#toDouble(Assignment)}.
946     * Use {@link Model#getTotalValue(Assignment)} instead.
947     * @return solution value
948     */
949    @Deprecated
950    public double getTotalValue() {
951        return getTotalValue(getDefaultAssignment());
952    }
953    
954    /**
955     * Value of the current solution. It is the sum of all assigned values,
956     * i.e., {@link Value#toDouble(Assignment)}.
957     * @param assignment current assignment
958     * @return solution value
959     */
960    public double getTotalValue(Assignment<V, T> assignment) {
961        double ret = 0.0;
962        if (getCriteria().isEmpty())
963            for (T t: assignment.assignedValues())
964                ret += t.toDouble(assignment);
965        else
966            for (Criterion<V, T> c: getCriteria())
967                ret += c.getWeightedValue(assignment);
968        return ret;
969    }
970
971    /**
972     * Value of the current solution. It is the sum of all assigned values,
973     * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are
974     * considered.
975     * Use {@link Model#getTotalValue(Assignment, Collection)} instead.
976     * @param variables sub-problem
977     * @return solution value
978     **/
979    @Deprecated
980    public double getTotalValue(Collection<V> variables) {
981        return getTotalValue(getDefaultAssignment(), variables);
982    }
983    
984    /**
985     * Value of the current solution. It is the sum of all assigned values,
986     * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are
987     * considered.
988     * @param assignment current assignment
989     * @param variables sub-problem
990     * @return solution value
991     **/
992    public double getTotalValue(Assignment<V, T> assignment, Collection<V> variables) {
993        double ret = 0.0;
994        for (V v: variables) {
995            T t = assignment.getValue(v);
996            if (t != null)
997                ret += t.toDouble(assignment);
998        }
999        return ret;
1000    }
1001
1002    /** Adds a model listener 
1003     * @param listener a model listener
1004     **/
1005    @SuppressWarnings("unchecked")
1006    public void addModelListener(ModelListener<V, T> listener) {
1007        iModelListeners.add(listener);
1008        if (listener instanceof InfoProvider<?, ?>)
1009            iInfoProviders.add((InfoProvider<V, T>) listener);
1010        for (Constraint<V, T> constraint : iConstraints)
1011            listener.constraintAdded(constraint);
1012        for (Constraint<V, T> constraint : iGlobalConstraints)
1013            listener.constraintAdded(constraint);
1014        for (V variable : iVariables)
1015            listener.variableAdded(variable);
1016    }
1017
1018    /** Removes a model listener
1019     * @param listener a model listener
1020     **/
1021    public void removeModelListener(ModelListener<V, T> listener) {
1022        if (listener instanceof InfoProvider<?, ?>)
1023            iInfoProviders.remove((InfoProvider<?, ?>)listener);
1024        for (V variable : iVariables)
1025            listener.variableRemoved(variable);
1026        for (Constraint<V, T> constraint : iConstraints)
1027            listener.constraintRemoved(constraint);
1028        for (Constraint<V, T> constraint : iGlobalConstraints)
1029            listener.constraintRemoved(constraint);
1030        iModelListeners.remove(listener);
1031    }
1032
1033    /** Model initialization
1034     * @param solver current solver
1035     * @return true if successfully initialized 
1036     **/
1037    public boolean init(Solver<V, T> solver) {
1038        for (ModelListener<V, T> listener : new ArrayList<ModelListener<V, T>>(iModelListeners)) {
1039            if (!listener.init(solver))
1040                return false;
1041        }
1042        return true;
1043    }
1044
1045    /** The list of model listeners 
1046     * @return list of model listeners
1047     **/
1048    public List<ModelListener<V, T>> getModelListeners() {
1049        return iModelListeners;
1050    }
1051
1052    /** The list of model listeners that are of the given class
1053     * @param type model listener type
1054     * @return list of model listeners that are of the given class
1055     **/
1056    public ModelListener<V, T> modelListenerOfType(Class<ModelListener<V, T>> type) {
1057        for (ModelListener<V, T> listener : iModelListeners) {
1058            if (listener.getClass() == type)
1059                return listener;
1060        }
1061        return null;
1062    }
1063
1064    /**
1065     * The list of constraints which are in a conflict with the given value if
1066     * it is assigned to its variable. This means the constraints, which adds a
1067     * value into the set of conflicting values in
1068     * {@link Constraint#computeConflicts(Assignment, Value, Set)}.
1069     * @param assignment current assignment
1070     * @param value given value
1071     * @return hard constraints and their conflicts that are conflicting with the given value
1072     */
1073    public Map<Constraint<V, T>, Set<T>> conflictConstraints(Assignment<V, T> assignment, T value) {
1074        Map<Constraint<V, T>, Set<T>> conflictConstraints = new HashMap<Constraint<V, T>, Set<T>>();
1075        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
1076            Set<T> conflicts = new HashSet<T>();
1077            constraint.computeConflicts(assignment, value, conflicts);
1078            if (!conflicts.isEmpty()) {
1079                conflictConstraints.put(constraint, conflicts);
1080            }
1081        }
1082        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
1083            Set<T> conflicts = new HashSet<T>();
1084            constraint.computeConflicts(assignment, value, conflicts);
1085            if (!conflicts.isEmpty()) {
1086                conflictConstraints.put(constraint, conflicts);
1087            }
1088        }
1089        return conflictConstraints;
1090    }
1091
1092    /**
1093     * The list of hard constraints which contain at least one variable that is
1094     * not assigned.
1095     * @param assignment current assignment
1096     * @return list of hard constraints which contain at least one variable that is not assigned
1097     */
1098    public List<Constraint<V, T>> unassignedHardConstraints(Assignment<V, T> assignment) {
1099        List<Constraint<V, T>> ret = new ArrayList<Constraint<V, T>>();
1100        constraints: for (Constraint<V, T> constraint : constraints()) {
1101            if (!constraint.isHard())
1102                continue;
1103            for (V v : constraint.variables()) {
1104                if (assignment.getValue(v) == null) {
1105                    ret.add(constraint);
1106                    continue constraints;
1107                }
1108            }
1109        }
1110        if (iVariables.size() > assignment.nrAssignedVariables())
1111            ret.addAll(globalConstraints());
1112        return ret;
1113    }
1114
1115    /** Registered info providers (see {@link InfoProvider}) 
1116     * @return list of registered info providers
1117     **/
1118    protected List<InfoProvider<V, T>> getInfoProviders() {
1119        return iInfoProviders;
1120    }
1121    
1122    /** Register a new criterion 
1123     * @param criterion a criterion
1124     **/
1125    public void addCriterion(Criterion<V,T> criterion) {
1126        iCriteria.put(criterion.getClass().getName(), criterion);
1127        criterion.setModel(this);
1128        addModelListener(criterion);
1129    }
1130    
1131    /** Unregister an existing criterion
1132     * @param criterion a criterion
1133     **/
1134    public void removeCriterion(Criterion<V,T> criterion) {
1135        iCriteria.remove(criterion.getClass().getName());
1136        criterion.setModel(null);
1137        removeModelListener(criterion);
1138    }
1139    
1140    /** Unregister an existing criterion
1141     * @param criterion a criterion
1142     **/
1143    public void removeCriterion(Class<? extends Criterion<V, T>> criterion) {
1144        Criterion<V,T> c = iCriteria.remove(criterion.getName());
1145        if (c != null)
1146            removeModelListener(c);
1147    }
1148
1149    /** Return a registered criterion of the given type. 
1150     * @param criterion criterion type 
1151     * @return registered criterion of the given type
1152     **/
1153    public Criterion<V, T> getCriterion(Class<? extends Criterion<V, T>> criterion) {
1154        return iCriteria.get(criterion.getName());
1155    }
1156    
1157    /** List all registered criteria
1158     * @return list all registered criteria
1159     **/
1160    public Collection<Criterion<V, T>> getCriteria() {
1161        return iCriteria.values();
1162    }
1163    
1164    /**
1165     * Weaken all weakening constraint so that the given value can be assigned without
1166     * them creating a conflict using {@link WeakeningConstraint#weaken(Assignment, Value)}.
1167     * This method is handy for instance when an existing solution is being loaded
1168     * into the solver.
1169     * @param assignment current assignment
1170     * @param value given value
1171     */
1172    @SuppressWarnings("unchecked")
1173    public void weaken(Assignment<V, T> assignment, T value) {
1174        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
1175            if (constraint instanceof WeakeningConstraint)
1176                ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value);
1177        }
1178        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
1179            if (constraint instanceof WeakeningConstraint)
1180                ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value);
1181        }
1182    }
1183    
1184    /**
1185     * Create a reference to an assignment context for a class that is in a need of one. Through this
1186     * reference an assignment context (see {@link AssignmentContext}) can be accessed using
1187     * {@link Assignment#getAssignmentContext(AssignmentContextReference)}.
1188     * @param parent class needing an assignment context
1189     * @param <C> assignment context type
1190     * @return reference to an assignment context
1191     */
1192    public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> createReference(HasAssignmentContext<V, T, C> parent) {
1193        AssignmentContextReference<V, T, C> ref = new AssignmentContextReference<V, T, C>(parent, iNextReferenceId);
1194        iAssignmentContextReferences.put(iNextReferenceId, ref);
1195        iNextReferenceId++;
1196        return ref;
1197    }
1198    
1199    /**
1200     * Clear all assignment contexts for the given assignment
1201     * @param assignment given {@link Assignment}
1202     */
1203    public synchronized void clearAssignmentContexts(Assignment<V, T> assignment) {
1204        for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values())
1205            assignment.clearContext(ref);
1206    }
1207    
1208    /**
1209     * Remove a reference to an assignment context for the model
1210     * @param parent class with an assignment context
1211     * @param <C> assignment context type
1212     * @return reference to an assignment context that was removed from the model (if any)
1213     */
1214    @SuppressWarnings("unchecked")
1215    public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> removeReference(HasAssignmentContext<V, T, C> parent) {
1216        AssignmentContextReference<V,T,C> reference = parent.getAssignmentContextReference();
1217        if (reference != null)
1218            return (AssignmentContextReference<V,T,C>) iAssignmentContextReferences.remove(reference.getIndex());
1219        return null;
1220    }
1221    
1222    /**
1223     * Create all assignment contexts for the given assignment
1224     * @param assignment given {@link Assignment}
1225     * @param clear if true {@link Assignment#clearContext(AssignmentContextReference)} is called first
1226     */
1227    public synchronized void createAssignmentContexts(Assignment<V, T> assignment, boolean clear) {
1228        for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values()) {
1229            if (clear) assignment.clearContext(ref);
1230            assignment.getAssignmentContext(ref);
1231        }
1232    }
1233
1234    /**
1235     * Return default assignment that is using the old {@link Variable#getAssignment()} assignments.
1236     * @return as instance of {@link DefaultSingleAssignment}
1237     */
1238    @Deprecated
1239    public Assignment<V, T> getDefaultAssignment() {
1240        if (iAssignment == null)
1241            iAssignment = new DefaultSingleAssignment<V, T>();
1242        return iAssignment;
1243    }
1244    
1245    /**
1246     * Set default assignment 
1247     * @param assignment current assignment to become default
1248     */
1249    @Deprecated
1250    public void setDefaultAssignment(Assignment<V, T> assignment) {
1251        iAssignment = assignment;
1252    }
1253    
1254    /**
1255     * Returns an instance of an empty assignment (using {@link EmptyAssignment})
1256     * @return an empty assignment
1257     */
1258    public Assignment<V, T> getEmptyAssignment() {
1259        if (iEmptyAssignment == null)
1260            iEmptyAssignment = new EmptyAssignment<V, T>();
1261        return iEmptyAssignment;
1262    }
1263    
1264    
1265    /**
1266     * Create a new inherited assignment from the given solution
1267     * @param solution a solution that is using this model
1268     * @param index thread index of the new assignment
1269     * @return a new inherited assignment
1270     */
1271    public InheritedAssignment<V, T> createInheritedAssignment(Solution<V, T> solution, int index) {
1272        return new DefaultInheritedAssignment<V, T>(solution, index);
1273    }
1274}