001 package net.sf.cpsolver.ifs.extension;
002
003
004 import java.util.*;
005
006 import net.sf.cpsolver.ifs.model.*;
007 import net.sf.cpsolver.ifs.solver.*;
008 import net.sf.cpsolver.ifs.util.*;
009
010 /**
011 * Computation of violated initial values (minimal perturbation problem).
012 * <br><br>
013 * It is using {@link Constraint#isConsistent(Value, Value)} to find out what
014 * initial values (of different variables) cannot be assigned when an arbitrary value is
015 * assigned to a variable. This information is computed in advance, before the solver is
016 * executed. It is used for better estimation of perturbation penalty (see
017 * {@link net.sf.cpsolver.ifs.perturbations.PerturbationsCounter}) when a value is to be assigned to a variable.
018 *
019 * @version
020 * IFS 1.1 (Iterative Forward Search)<br>
021 * Copyright (C) 2006 Tomáš Müller<br>
022 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
023 * Lazenska 391, 76314 Zlin, Czech Republic<br>
024 * <br>
025 * This library is free software; you can redistribute it and/or
026 * modify it under the terms of the GNU Lesser General Public
027 * License as published by the Free Software Foundation; either
028 * version 2.1 of the License, or (at your option) any later version.
029 * <br><br>
030 * This library is distributed in the hope that it will be useful,
031 * but WITHOUT ANY WARRANTY; without even the implied warranty of
032 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
033 * Lesser General Public License for more details.
034 * <br><br>
035 * You should have received a copy of the GNU Lesser General Public
036 * License along with this library; if not, write to the Free Software
037 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
038 */
039 public class ViolatedInitials extends Extension {
040 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(ViolatedInitials.class);
041 private Hashtable iViolatedInitials = new Hashtable();
042
043 public ViolatedInitials(Solver solver, DataProperties properties) {
044 super(solver, properties);
045 }
046
047 /** Compute the violations between any value and all other initial values */
048 public boolean init() {
049 sLogger.info("Computation of violated initials enabled.");
050 for (Enumeration i = getModel().variables().elements(); i.hasMoreElements();) {
051 Variable variable = (Variable)i.nextElement();
052 if (variable.getInitialAssignment() == null) continue;
053 for (Enumeration i1 = variable.constraints().elements(); i1.hasMoreElements();) {
054 Constraint constraint = (Constraint)i1.nextElement();
055 Vector conflicts = conflictValues(constraint, variable.getInitialAssignment());
056 for (Enumeration i2 = conflicts.elements(); i2.hasMoreElements(); ) {
057 Value value = (Value)i2.nextElement();
058 addViolatedInitial(value, variable.getInitialAssignment());
059 }
060 }
061 }
062 return true;
063 }
064
065 /** Initial values that cannot be assigned when the given value is assigned */
066 public Set getViolatedInitials(Value value) {
067 return (Set)iViolatedInitials.get(value);
068 }
069
070 private void addViolatedInitial(Value value, Value anotherValue) {
071 Set violations = (Set)iViolatedInitials.get(value);
072 if (violations == null) {
073 violations = new HashSet();
074 iViolatedInitials.put(value, violations);
075 }
076 violations.add(anotherValue);
077 }
078
079 private Vector conflictValues(Constraint constraint, Value aValue) {
080 Vector ret = new FastVector();
081 for (Enumeration i1 = constraint.variables().elements();i1.hasMoreElements();) {
082 Variable variable = (Variable)i1.nextElement();
083 if (variable.equals(aValue.variable())) continue;
084 if (variable.getAssignment() != null) continue;
085 for (Enumeration i2 = variable.values().elements(); i2.hasMoreElements(); ) {
086 Value value = (Value)i2.nextElement();
087 if (!constraint.isConsistent(aValue, value))
088 ret.addElement(value);
089 }
090 }
091 return ret;
092 }
093 }