001package org.cpsolver.ifs.extension; 002 003import java.util.ArrayList; 004import java.util.HashSet; 005import java.util.HashMap; 006import java.util.List; 007import java.util.Map; 008import java.util.Set; 009 010import org.cpsolver.ifs.assignment.Assignment; 011import org.cpsolver.ifs.model.Constraint; 012import org.cpsolver.ifs.model.Value; 013import org.cpsolver.ifs.model.Variable; 014import org.cpsolver.ifs.solver.Solver; 015import org.cpsolver.ifs.util.DataProperties; 016 017 018/** 019 * Computation of violated initial values (minimal perturbation problem). <br> 020 * <br> 021 * It is using {@link Constraint#isConsistent(Value, Value)} to find out what 022 * initial values (of different variables) cannot be assigned when an arbitrary 023 * value is assigned to a variable. This information is computed in advance, 024 * before the solver is executed. It is used for better estimation of 025 * perturbation penalty (see 026 * {@link org.cpsolver.ifs.perturbations.PerturbationsCounter}) when a value 027 * is to be assigned to a variable. 028 * 029 * @version IFS 1.3 (Iterative Forward Search)<br> 030 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 031 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 032 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 033 * <br> 034 * This library is free software; you can redistribute it and/or modify 035 * it under the terms of the GNU Lesser General Public License as 036 * published by the Free Software Foundation; either version 3 of the 037 * License, or (at your option) any later version. <br> 038 * <br> 039 * This library is distributed in the hope that it will be useful, but 040 * WITHOUT ANY WARRANTY; without even the implied warranty of 041 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 042 * Lesser General Public License for more details. <br> 043 * <br> 044 * You should have received a copy of the GNU Lesser General Public 045 * License along with this library; if not see 046 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 047 * @param <V> Variable 048 * @param <T> Value 049 */ 050public class ViolatedInitials<V extends Variable<V, T>, T extends Value<V, T>> extends Extension<V, T> { 051 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(ViolatedInitials.class); 052 private Map<T, Set<T>> iViolatedInitials = new HashMap<T, Set<T>>(); 053 054 public ViolatedInitials(Solver<V, T> solver, DataProperties properties) { 055 super(solver, properties); 056 } 057 058 /** Compute the violations between any value and all other initial values 059 * @param assignment current assignment 060 * @return true if initialized properly 061 **/ 062 public boolean init(Assignment<V, T> assignment) { 063 sLogger.info("Computation of violated initials enabled."); 064 for (V variable : getModel().variables()) { 065 if (variable.getInitialAssignment() == null) 066 continue; 067 for (Constraint<V, T> constraint : variable.hardConstraints()) { 068 for (T value : conflictValues(assignment, constraint, variable.getInitialAssignment())) { 069 addViolatedInitial(value, variable.getInitialAssignment()); 070 } 071 } 072 } 073 return true; 074 } 075 076 /** Initial values that cannot be assigned when the given value is assigned 077 * @param value given value 078 * @return list of initial values that cannot be assigned due to the given value 079 * 080 **/ 081 public Set<T> getViolatedInitials(T value) { 082 return iViolatedInitials.get(value); 083 } 084 085 private void addViolatedInitial(T value, T anotherValue) { 086 Set<T> violations = iViolatedInitials.get(value); 087 if (violations == null) { 088 violations = new HashSet<T>(); 089 iViolatedInitials.put(value, violations); 090 } 091 violations.add(anotherValue); 092 } 093 094 private List<T> conflictValues(Assignment<V, T> assignment, Constraint<V, T> constraint, T aValue) { 095 List<T> ret = new ArrayList<T>(); 096 for (V variable : constraint.variables()) { 097 if (variable.equals(aValue.variable())) 098 continue; 099 if (assignment.getValue(variable) != null) 100 continue; 101 for (T value : variable.values(assignment)) { 102 if (!constraint.isConsistent(aValue, value)) 103 ret.add(value); 104 } 105 } 106 return ret; 107 } 108}