001 package net.sf.cpsolver.coursett.model; 002 003 import java.util.ArrayList; 004 import java.util.Collection; 005 import java.util.HashSet; 006 import java.util.HashMap; 007 import java.util.List; 008 import java.util.Locale; 009 import java.util.Map; 010 import java.util.Set; 011 012 import net.sf.cpsolver.coursett.Constants; 013 import net.sf.cpsolver.coursett.constraint.ClassLimitConstraint; 014 import net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint; 015 import net.sf.cpsolver.coursett.constraint.GroupConstraint; 016 import net.sf.cpsolver.coursett.constraint.InstructorConstraint; 017 import net.sf.cpsolver.coursett.constraint.JenrlConstraint; 018 import net.sf.cpsolver.coursett.constraint.RoomConstraint; 019 import net.sf.cpsolver.coursett.constraint.SpreadConstraint; 020 import net.sf.cpsolver.coursett.constraint.WeakeningConstraint; 021 import net.sf.cpsolver.coursett.criteria.BackToBackInstructorPreferences; 022 import net.sf.cpsolver.coursett.criteria.BrokenTimePatterns; 023 import net.sf.cpsolver.coursett.criteria.DepartmentBalancingPenalty; 024 import net.sf.cpsolver.coursett.criteria.DistributionPreferences; 025 import net.sf.cpsolver.coursett.criteria.Perturbations; 026 import net.sf.cpsolver.coursett.criteria.RoomPreferences; 027 import net.sf.cpsolver.coursett.criteria.RoomViolations; 028 import net.sf.cpsolver.coursett.criteria.SameSubpartBalancingPenalty; 029 import net.sf.cpsolver.coursett.criteria.StudentCommittedConflict; 030 import net.sf.cpsolver.coursett.criteria.StudentConflict; 031 import net.sf.cpsolver.coursett.criteria.StudentDistanceConflict; 032 import net.sf.cpsolver.coursett.criteria.StudentHardConflict; 033 import net.sf.cpsolver.coursett.criteria.StudentOverlapConflict; 034 import net.sf.cpsolver.coursett.criteria.TimePreferences; 035 import net.sf.cpsolver.coursett.criteria.TimeViolations; 036 import net.sf.cpsolver.coursett.criteria.TooBigRooms; 037 import net.sf.cpsolver.coursett.criteria.UselessHalfHours; 038 import net.sf.cpsolver.coursett.criteria.placement.AssignmentCount; 039 import net.sf.cpsolver.coursett.criteria.placement.DeltaTimePreference; 040 import net.sf.cpsolver.coursett.criteria.placement.HardConflicts; 041 import net.sf.cpsolver.coursett.criteria.placement.PotentialHardConflicts; 042 import net.sf.cpsolver.coursett.criteria.placement.WeightedHardConflicts; 043 import net.sf.cpsolver.ifs.constant.ConstantModel; 044 import net.sf.cpsolver.ifs.criteria.Criterion; 045 import net.sf.cpsolver.ifs.model.Constraint; 046 import net.sf.cpsolver.ifs.model.GlobalConstraint; 047 import net.sf.cpsolver.ifs.util.DataProperties; 048 import net.sf.cpsolver.ifs.util.DistanceMetric; 049 050 /** 051 * Timetable model. 052 * 053 * @version CourseTT 1.2 (University Course Timetabling)<br> 054 * Copyright (C) 2006 - 2010 Tomas Muller<br> 055 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 056 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 057 * <br> 058 * This library is free software; you can redistribute it and/or modify 059 * it under the terms of the GNU Lesser General Public License as 060 * published by the Free Software Foundation; either version 3 of the 061 * License, or (at your option) any later version. <br> 062 * <br> 063 * This library is distributed in the hope that it will be useful, but 064 * WITHOUT ANY WARRANTY; without even the implied warranty of 065 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 066 * Lesser General Public License for more details. <br> 067 * <br> 068 * You should have received a copy of the GNU Lesser General Public 069 * License along with this library; if not see 070 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 071 */ 072 073 public class TimetableModel extends ConstantModel<Lecture, Placement> { 074 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableModel.class); 075 private static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00", 076 new java.text.DecimalFormatSymbols(Locale.US)); 077 078 private List<InstructorConstraint> iInstructorConstraints = new ArrayList<InstructorConstraint>(); 079 private List<JenrlConstraint> iJenrlConstraints = new ArrayList<JenrlConstraint>(); 080 private List<RoomConstraint> iRoomConstraints = new ArrayList<RoomConstraint>(); 081 private List<DepartmentSpreadConstraint> iDepartmentSpreadConstraints = new ArrayList<DepartmentSpreadConstraint>(); 082 private List<SpreadConstraint> iSpreadConstraints = new ArrayList<SpreadConstraint>(); 083 private List<GroupConstraint> iGroupConstraints = new ArrayList<GroupConstraint>(); 084 private List<ClassLimitConstraint> iClassLimitConstraints = new ArrayList<ClassLimitConstraint>(); 085 private DataProperties iProperties = null; 086 private int iYear = -1; 087 088 private HashSet<Student> iAllStudents = new HashSet<Student>(); 089 090 private DistanceMetric iDistanceMetric = null; 091 092 093 public TimetableModel(DataProperties properties) { 094 super(); 095 iProperties = properties; 096 iDistanceMetric = new DistanceMetric(properties); 097 if (properties.getPropertyBoolean("OnFlySectioning.Enabled", false)) 098 addModelListener(new OnFlySectioning(this)); 099 String criteria = properties.getProperty("General.Criteria", 100 // Objectives 101 StudentConflict.class.getName() + ";" + 102 StudentDistanceConflict.class.getName() + ";" + 103 StudentHardConflict.class.getName() + ";" + 104 StudentCommittedConflict.class.getName() + ";" + 105 StudentOverlapConflict.class.getName() + ";" + 106 UselessHalfHours.class.getName() + ";" + 107 BrokenTimePatterns.class.getName() + ";" + 108 TooBigRooms.class.getName() + ";" + 109 TimePreferences.class.getName() + ";" + 110 RoomPreferences.class.getName() + ";" + 111 DistributionPreferences.class.getName() + ";" + 112 SameSubpartBalancingPenalty.class.getName() + ";" + 113 DepartmentBalancingPenalty.class.getName() + ";" + 114 BackToBackInstructorPreferences.class.getName() + ";" + 115 Perturbations.class.getName() + ";" + 116 // Additional placement selection criteria 117 AssignmentCount.class.getName() + ";" + 118 DeltaTimePreference.class.getName() + ";" + 119 HardConflicts.class.getName() + ";" + 120 PotentialHardConflicts.class.getName() + ";" + 121 WeightedHardConflicts.class.getName()); 122 // Interactive mode -- count time / room violations 123 if (properties.getPropertyBoolean("General.InteractiveMode", false)) 124 criteria += ";" + TimeViolations.class.getName() + ";" + RoomViolations.class.getName(); 125 // Additional (custom) criteria 126 criteria += ";" + properties.getProperty("General.AdditionalCriteria", ""); 127 for (String criterion: criteria.split("\\;")) { 128 if (criterion == null || criterion.isEmpty()) continue; 129 try { 130 @SuppressWarnings("unchecked") 131 Class<Criterion<Lecture, Placement>> clazz = (Class<Criterion<Lecture, Placement>>)Class.forName(criterion); 132 addCriterion(clazz.newInstance()); 133 } catch (Exception e) { 134 sLogger.error("Unable to use " + criterion + ": " + e.getMessage()); 135 } 136 } 137 } 138 139 public DistanceMetric getDistanceMetric() { 140 return iDistanceMetric; 141 } 142 143 public DataProperties getProperties() { 144 return iProperties; 145 } 146 147 /** 148 * Student final sectioning (switching students between sections of the same 149 * class in order to minimize overall number of student conflicts) 150 */ 151 public void switchStudents() { 152 FinalSectioning sect = new FinalSectioning(this); 153 sect.run(); 154 } 155 156 @Override 157 public String toString() { 158 return "TimetableModel{" + "\n super=" + super.toString() 159 + "\n studentConflicts=" + sDoubleFormat.format(getCriterion(StudentConflict.class).getValue()) 160 + "\n roomPreferences=" + sDoubleFormat.format(getCriterion(RoomPreferences.class).getValue()) 161 + "\n timePreferences=" + sDoubleFormat.format(getCriterion(TimePreferences.class).getValue()) 162 + "\n groupConstraintPreferences=" + sDoubleFormat.format(getCriterion(DistributionPreferences.class).getValue()) 163 + "\n}"; 164 } 165 166 public Map<String, String> getBounds() { 167 Map<String, String> ret = new HashMap<String, String>(); 168 ret.put("Room preferences min", "" + getCriterion(RoomPreferences.class).getBounds()[0]); 169 ret.put("Room preferences max", "" + getCriterion(RoomPreferences.class).getBounds()[1]); 170 ret.put("Time preferences min", "" + getCriterion(TimePreferences.class).getBounds()[0]); 171 ret.put("Time preferences max", "" + getCriterion(TimePreferences.class).getBounds()[1]); 172 ret.put("Distribution preferences min", "" + getCriterion(DistributionPreferences.class).getBounds()[0]); 173 ret.put("Distribution preferences max", "" + getCriterion(DistributionPreferences.class).getBounds()[1]); 174 if (getProperties().getPropertyBoolean("General.UseDistanceConstraints", false)) { 175 ret.put("Back-to-back instructor preferences max", "" + getCriterion(BackToBackInstructorPreferences.class).getBounds()[1]); 176 } 177 ret.put("Too big rooms max", "" + getCriterion(TooBigRooms.class).getBounds()[0]); 178 ret.put("Useless half-hours", "" + getCriterion(UselessHalfHours.class).getBounds()[0]); 179 return ret; 180 } 181 182 /** Global info */ 183 @Override 184 public Map<String, String> getInfo() { 185 Map<String, String> ret = super.getInfo(); 186 ret.put("Memory usage", getMem()); 187 188 Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class); 189 Criterion<Lecture, Placement> rv = getCriterion(RoomViolations.class); 190 ret.put("Room preferences", getPerc(rp.getValue(), rp.getBounds()[0], rp.getBounds()[1]) + "% (" + Math.round(rp.getValue()) + ")" 191 + (rv != null && rv.getValue() >= 0.5 ? " [hard:" + Math.round(rv.getValue()) + "]" : "")); 192 193 Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class); 194 Criterion<Lecture, Placement> tv = getCriterion(TimeViolations.class); 195 ret.put("Time preferences", getPerc(tp.getValue(), tp.getBounds()[0], tp.getBounds()[1]) + "% (" + sDoubleFormat.format(tp.getValue()) + ")" 196 + (tv != null && tv.getValue() >= 0.5 ? " [hard:" + Math.round(tv.getValue()) + "]" : "")); 197 198 Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class); 199 ret.put("Distribution preferences", getPerc(dp.getValue(), dp.getBounds()[0], dp.getBounds()[1]) + "% (" + sDoubleFormat.format(dp.getValue()) + ")"); 200 201 Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class); 202 Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class); 203 Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class); 204 Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class); 205 ret.put("Student conflicts", Math.round(scc.getValue() + sc.getValue()) + 206 " [committed:" + Math.round(scc.getValue()) + 207 ", distance:" + Math.round(sdc.getValue()) + 208 ", hard:" + Math.round(shc.getValue()) + "]"); 209 210 if (!getSpreadConstraints().isEmpty()) { 211 Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class); 212 ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(), ip.getBounds()[0], ip.getBounds()[1]) + "% (" + Math.round(ip.getValue()) + ")"); 213 } 214 215 if (!getDepartmentSpreadConstraints().isEmpty()) { 216 Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class); 217 ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue())); 218 } 219 220 Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class); 221 ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue())); 222 223 Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class); 224 ret.put("Too big rooms", getPercRev(tbr.getValue(), tbr.getBounds()[1], tbr.getBounds()[0]) + "% (" + Math.round(tbr.getValue()) + ")"); 225 226 Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class); 227 Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class); 228 229 ret.put("Useless half-hours", getPercRev(uh.getValue() + bt.getValue(), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds()[0]) + 230 "% (" + Math.round(uh.getValue()) + " + " + Math.round(bt.getValue()) + ")"); 231 return ret; 232 } 233 234 @Override 235 public Map<String, String> getInfo(Collection<Lecture> variables) { 236 Map<String, String> ret = super.getInfo(variables); 237 238 ret.put("Memory usage", getMem()); 239 240 Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class); 241 ret.put("Room preferences", getPerc(rp.getValue(variables), rp.getBounds(variables)[0], rp.getBounds(variables)[1]) + "% (" + Math.round(rp.getValue(variables)) + ")"); 242 243 Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class); 244 ret.put("Time preferences", getPerc(tp.getValue(variables), tp.getBounds(variables)[0], tp.getBounds(variables)[1]) + "% (" + sDoubleFormat.format(tp.getValue(variables)) + ")"); 245 246 Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class); 247 ret.put("Distribution preferences", getPerc(dp.getValue(variables), dp.getBounds(variables)[0], dp.getBounds(variables)[1]) + "% (" + sDoubleFormat.format(dp.getValue(variables)) + ")"); 248 249 Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class); 250 Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class); 251 Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class); 252 Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class); 253 ret.put("Student conflicts", Math.round(scc.getValue(variables) + sc.getValue(variables)) + 254 " [committed:" + Math.round(scc.getValue(variables)) + 255 ", distance:" + Math.round(sdc.getValue(variables)) + 256 ", hard:" + Math.round(shc.getValue(variables)) + "]"); 257 258 if (!getSpreadConstraints().isEmpty()) { 259 Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class); 260 ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(variables), ip.getBounds(variables)[0], ip.getBounds(variables)[1]) + "% (" + Math.round(ip.getValue(variables)) + ")"); 261 } 262 263 if (!getDepartmentSpreadConstraints().isEmpty()) { 264 Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class); 265 ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue(variables))); 266 } 267 268 Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class); 269 ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue(variables))); 270 271 Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class); 272 ret.put("Too big rooms", getPercRev(tbr.getValue(variables), tbr.getBounds(variables)[1], tbr.getBounds(variables)[0]) + "% (" + Math.round(tbr.getValue(variables)) + ")"); 273 274 Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class); 275 Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class); 276 277 ret.put("Useless half-hours", getPercRev(uh.getValue(variables) + bt.getValue(variables), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds(variables)[0]) + 278 "% (" + Math.round(uh.getValue(variables)) + " + " + Math.round(bt.getValue(variables)) + ")"); 279 return ret; 280 } 281 282 @Override 283 public void addConstraint(Constraint<Lecture, Placement> constraint) { 284 super.addConstraint(constraint); 285 if (constraint instanceof InstructorConstraint) { 286 iInstructorConstraints.add((InstructorConstraint) constraint); 287 } else if (constraint instanceof JenrlConstraint) { 288 iJenrlConstraints.add((JenrlConstraint) constraint); 289 } else if (constraint instanceof RoomConstraint) { 290 iRoomConstraints.add((RoomConstraint) constraint); 291 } else if (constraint instanceof DepartmentSpreadConstraint) { 292 iDepartmentSpreadConstraints.add((DepartmentSpreadConstraint) constraint); 293 } else if (constraint instanceof SpreadConstraint) { 294 iSpreadConstraints.add((SpreadConstraint) constraint); 295 } else if (constraint instanceof ClassLimitConstraint) { 296 iClassLimitConstraints.add((ClassLimitConstraint) constraint); 297 } else if (constraint instanceof GroupConstraint) { 298 iGroupConstraints.add((GroupConstraint) constraint); 299 } 300 } 301 302 @Override 303 public void removeConstraint(Constraint<Lecture, Placement> constraint) { 304 super.removeConstraint(constraint); 305 if (constraint instanceof InstructorConstraint) { 306 iInstructorConstraints.remove(constraint); 307 } else if (constraint instanceof JenrlConstraint) { 308 iJenrlConstraints.remove(constraint); 309 } else if (constraint instanceof RoomConstraint) { 310 iRoomConstraints.remove(constraint); 311 } else if (constraint instanceof DepartmentSpreadConstraint) { 312 iDepartmentSpreadConstraints.remove(constraint); 313 } else if (constraint instanceof SpreadConstraint) { 314 iSpreadConstraints.remove(constraint); 315 } else if (constraint instanceof ClassLimitConstraint) { 316 iClassLimitConstraints.remove(constraint); 317 } else if (constraint instanceof GroupConstraint) { 318 iGroupConstraints.remove(constraint); 319 } 320 } 321 322 /** The list of all instructor constraints */ 323 public List<InstructorConstraint> getInstructorConstraints() { 324 return iInstructorConstraints; 325 } 326 327 /** The list of all group constraints */ 328 public List<GroupConstraint> getGroupConstraints() { 329 return iGroupConstraints; 330 } 331 332 /** The list of all jenrl constraints */ 333 public List<JenrlConstraint> getJenrlConstraints() { 334 return iJenrlConstraints; 335 } 336 337 /** The list of all room constraints */ 338 public List<RoomConstraint> getRoomConstraints() { 339 return iRoomConstraints; 340 } 341 342 /** The list of all departmental spread constraints */ 343 public List<DepartmentSpreadConstraint> getDepartmentSpreadConstraints() { 344 return iDepartmentSpreadConstraints; 345 } 346 347 public List<SpreadConstraint> getSpreadConstraints() { 348 return iSpreadConstraints; 349 } 350 351 public List<ClassLimitConstraint> getClassLimitConstraints() { 352 return iClassLimitConstraints; 353 } 354 @Override 355 public double getTotalValue() { 356 double ret = 0; 357 for (Criterion<Lecture, Placement> criterion: getCriteria()) 358 ret += criterion.getWeightedValue(); 359 return ret; 360 } 361 362 @Override 363 public double getTotalValue(Collection<Lecture> variables) { 364 double ret = 0; 365 for (Criterion<Lecture, Placement> criterion: getCriteria()) 366 ret += criterion.getWeightedValue(variables); 367 return ret; 368 } 369 370 public int getYear() { 371 return iYear; 372 } 373 374 public void setYear(int year) { 375 iYear = year; 376 } 377 378 public Set<Student> getAllStudents() { 379 return iAllStudents; 380 } 381 382 public void addStudent(Student student) { 383 iAllStudents.add(student); 384 } 385 386 public void removeStudent(Student student) { 387 iAllStudents.remove(student); 388 } 389 390 /** 391 * Returns amount of allocated memory. 392 * 393 * @return amount of allocated memory to be written in the log 394 */ 395 public static synchronized String getMem() { 396 Runtime rt = Runtime.getRuntime(); 397 return sDoubleFormat.format(((double) (rt.totalMemory() - rt.freeMemory())) / 1048576) + "M"; 398 } 399 400 401 /** 402 * Returns the set of conflicting variables with this value, if it is 403 * assigned to its variable. Conflicts with constraints that implement 404 * {@link WeakeningConstraint} are ignored. 405 */ 406 public Set<Placement> conflictValuesSkipWeakeningConstraints(Placement value) { 407 Set<Placement> conflictValues = new HashSet<Placement>(); 408 for (Constraint<Lecture, Placement> constraint : value.variable().hardConstraints()) { 409 if (constraint instanceof WeakeningConstraint) continue; 410 constraint.computeConflicts(value, conflictValues); 411 } 412 for (GlobalConstraint<Lecture, Placement> constraint : globalConstraints()) { 413 if (constraint instanceof WeakeningConstraint) continue; 414 constraint.computeConflicts(value, conflictValues); 415 } 416 return conflictValues; 417 } 418 419 420 /** 421 * Weaken all weakening constraint so that the given value can be assigned without 422 * them creating a conflict using {@link WeakeningConstraint#weaken(Placement)}. 423 * This method is handy for instance when an existing solution is being loaded 424 * into the solver. 425 */ 426 public void weaken(Placement value) { 427 for (Constraint<Lecture, Placement> constraint : value.variable().hardConstraints()) { 428 if (constraint instanceof WeakeningConstraint) 429 ((WeakeningConstraint)constraint).weaken(value); 430 } 431 for (GlobalConstraint<Lecture, Placement> constraint : globalConstraints()) { 432 if (constraint instanceof WeakeningConstraint) 433 ((WeakeningConstraint)constraint).weaken(value); 434 } 435 } 436 }