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