001package net.sf.cpsolver.coursett.heuristics; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashMap; 006import java.util.Iterator; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010 011import net.sf.cpsolver.coursett.model.Lecture; 012import net.sf.cpsolver.coursett.model.Placement; 013import net.sf.cpsolver.coursett.model.TimetableModel; 014import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection; 015import net.sf.cpsolver.ifs.model.Neighbour; 016import net.sf.cpsolver.ifs.solution.Solution; 017import net.sf.cpsolver.ifs.solver.Solver; 018import net.sf.cpsolver.ifs.util.DataProperties; 019import net.sf.cpsolver.ifs.util.JProf; 020import net.sf.cpsolver.ifs.util.ToolBox; 021 022/** 023 * Neighbour selection which does the standard time neighbour selection most of 024 * the time, however, the very best neighbour is selected time to time (using 025 * backtracking based search). 026 * 027 * @see StandardNeighbourSelection 028 * @version CourseTT 1.2 (University Course Timetabling)<br> 029 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 030 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 031 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 032 * <br> 033 * This library is free software; you can redistribute it and/or modify 034 * it under the terms of the GNU Lesser General Public License as 035 * published by the Free Software Foundation; either version 3 of the 036 * License, or (at your option) any later version. <br> 037 * <br> 038 * This library is distributed in the hope that it will be useful, but 039 * WITHOUT ANY WARRANTY; without even the implied warranty of 040 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 041 * Lesser General Public License for more details. <br> 042 * <br> 043 * You should have received a copy of the GNU Lesser General Public 044 * License along with this library; if not see 045 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 046 */ 047 048public class NeighbourSelectionWithSuggestions extends StandardNeighbourSelection<Lecture, Placement> { 049 private double iSuggestionProbability = 0.1; 050 private double iSuggestionProbabilityAllAssigned = 0.5; 051 private int iSuggestionTimeout = 500; 052 private int iSuggestionDepth = 4; 053 054 private Solution<Lecture, Placement> iSolution = null; 055 private SuggestionNeighbour iSuggestionNeighbour = null; 056 private double iValue = 0; 057 private int iNrAssigned = 0; 058 private boolean iTimeoutReached = false; 059 060 public NeighbourSelectionWithSuggestions(DataProperties properties) throws Exception { 061 super(properties); 062 iSuggestionProbability = properties 063 .getPropertyDouble("Neighbour.SuggestionProbability", iSuggestionProbability); 064 iSuggestionProbabilityAllAssigned = properties.getPropertyDouble("Neighbour.SuggestionProbabilityAllAssigned", 065 iSuggestionProbabilityAllAssigned); 066 iSuggestionTimeout = properties.getPropertyInt("Neighbour.SuggestionTimeout", iSuggestionTimeout); 067 iSuggestionDepth = properties.getPropertyInt("Neighbour.SuggestionDepth", iSuggestionDepth); 068 } 069 070 public NeighbourSelectionWithSuggestions(Solver<Lecture, Placement> solver) throws Exception { 071 this(solver.getProperties()); 072 init(solver); 073 } 074 075 @Override 076 public void init(Solver<Lecture, Placement> solver) { 077 super.init(solver); 078 } 079 080 @Override 081 public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) { 082 Neighbour<Lecture, Placement> neighbour = null; 083 if (solution.getModel().unassignedVariables().isEmpty()) { 084 for (int d = iSuggestionDepth; d > 1; d--) { 085 if (ToolBox.random() < Math.pow(iSuggestionProbabilityAllAssigned, d - 1)) { 086 neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d); 087 break; 088 } 089 } 090 } else { 091 for (int d = iSuggestionDepth; d > 1; d--) { 092 if (ToolBox.random() < Math.pow(iSuggestionProbability, d - 1)) { 093 neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d); 094 break; 095 } 096 } 097 } 098 return (neighbour != null ? neighbour : super.selectNeighbour(solution)); 099 } 100 101 public synchronized Neighbour<Lecture, Placement> selectNeighbourWithSuggestions( 102 Solution<Lecture, Placement> solution, Lecture lecture, int depth) { 103 if (lecture == null) 104 return null; 105 106 iSolution = solution; 107 iSuggestionNeighbour = null; 108 iValue = solution.getModel().getTotalValue(); 109 iNrAssigned = solution.getModel().assignedVariables().size(); 110 iTimeoutReached = false; 111 112 synchronized (solution) { 113 // System.out.println("BEFORE BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+", value="+iCmp.currentValue(iSolution)); 114 115 List<Lecture> initialLectures = new ArrayList<Lecture>(1); 116 initialLectures.add(lecture); 117 backtrack(JProf.currentTimeMillis(), initialLectures, new HashMap<Lecture, Placement>(), 118 new HashMap<Lecture, Placement>(), depth); 119 120 // System.out.println("AFTER BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+", value="+iCmp.currentValue(iSolution)); 121 } 122 123 return iSuggestionNeighbour; 124 } 125 126 private boolean containsCommited(Collection<Placement> values) { 127 if (((TimetableModel) iSolution.getModel()).hasConstantVariables()) { 128 for (Placement placement : values) { 129 Lecture lecture = placement.variable(); 130 if (lecture.isCommitted()) 131 return true; 132 } 133 } 134 return false; 135 } 136 137 private void backtrack(long startTime, List<Lecture> initialLectures, Map<Lecture, Placement> resolvedLectures, 138 HashMap<Lecture, Placement> conflictsToResolve, int depth) { 139 int nrUnassigned = conflictsToResolve.size(); 140 if ((initialLectures == null || initialLectures.isEmpty()) && nrUnassigned == 0) { 141 if (iSolution.getModel().assignedVariables().size() > iNrAssigned 142 || (iSolution.getModel().assignedVariables().size() == iNrAssigned && iValue > iSolution.getModel().getTotalValue())) { 143 if (iSuggestionNeighbour == null || iSuggestionNeighbour.compareTo(iSolution) >= 0) 144 iSuggestionNeighbour = new SuggestionNeighbour(resolvedLectures); 145 } 146 return; 147 } 148 if (depth <= 0) 149 return; 150 if (iTimeoutReached || iSuggestionTimeout > 0 && JProf.currentTimeMillis() - startTime > iSuggestionTimeout) { 151 iTimeoutReached = true; 152 return; 153 } 154 155 for (Lecture lecture: initialLectures != null && !initialLectures.isEmpty() ? initialLectures : new ArrayList<Lecture>(conflictsToResolve.keySet())) { 156 if (iTimeoutReached) break; 157 if (resolvedLectures.containsKey(lecture)) 158 continue; 159 placements: for (Placement placement : lecture.values()) { 160 if (iTimeoutReached) break; 161 if (placement.equals(lecture.getAssignment())) 162 continue; 163 if (placement.isHard()) 164 continue; 165 Set<Placement> conflicts = iSolution.getModel().conflictValues(placement); 166 if (nrUnassigned + conflicts.size() > depth) 167 continue; 168 if (conflicts.contains(placement)) 169 continue; 170 if (containsCommited(conflicts)) 171 continue; 172 for (Iterator<Placement> i = conflicts.iterator();i.hasNext();) { 173 Placement c = i.next(); 174 if (resolvedLectures.containsKey(c.variable())) 175 continue placements; 176 } 177 Placement cur = lecture.getAssignment(); 178 for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) { 179 Placement c = i.next(); 180 c.variable().unassign(0); 181 } 182 if (cur != null) 183 lecture.unassign(0); 184 lecture.assign(0, placement); 185 for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) { 186 Placement c = i.next(); 187 conflictsToResolve.put(c.variable(), c); 188 } 189 Placement resolvedConf = conflictsToResolve.remove(lecture); 190 resolvedLectures.put(lecture, placement); 191 backtrack(startTime, null, resolvedLectures, conflictsToResolve, depth - 1); 192 resolvedLectures.remove(lecture); 193 if (cur == null) 194 lecture.unassign(0); 195 else 196 lecture.assign(0, cur); 197 for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) { 198 Placement p = i.next(); 199 p.variable().assign(0, p); 200 conflictsToResolve.remove(p.variable()); 201 } 202 if (resolvedConf != null) 203 conflictsToResolve.put(lecture, resolvedConf); 204 } 205 } 206 } 207 208 public class SuggestionNeighbour extends Neighbour<Lecture, Placement> { 209 private double iValue = 0; 210 private List<Placement> iDifferentAssignments = null; 211 212 public SuggestionNeighbour(Map<Lecture, Placement> resolvedLectures) { 213 iValue = iSolution.getModel().getTotalValue(); 214 iDifferentAssignments = new ArrayList<Placement>(resolvedLectures.values()); 215 } 216 217 @Override 218 public double value() { 219 return iValue; 220 } 221 222 @Override 223 public void assign(long iteration) { 224 // System.out.println("START ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+", value="+iCmp.currentValue(iSolution)); 225 // System.out.println(" "+this); 226 for (Placement p : iDifferentAssignments) { 227 if (p.variable().getAssignment() != null) 228 p.variable().unassign(iteration); 229 } 230 for (Placement p : iDifferentAssignments) { 231 p.variable().assign(iteration, p); 232 } 233 // System.out.println("END ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+", value="+iCmp.currentValue(iSolution)); 234 } 235 236 public int compareTo(Solution<Lecture, Placement> solution) { 237 return Double.compare(iValue, iSolution.getModel().getTotalValue()); 238 } 239 240 @Override 241 public String toString() { 242 StringBuffer sb = new StringBuffer("Suggestion{value=" + (iValue - iSolution.getModel().getTotalValue()) + ": "); 243 for (Iterator<Placement> e = iDifferentAssignments.iterator(); e.hasNext();) { 244 Placement p = e.next(); 245 sb.append("\n " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : "")); 246 } 247 sb.append("}"); 248 return sb.toString(); 249 } 250 } 251}