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     * &nbsp;&nbsp;&nbsp;&nbsp;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    }