001 package net.sf.cpsolver.ifs.perturbations;
002
003 import java.util.*;
004
005 import net.sf.cpsolver.ifs.extension.*;
006 import net.sf.cpsolver.ifs.model.*;
007 import net.sf.cpsolver.ifs.solution.*;
008 import net.sf.cpsolver.ifs.solver.*;
009 import net.sf.cpsolver.ifs.util.*;
010
011 /**
012 * Default computation of perturbation penalty (minimal perturbation problem).
013 * <br><br>
014 * A distance function can be defined with the help of perturbations. A perturbation is a variable that has a different
015 * value in the solutions of the initial and the new problem. Some perturbations must be present in each new solution.
016 * So called input perturbation means that a variable must have different values in the initial and changed problem
017 * because of some input changes (e.g., a course must be scheduled at a different time in the changed problem).
018 * The distance function can be defined as the number of additional perturbations. They are given by subtraction of
019 * the final number of perturbations and the number of input perturbations (variables without initial assignments).
020 * <br><br>
021 * This implementation is easily extendable. It disassemble all the available cases into a comparison of the initial and
022 * the assigned value different each other. So, the only method which is needed to be changed is
023 * {@link DefaultPerturbationsCounter#getPenalty(Value, Value)}. Its current implementation is: <ul><code>
024 * protected double getPenalty(Value assignedValue, Value initialValue) {<br>
025 * return 1.0;<br>
026 * }<br>
027 * </code></ul>
028 * It is called only when assignedValue is different to initialValue.
029 *
030 * @see Solver
031 * @see Solution
032 * @see Variable
033 *
034 * @version
035 * IFS 1.1 (Iterative Forward Search)<br>
036 * Copyright (C) 2006 Tomáš Müller<br>
037 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
038 * Lazenska 391, 76314 Zlin, Czech Republic<br>
039 * <br>
040 * This library is free software; you can redistribute it and/or
041 * modify it under the terms of the GNU Lesser General Public
042 * License as published by the Free Software Foundation; either
043 * version 2.1 of the License, or (at your option) any later version.
044 * <br><br>
045 * This library is distributed in the hope that it will be useful,
046 * but WITHOUT ANY WARRANTY; without even the implied warranty of
047 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
048 * Lesser General Public License for more details.
049 * <br><br>
050 * You should have received a copy of the GNU Lesser General Public
051 * License along with this library; if not, write to the Free Software
052 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
053 */
054
055 public class DefaultPerturbationsCounter implements PerturbationsCounter {
056 private ViolatedInitials iViolatedInitials = null;
057 protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
058
059 /** Constructor
060 * @param properties input configuration
061 */
062 public DefaultPerturbationsCounter(DataProperties properties) {
063 }
064
065 /** Initialization */
066 public void init(Solver solver) {
067 for (Enumeration i=solver.getExtensions().elements();i.hasMoreElements();) {
068 Extension extension = (Extension)i.nextElement();
069 if (extension instanceof ViolatedInitials)
070 iViolatedInitials = (ViolatedInitials)extension;
071 }
072 }
073
074 public double getPerturbationPenalty(Model model) {
075 double penalty = 0.0;
076 for (Enumeration e=model.perturbVariables().elements();e.hasMoreElements();) {
077 Variable variable = (Variable)e.nextElement();
078 if (variable.getAssignment()!=null && variable.getInitialAssignment()!=null && !variable.getAssignment().equals(variable.getInitialAssignment()))
079 penalty += getPenaltyD(variable.getAssignment(),variable.getInitialAssignment());
080 }
081 return penalty;
082 }
083
084 public double getPerturbationPenalty(Model model, Vector variables) {
085 double penalty = 0.0;
086 for (Enumeration e=model.perturbVariables(variables).elements();e.hasMoreElements();) {
087 Variable variable = (Variable)e.nextElement();
088 if (variable.getAssignment()!=null && variable.getInitialAssignment()!=null && !variable.getAssignment().equals(variable.getInitialAssignment()))
089 penalty += getPenaltyD(variable.getAssignment(),variable.getInitialAssignment());
090 }
091 return penalty;
092 }
093
094 protected ViolatedInitials getViolatedInitials() { return iViolatedInitials; }
095
096 /** Computes perturbation penalty between assigned and initial value of the same lecture.
097 * It is called only when assignedValue is different to initialValue.
098 * @param assignedValue value assigned to a varuable (null when variable is unassigned)
099 * @param initialValue initial value of the same varaible (always not null)
100 */
101 protected double getPenalty(Value assignedValue, Value initialValue) {
102 return 1.0;
103 }
104
105 /** Case A: initial value of a different unassigned variable cannot be assigned (computed by {@link ViolatedInitials})
106 * @param selectedValue value which is going to be assigned to its variable
107 * @param initialValue value of a different variable, which is currently assigned but which need to be unassifned
108 * Different variable, which is unassigned and whose initial value is in conflict with the selected value.*/
109 protected double getPenaltyA(Value selectedValue, Value initialValue) {
110 return getPenalty(null, initialValue);
111 }
112
113 /** Case B: initial value is unassigned from a conflicting variable.
114 * @param selectedValue value which is going to be unassigned to its variable
115 * @param assignedValue value currently assigned to a conflicting variable (different from the one of selectedVariable)
116 * @param initialValue initial value of the conflicting variable of assignedValue
117 */
118 protected double getPenaltyB(Value selectedValue, Value assignedValue, Value initialValue) {
119 return getPenalty(assignedValue, initialValue);
120 }
121
122 /** Case C: non-initial value is unassigned from a conflicting variable.
123 * @param selectedValue value which is going to be unassigned to its variable
124 * @param assignedValue value currently assigned to a conflicting variable (different from the one of selectedVariable)
125 * @param initialValue initial value of the conflicting variable of assignedValue
126 */
127 protected double getPenaltyC(Value selectedValue, Value assignedValue, Value initialValue) {
128 return -getPenalty(assignedValue, initialValue);
129 }
130
131 /** Case D: different than initial value is assigned to the varaible
132 * @param selectedValue value which is going to be unassigned to its variable
133 * @param initialValue initial value of the same variable
134 */
135 protected double getPenaltyD(Value selectedValue, Value initialValue) {
136 return getPenalty(selectedValue, initialValue);
137 }
138
139 public double getPerturbationPenalty(Model model, Value selectedValue, Collection conflicts) {
140 double penalty = 0;
141 Set violations = (getViolatedInitials()==null?null:getViolatedInitials().getViolatedInitials(selectedValue));
142 if (violations!=null)
143 for (Iterator it1=violations.iterator(); it1.hasNext(); ) {
144 Value aValue = (Value)it1.next();
145 if (aValue.variable().getAssignment()==null)
146 penalty += getPenaltyA(selectedValue,aValue);
147 }
148 for (Iterator it1=conflicts.iterator(); it1.hasNext(); ) {
149 Value conflictValue = (Value)it1.next();
150 Value initialValue = conflictValue.variable().getInitialAssignment();
151 if (initialValue!=null) {
152 if (initialValue.equals(conflictValue))
153 penalty += getPenaltyB(selectedValue, conflictValue, initialValue);
154 else {
155 if (violations==null || !violations.contains(initialValue))
156 penalty += getPenaltyC(selectedValue, conflictValue, initialValue);
157 }
158 }
159 }
160 if (selectedValue.variable().getInitialAssignment()!=null && !selectedValue.equals(selectedValue.variable().getInitialAssignment()))
161 penalty += getPenaltyD(selectedValue, selectedValue.variable().getInitialAssignment());
162 return penalty;
163 }
164
165 public void getInfo(Dictionary info, Model model) {
166 if (model.variablesWithInitialValue().size()>0)
167 info.put("Perturbations: Total penalty", sDoubleFormat.format(getPerturbationPenalty(model)));
168 }
169
170 public void getInfo(Dictionary info, Model model, Vector variables) {
171 if (model.variablesWithInitialValue().size()>0)
172 info.put("Perturbations: Total penalty", sDoubleFormat.format(getPerturbationPenalty(model, variables)));
173 }
174 }