001package net.sf.cpsolver.ifs.perturbations; 002 003import java.util.Collection; 004import java.util.Locale; 005import java.util.Map; 006import java.util.Set; 007 008import net.sf.cpsolver.ifs.extension.Extension; 009import net.sf.cpsolver.ifs.extension.ViolatedInitials; 010import net.sf.cpsolver.ifs.model.Model; 011import net.sf.cpsolver.ifs.model.Value; 012import net.sf.cpsolver.ifs.model.Variable; 013import net.sf.cpsolver.ifs.solution.Solution; 014import net.sf.cpsolver.ifs.solver.Solver; 015import 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 Tomáš Müller<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 069public 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}