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