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