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