001 package net.sf.cpsolver.coursett.heuristics;
002
003 import java.util.Enumeration;
004 import java.util.HashSet;
005 import java.util.Iterator;
006 import java.util.Vector;
007
008 import net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint;
009 import net.sf.cpsolver.coursett.constraint.GroupConstraint;
010 import net.sf.cpsolver.coursett.constraint.InstructorConstraint;
011 import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
012 import net.sf.cpsolver.coursett.constraint.RoomConstraint;
013 import net.sf.cpsolver.coursett.constraint.SpreadConstraint;
014 import net.sf.cpsolver.coursett.model.Lecture;
015 import net.sf.cpsolver.coursett.model.Placement;
016 import net.sf.cpsolver.coursett.model.TimetableModel;
017 import net.sf.cpsolver.ifs.model.Constraint;
018 import net.sf.cpsolver.ifs.perturbations.PerturbationsCounter;
019 import net.sf.cpsolver.ifs.solution.Solution;
020 import net.sf.cpsolver.ifs.solution.SolutionComparator;
021 import net.sf.cpsolver.ifs.util.DataProperties;
022
023 /**
024 * Timetable (solution) comparator.
025 * <br><br>
026 * The quality of a solution is expressed as a weighted sum combining soft time and classroom preferences, satisfied soft
027 * group constrains and the total number of student conflicts. This allows us to express the importance of different
028 * types of soft constraints.
029 * <br><br>
030 * The solution comparator prefers a more complete solution (with a smaller number of unassigned variables) and a solution
031 * with a smaller number of perturbations among solutions with the same number of unassigned variables. If both solutions
032 * have the same number of unassigned variables and perturbations, the solution of better quality is selected.
033 * <br><br>
034 * Parameters:
035 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
036 * <tr><td>Comparator.HardStudentConflictWeight</td><td>{@link Double}</td><td>Weight of hard student conflict (conflict between single-section classes)</td></tr>
037 * <tr><td>Comparator.StudentConflictWeight</td><td>{@link Double}</td><td>Weight of student conflict</td></tr>
038 * <tr><td>Comparator.TimePreferenceWeight</td><td>{@link Double}</td><td>Time preferences weight</td></tr>
039 * <tr><td>Comparator.ContrPreferenceWeight</td><td>{@link Double}</td><td>Group constraint preferences weight</td></tr>
040 * <tr><td>Comparator.RoomPreferenceWeight</td><td>{@link Double}</td><td>Room preferences weight</td></tr>
041 * <tr><td>Comparator.UselessSlotWeight</td><td>{@link Double}</td><td>Useless slots weight</td></tr>
042 * <tr><td>Comparator.TooBigRoomWeight</td><td>{@link Double}</td><td>Too big room weight</td></tr>
043 * <tr><td>Comparator.DistanceInstructorPreferenceWeight</td><td>{@link Double}</td><td>Distance (of the rooms of the back-to-back classes) based instructor preferences weight</td></tr>
044 * <tr><td>Comparator.PerturbationPenaltyWeight</td><td>{@link Double}</td><td>Perturbation penalty (see {@link UniversalPerturbationsCounter})</td></tr>
045 * <tr><td>Comparator.DeptSpreadPenaltyWeight</td><td>{@link Double}</td><td>Department balancing penalty (see {@link net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint})</td></tr>
046 * </table>
047 *
048 *
049 * @version
050 * CourseTT 1.1 (University Course Timetabling)<br>
051 * Copyright (C) 2006 Tomáš Müller<br>
052 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
053 * Lazenska 391, 76314 Zlin, Czech Republic<br>
054 * <br>
055 * This library is free software; you can redistribute it and/or
056 * modify it under the terms of the GNU Lesser General Public
057 * License as published by the Free Software Foundation; either
058 * version 2.1 of the License, or (at your option) any later version.
059 * <br><br>
060 * This library is distributed in the hope that it will be useful,
061 * but WITHOUT ANY WARRANTY; without even the implied warranty of
062 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
063 * Lesser General Public License for more details.
064 * <br><br>
065 * You should have received a copy of the GNU Lesser General Public
066 * License along with this library; if not, write to the Free Software
067 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
068 */
069
070 public class TimetableComparator implements SolutionComparator {
071 protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableComparator.class);
072
073 private double iEmptySingleSlotWeight;
074 public static final String USELESS_SLOT_WEIGHT="Comparator.UselessSlotWeight";
075 private double iTimePreferencesWeight;
076 public static final String TIME_PREFERENCE_WEIGHT="Comparator.TimePreferenceWeight";
077 private double iStudentConflictWeight;
078 public static final String STUDENT_CONFLICT_WEIGHT="Comparator.StudentConflictWeight";
079 private double iRoomPreferencesWeight;
080 public static final String ROOM_PREFERENCE_WEIGHT="Comparator.RoomPreferenceWeight";
081 private double iConstrPreferencesWeight;
082 public static final String CONSTR_PREFERENCE_WEIGHT="Comparator.ContrPreferenceWeight";
083 private double iHardStudentConflictWeight;
084 public static final String HARD_STUDENT_CONFLICT_WEIGHT="Comparator.HardStudentConflictWeight";
085 private double iTooBigRoomWeight;
086 public static final String TOO_BIG_ROOM_WEIGHT = "Comparator.TooBigRoomWeight";
087 private boolean iCompareMpp;
088 public static final String DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT = "Comparator.DistanceInstructorPreferenceWeight";
089 private double iDistanceInstructorPreferenceWeight;
090 public static final String PERTURBATION_PENALTY_WEIGHT = "Comparator.PerturbationPenaltyWeight";
091 private double iPerturbationPenaltyWeight;
092 public static final String DEPT_SPREAD_PENALTY_WEIGHT = "Comparator.DeptSpreadPenaltyWeight";
093 private double iDeptSpreadPenaltyWeight;
094 public static final String SPREAD_PENALTY_WEIGHT = "Comparator.SpreadPenaltyWeight";
095 private double iSpreadPenaltyWeight;
096 public static final String COMMITED_STUDENT_CONFLICT_WEIGHT="Comparator.CommitedStudentConflictWeight";
097 private double iCommitedStudentConflictWeight;
098
099 public TimetableComparator(DataProperties properties) {
100 iEmptySingleSlotWeight = properties.getPropertyDouble(USELESS_SLOT_WEIGHT,0.0);
101 iTimePreferencesWeight = properties.getPropertyDouble(TIME_PREFERENCE_WEIGHT,1.0);
102 iRoomPreferencesWeight = properties.getPropertyDouble(ROOM_PREFERENCE_WEIGHT,0.1);
103 iConstrPreferencesWeight = properties.getPropertyDouble(CONSTR_PREFERENCE_WEIGHT,1.0);
104 if (properties.getPropertyBoolean("General.SwitchStudents",true)) {
105 iHardStudentConflictWeight = properties.getPropertyDouble(HARD_STUDENT_CONFLICT_WEIGHT,1.0);
106 iStudentConflictWeight = properties.getPropertyDouble(STUDENT_CONFLICT_WEIGHT,0.2);
107 } else {
108 iHardStudentConflictWeight = 0.0;
109 iStudentConflictWeight = properties.getPropertyDouble(STUDENT_CONFLICT_WEIGHT,1.0);
110 }
111 iDistanceInstructorPreferenceWeight = properties.getPropertyDouble(DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT, 1.0);
112 iTooBigRoomWeight = properties.getPropertyDouble(TOO_BIG_ROOM_WEIGHT,0.0);
113 iCompareMpp = properties.getPropertyBoolean("General.MPP", false);
114 iPerturbationPenaltyWeight = properties.getPropertyDouble(PERTURBATION_PENALTY_WEIGHT,1.0);
115 iDeptSpreadPenaltyWeight = properties.getPropertyDouble(DEPT_SPREAD_PENALTY_WEIGHT,1.0);
116 iSpreadPenaltyWeight = properties.getPropertyDouble(SPREAD_PENALTY_WEIGHT,1.0);
117 iCommitedStudentConflictWeight = properties.getPropertyDouble(COMMITED_STUDENT_CONFLICT_WEIGHT,1.0);
118 }
119
120 public boolean isBetterThanBestSolution(Solution currentSolution) {
121 if (currentSolution.getBestInfo()==null) return true;
122 TimetableModel tm = (TimetableModel)currentSolution.getModel();
123 int unassigned = tm.unassignedVariables().size();
124 if (tm.getBestUnassignedVariables()!=unassigned)
125 return tm.getBestUnassignedVariables()>unassigned;
126
127 return (currentValue(currentSolution)<bestValue(currentSolution));
128 }
129
130 public double currentValue(Solution currentSolution) {
131 return currentValue((TimetableModel)currentSolution.getModel(),currentSolution.getPerturbationsCounter());
132 }
133
134 public double currentValue(TimetableModel tm, PerturbationsCounter cnt) {
135 int unassigned = tm.unassignedVariables().size();
136
137 int tooBigCurr=0;
138 if (iTooBigRoomWeight!=0.0) tooBigCurr = tm.countTooBigRooms();
139 long uselessSlotsCur=0;
140 if (iEmptySingleSlotWeight!=0.0)
141 uselessSlotsCur = tm.getUselessSlots();
142 long hardSCCurr = 0;
143 if (iHardStudentConflictWeight!=0.0)
144 hardSCCurr = tm.getHardStudentConflicts();
145 double pertCurr=0.0;
146 if (iCompareMpp && iPerturbationPenaltyWeight!=0.0)
147 pertCurr = cnt.getPerturbationPenalty(tm);
148 double deptSpread=0.0;
149 if (iDeptSpreadPenaltyWeight!=0.0)
150 deptSpread = tm.getDepartmentSpreadPenalty();
151 double spread=0.0;
152 if (iSpreadPenaltyWeight!=0.0)
153 spread = tm.getSpreadPenalty();
154 int commitedStudentConflicts = 0;
155 if (iCommitedStudentConflictWeight!=0.0)
156 commitedStudentConflicts = tm.getCommitedStudentConflicts();
157
158 double prefCurr = (iEmptySingleSlotWeight*uselessSlotsCur)+
159 (iTimePreferencesWeight*tm.getGlobalTimePreference())+
160 (iRoomPreferencesWeight*tm.getGlobalRoomPreference())+
161 (iConstrPreferencesWeight*tm.getGlobalGroupConstraintPreference())+
162 (iStudentConflictWeight*tm.getViolatedStudentConflicts())+
163 (iHardStudentConflictWeight*hardSCCurr)+
164 (iTooBigRoomWeight*tooBigCurr)+
165 (iDistanceInstructorPreferenceWeight*tm.getInstructorDistancePreference())+
166 (iPerturbationPenaltyWeight*pertCurr)+
167 (iDeptSpreadPenaltyWeight*deptSpread)+
168 (iSpreadPenaltyWeight*spread)+
169 (iCommitedStudentConflictWeight*commitedStudentConflicts)
170 ;
171 return prefCurr;
172 }
173
174 public double currentValue(TimetableModel tm, PerturbationsCounter cnt, Vector variables) {
175 int unassigned = 0;
176
177 int roomPref = 0;
178 double timePref = 0;
179 double grPref = 0;
180 long allSC = 0, comSC = 0, hardSC = 0;
181 int instPref = 0;
182 int spreadPen = 0, deptSpreadPen = 0;
183 int tooBigRooms = 0;
184 int uselessSlots = 0;
185 double pertCurr = 0;
186
187 if (iCompareMpp && iPerturbationPenaltyWeight!=0.0)
188 pertCurr = cnt.getPerturbationPenalty(tm, variables);
189
190 HashSet used = new HashSet();
191
192 for (Enumeration e=variables.elements();e.hasMoreElements();) {
193 Lecture lecture = (Lecture)e.nextElement();
194 Placement placement = (Placement)lecture.getAssignment();
195
196 if (placement!=null) {
197 roomPref += placement.getRoomPreference();
198 timePref += placement.getTimeLocation().getNormalizedPreference();
199 comSC += lecture.getCommitedConflicts(placement);
200 tooBigRooms += placement.getTooBigRoomPreference();
201 } else {
202 unassigned ++;
203 }
204
205 for (Enumeration f=lecture.constraints().elements();f.hasMoreElements();) {
206 Constraint c = (Constraint)f.nextElement();
207 if (!used.add(c)) continue;
208
209 if (c instanceof InstructorConstraint) {
210 InstructorConstraint ic = (InstructorConstraint)c;
211 instPref += ic.getPreference();
212 }
213
214 if (c instanceof DepartmentSpreadConstraint) {
215 DepartmentSpreadConstraint dsc = (DepartmentSpreadConstraint)c;
216 deptSpreadPen += dsc.getPenalty();
217 } else if (c instanceof SpreadConstraint) {
218 SpreadConstraint sc = (SpreadConstraint)c;
219 spreadPen += sc.getPenalty();
220 }
221
222 if (c instanceof GroupConstraint) {
223 GroupConstraint gc = (GroupConstraint)c;
224 grPref += gc.getCurrentPreference();
225 }
226
227 if (c instanceof JenrlConstraint) {
228 JenrlConstraint jc = (JenrlConstraint)c;
229 if (!jc.isInConflict()) continue;
230 Lecture l1 = (Lecture)jc.first();
231 Lecture l2 = (Lecture)jc.second();
232 allSC += jc.getJenrl();
233 if (l1.areStudentConflictsHard(l2))
234 hardSC += jc.getJenrl();
235 }
236
237 if (c instanceof RoomConstraint) {
238 RoomConstraint rc = (RoomConstraint)c;
239 uselessSlots+=rc.countUselessSlots();
240 }
241 }
242 }
243
244 double prefCurr = (iEmptySingleSlotWeight*uselessSlots)+
245 (iTimePreferencesWeight*timePref)+
246 (iRoomPreferencesWeight*roomPref)+
247 (iConstrPreferencesWeight*grPref)+
248 (iStudentConflictWeight*allSC)+
249 (iHardStudentConflictWeight*hardSC)+
250 (iTooBigRoomWeight*tooBigRooms)+
251 (iDistanceInstructorPreferenceWeight*instPref)+
252 (iPerturbationPenaltyWeight*pertCurr)+
253 (iDeptSpreadPenaltyWeight*deptSpreadPen)+
254 (iSpreadPenaltyWeight*spreadPen)+
255 (iCommitedStudentConflictWeight*comSC)
256 ;
257 return prefCurr;
258 }
259
260 public double bestValue(Solution currentSolution) {
261 TimetableModel tm = (TimetableModel)currentSolution.getModel();
262 int unassigned = tm.unassignedVariables().size();
263
264 int tooBigBest=0;
265 if (iTooBigRoomWeight!=0.0)
266 tooBigBest = tm.bestTooBigRooms();
267 long uselessSlotsBest=0;
268 if (iEmptySingleSlotWeight!=0.0)
269 uselessSlotsBest = tm.bestUselessSlots();
270 long hardSCBest = 0;
271 if (iHardStudentConflictWeight!=0.0)
272 hardSCBest = tm.bestHardStudentConflicts();
273 double pertBest=0.0;
274 if (iCompareMpp && iPerturbationPenaltyWeight!=0.0)
275 pertBest = currentSolution.getBestPerturbationsPenalty();
276 double deptSpreadBest=0.0;
277 if (iDeptSpreadPenaltyWeight!=0.0)
278 deptSpreadBest = tm.bestDepartmentSpreadPenalty();
279 double spread=0.0;
280 if (iSpreadPenaltyWeight!=0.0)
281 spread = tm.bestSpreadPenalty();
282 int commitedStudentConflicts = 0;
283 if (iCommitedStudentConflictWeight!=0.0)
284 commitedStudentConflicts = tm.bestCommitedStudentConflicts();
285
286 double prefBest = (iEmptySingleSlotWeight*uselessSlotsBest)+
287 (iTimePreferencesWeight*tm.bestGlobalTimePreference())+
288 (iRoomPreferencesWeight*tm.bestGlobalRoomPreference())+
289 (iConstrPreferencesWeight*tm.bestGlobalGroupConstraintPreference())+
290 (iStudentConflictWeight*tm.bestViolatedStudentConflicts())+
291 (iHardStudentConflictWeight*hardSCBest)+
292 (iTooBigRoomWeight*tooBigBest)+
293 (iDistanceInstructorPreferenceWeight*tm.bestInstructorDistancePreference())+
294 (iPerturbationPenaltyWeight*pertBest)+
295 (iDeptSpreadPenaltyWeight*deptSpreadBest)+
296 (iSpreadPenaltyWeight*spread)+
297 (iCommitedStudentConflictWeight*commitedStudentConflicts)
298 ;
299 return prefBest;
300 }
301
302 public double value(Placement placement, PerturbationsCounter cnt) {
303 Lecture lecture = (Lecture)placement.variable();
304
305 int constrPreference = 0;
306 if (iConstrPreferencesWeight!=0.0) {
307 for (Iterator i=lecture.groupConstraints().iterator();i.hasNext();) {
308 GroupConstraint gc = (GroupConstraint)i.next();
309 constrPreference += gc.getCurrentPreference(placement);
310 }
311 }
312
313 int distInstrPref = 0;
314 if (iDistanceInstructorPreferenceWeight!=0.0) {
315 for (Enumeration e=lecture.constraints().elements();e.hasMoreElements();) {
316 Constraint constraint = (Constraint)e.nextElement();
317 if (constraint instanceof InstructorConstraint) {
318 distInstrPref += ((InstructorConstraint)constraint).getPreference(placement);
319 }
320 }
321 }
322
323 return
324 (iEmptySingleSlotWeight==0.0?0.0:iEmptySingleSlotWeight*placement.nrUselessHalfHours())+
325 (iTimePreferencesWeight==0.0?0.0:iTimePreferencesWeight*placement.getTimeLocation().getNormalizedPreference())+
326 (iRoomPreferencesWeight==0.0?0.0:iRoomPreferencesWeight*placement.sumRoomPreference())+
327 (iConstrPreferencesWeight*constrPreference)+
328 (iStudentConflictWeight==0.0?0.0:iStudentConflictWeight*lecture.countStudentConflicts(placement))+
329 (iHardStudentConflictWeight==0.0?0.0:iHardStudentConflictWeight*lecture.countHardStudentConflicts(placement))+
330 (iTooBigRoomWeight==0.0?0.0:iTooBigRoomWeight*placement.getTooBigRoomPreference())+
331 (iDistanceInstructorPreferenceWeight*distInstrPref)+
332 (iPerturbationPenaltyWeight==0.0 || cnt==null?0.0:iPerturbationPenaltyWeight*cnt.getPerturbationPenalty(lecture.getModel(),placement,new Vector(0)))+
333 (iDeptSpreadPenaltyWeight==0.0 || lecture.getDeptSpreadConstraint()==null?0.0:iDeptSpreadPenaltyWeight*lecture.getDeptSpreadConstraint().getPenalty(placement))+
334 (iSpreadPenaltyWeight==0.0?0.0:iSpreadPenaltyWeight*placement.getSpreadPenalty())+
335 (iCommitedStudentConflictWeight==0.0?0.0:iCommitedStudentConflictWeight*lecture.getCommitedConflicts(placement))
336 ;
337 }
338 }