001package org.cpsolver.coursett.constraint; 002 003import java.util.HashSet; 004import java.util.Set; 005 006import org.cpsolver.coursett.criteria.StudentConflict; 007import org.cpsolver.coursett.model.Lecture; 008import org.cpsolver.coursett.model.Placement; 009import org.cpsolver.coursett.model.Student; 010import org.cpsolver.coursett.model.TimetableModel; 011import org.cpsolver.ifs.assignment.Assignment; 012import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 013import org.cpsolver.ifs.assignment.context.BinaryConstraintWithContext; 014import org.cpsolver.ifs.criteria.Criterion; 015import org.cpsolver.ifs.model.Model; 016import org.cpsolver.ifs.model.WeakeningConstraint; 017import org.cpsolver.ifs.util.DataProperties; 018import org.cpsolver.ifs.util.DistanceMetric; 019import org.cpsolver.ifs.util.ToolBox; 020 021 022/** 023 * Join student enrollment constraint. <br> 024 * This constraint is placed between all pairs of classes where there is at 025 * least one student attending both classes. It represents a number of student 026 * conflicts (number of joined enrollments), if the given two classes overlap in 027 * time. <br> 028 * Also, it dynamically maintains the counter of all student conflicts. It is a 029 * soft constraint. 030 * 031 * 032 * @version CourseTT 1.3 (University Course Timetabling)<br> 033 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 034 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 035 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 036 * <br> 037 * This library is free software; you can redistribute it and/or modify 038 * it under the terms of the GNU Lesser General Public License as 039 * published by the Free Software Foundation; either version 3 of the 040 * License, or (at your option) any later version. <br> 041 * <br> 042 * This library is distributed in the hope that it will be useful, but 043 * WITHOUT ANY WARRANTY; without even the implied warranty of 044 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 045 * Lesser General Public License for more details. <br> 046 * <br> 047 * You should have received a copy of the GNU Lesser General Public 048 * License along with this library; if not see 049 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 050 */ 051 052public class JenrlConstraint extends BinaryConstraintWithContext<Lecture, Placement, JenrlConstraint.JenrlConstraintContext> implements WeakeningConstraint<Lecture, Placement> { 053 private double iJenrl = 0.0; 054 private double iPriority = 0.0; 055 private Set<Student> iStudents = new HashSet<Student>(); 056 private Set<Student> iInstructors = new HashSet<Student>(); 057 private double iJenrlMaxConflicts = 1.0; 058 private double iJenrlMaxConflictsWeaken = 0.001; 059 060 /** 061 * Constructor 062 */ 063 public JenrlConstraint() { 064 super(); 065 } 066 067 @Override 068 public void setModel(Model<Lecture, Placement> model) { 069 super.setModel(model); 070 if (model != null && model instanceof TimetableModel) { 071 DataProperties config = ((TimetableModel)model).getProperties(); 072 iJenrlMaxConflicts = config.getPropertyDouble("General.JenrlMaxConflicts", 1.0); 073 iJenrlMaxConflictsWeaken = config.getPropertyDouble("General.JenrlMaxConflictsWeaken", 0.001); 074 } 075 } 076 077 @Override 078 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 079 if (!getContext(assignment).isOverLimit() || value.variable().isCommitted()) return; 080 Lecture other = another(value.variable()); 081 if (other == null) return; 082 Placement otherPlacement = assignment.getValue(other); 083 if (otherPlacement != null && !other.isCommitted() && isInConflict(value, otherPlacement, getDistanceMetric(), getWorkDayLimit())) 084 conflicts.add(otherPlacement); 085 } 086 087 @Override 088 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) { 089 if (!getContext(assignment).isOverLimit() || value.variable().isCommitted()) return false; 090 Lecture other = another(value.variable()); 091 if (other == null) return false; 092 Placement otherPlacement = assignment.getValue(other); 093 return otherPlacement != null && !other.isCommitted() && isInConflict(value, otherPlacement, getDistanceMetric(), getWorkDayLimit()); 094 } 095 096 /** 097 * Returns true if the given placements are overlapping or they are 098 * back-to-back and too far for students. 099 * @param p1 first placement 100 * @param p2 second placement 101 * @param m distance metrics 102 * @param workDayLimit limit on the work-day 103 * @return true if there is a student conflict between the two placements 104 */ 105 public static boolean isInConflict(Placement p1, Placement p2, DistanceMetric m, int workDayLimit) { 106 return p1 != null && p2 != null && !StudentConflict.ignore(p1.variable(), p2.variable()) && (StudentConflict.distance(m, p1, p2) || StudentConflict.overlaps(p1, p2) || StudentConflict.workday(workDayLimit, p1, p2)); 107 } 108 109 /** 110 * Number of joined enrollments if the given value is assigned to the given 111 * variable 112 * @param assignment current assignment 113 * @param variable a class 114 * @param value class placement under consideration 115 * @return number of student conflicts caused by this constraint if assigned 116 */ 117 public long jenrl(Assignment<Lecture, Placement> assignment, Lecture variable, Placement value) { 118 Lecture other = (first().equals(variable) ? second() : first()); 119 Placement otherPlacement = (other == null ? null : assignment.getValue(other)); 120 return (otherPlacement != null && isInConflict(value, otherPlacement, getDistanceMetric(), getWorkDayLimit()) ? Math.round(iJenrl) : 0); 121 } 122 123 private DistanceMetric getDistanceMetric() { 124 return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric()); 125 } 126 127 private int getWorkDayLimit() { 128 return (getModel() == null ? -1 : ((TimetableModel)getModel()).getStudentWorkDayLimit()); 129 } 130 131 /** True if the given two lectures overlap in time 132 * @param assignment current assignment 133 * @return true if this constraint is conflicting 134 **/ 135 public boolean isInConflict(Assignment<Lecture, Placement> assignment) { 136 return getContext(assignment).isConflicting(); 137 } 138 139 /** 140 * Increment the number of joined enrollments (during student final 141 * sectioning) 142 * @param assignment current assignment 143 * @param student student added in between the two classes of this constraint 144 */ 145 public void incJenrl(Assignment<Lecture, Placement> assignment, Student student) { 146 JenrlConstraintContext context = getContext(assignment); 147 boolean hard = context.isOverLimit(); 148 double jenrlWeight = student.getJenrlWeight(first(), second()); 149 iJenrl += jenrlWeight; 150 Double conflictPriority = student.getConflictingPriorty(first(), second()); 151 if (conflictPriority != null) iPriority += conflictPriority * jenrlWeight; 152 iStudents.add(student); 153 if (student.getInstructor() != null && (student.getInstructor().variables().contains(first()) || 154 student.getInstructor().variables().contains(second()))) 155 iInstructors.add(student); 156 for (Criterion<Lecture, Placement> criterion: getModel().getCriteria()) 157 if (criterion instanceof StudentConflict) 158 ((StudentConflict)criterion).incJenrl(assignment, this, jenrlWeight, conflictPriority, student); 159 if (!hard && context.isOverLimit() && isInConflict(assignment)) { 160 context.incLimit(jenrlWeight); 161 } 162 } 163 164 public double getJenrlWeight(Student student) { 165 return student.getJenrlWeight(first(), second()); 166 } 167 168 /** 169 * Decrement the number of joined enrollments (during student final 170 * sectioning) 171 * @param assignment current assignment 172 * @param student student removed from between the two classes of this constraint 173 */ 174 public void decJenrl(Assignment<Lecture, Placement> assignment, Student student) { 175 JenrlConstraintContext context = getContext(assignment); 176 boolean hard = context.isOverLimit(); 177 double jenrlWeight = student.getJenrlWeight(first(), second()); 178 iJenrl -= jenrlWeight; 179 Double conflictPriority = student.getConflictingPriorty(first(), second()); 180 if (conflictPriority != null) iPriority -= conflictPriority * jenrlWeight; 181 iStudents.remove(student); 182 iInstructors.remove(student); 183 for (Criterion<Lecture, Placement> criterion: getModel().getCriteria()) 184 if (criterion instanceof StudentConflict) 185 ((StudentConflict)criterion).incJenrl(assignment, this, -jenrlWeight, conflictPriority, student); 186 if (hard && !context.isOverLimit()) 187 context.decLimit(jenrlWeight); 188 } 189 190 /** Number of joined enrollments (during student final sectioning) 191 * @return number of joined enrollments 192 **/ 193 public long getJenrl() { 194 return Math.round(iJenrl); 195 } 196 197 public double jenrl() { 198 return iJenrl; 199 } 200 201 public double priority() { 202 return iPriority; 203 } 204 205 public int getNrStudents() { 206 return iStudents.size(); 207 } 208 209 public Set<Student> getStudents() { 210 return iStudents; 211 } 212 213 public int getNrInstructors() { 214 return iInstructors.size(); 215 } 216 217 public Set<Student> getInstructors() { 218 return iInstructors; 219 } 220 221 @Override 222 public boolean isHard() { 223 return true; 224 } 225 226 @Override 227 public String getName() { 228 return "Join Enrollment"; 229 } 230 231 @Override 232 public String toString() { 233 return "Join Enrollment between " + first().getName() + " and " + second().getName(); 234 } 235 236 public boolean areStudentConflictsHard() { 237 return StudentConflict.hard(first(), second()); 238 } 239 240 public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment) { 241 return StudentConflict.distance(getDistanceMetric(), assignment.getValue(first()), assignment.getValue(second())); 242 } 243 244 public boolean areStudentConflictsCommitted() { 245 return StudentConflict.committed(first(), second()); 246 } 247 248 public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment, Placement value) { 249 return StudentConflict.distance(getDistanceMetric(), value, assignment.getValue(another(value.variable()))); 250 } 251 252 public boolean areStudentConflictsWorkday(Assignment<Lecture, Placement> assignment, Placement value) { 253 return StudentConflict.workday(getWorkDayLimit(), value, assignment.getValue(another(value.variable()))); 254 } 255 256 public boolean isOfTheSameProblem() { 257 return ToolBox.equals(first().getSolverGroupId(), second().getSolverGroupId()); 258 } 259 260 @Override 261 public void weaken(Assignment<Lecture, Placement> assignment) { 262 getContext(assignment).weaken(); 263 } 264 265 @Override 266 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 267 getContext(assignment).weaken(assignment, value); 268 } 269 270 /** 271 * Returns true if there is {@link IgnoreStudentConflictsConstraint} between the two lectures. 272 * @return true if this constraint is to be ignored 273 */ 274 public boolean isToBeIgnored() { 275 return first().isToIgnoreStudentConflictsWith(second()); 276 } 277 278 @Override 279 public JenrlConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 280 return new JenrlConstraintContext(assignment); 281 } 282 283 public class JenrlConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 284 private boolean iAdded = false; 285 private Double iJenrlLimit = null; 286 private double iTwiggle = 0.0; 287 288 public JenrlConstraintContext(Assignment<Lecture, Placement> assignment) { 289 Placement p1 = assignment.getValue(first()); 290 Placement p2 = assignment.getValue(second()); 291 if (p1 != null && p2 != null && isInConflict(p1, p2, getDistanceMetric(), getWorkDayLimit())) { 292 iAdded = true; 293 first().addActiveJenrl(assignment, JenrlConstraint.this); 294 second().addActiveJenrl(assignment, JenrlConstraint.this); 295 } 296 if (iJenrlMaxConflicts >= 0.0 && iJenrlMaxConflicts < 1.0) 297 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * iJenrlMaxConflicts; 298 } 299 300 @Override 301 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 302 Lecture other = another(value.variable()); 303 if (other == null) return; 304 Placement otherValue = assignment.getValue(other); 305 if (!iAdded && otherValue != null && isInConflict(value, otherValue, getDistanceMetric(), getWorkDayLimit())) { 306 iAdded = true; 307 first().addActiveJenrl(assignment, JenrlConstraint.this); 308 second().addActiveJenrl(assignment, JenrlConstraint.this); 309 } 310 } 311 312 @Override 313 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 314 if (iAdded) { 315 iAdded = false; 316 first().removeActiveJenrl(assignment, JenrlConstraint.this); 317 second().removeActiveJenrl(assignment, JenrlConstraint.this); 318 } 319 } 320 321 public boolean isConflicting() { 322 return iAdded; 323 } 324 325 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 326 if (inConflict(assignment, value)) { 327 double maxConflicts = iJenrlMaxConflicts + iTwiggle; 328 iTwiggle = (iJenrl + 0.00001) / Math.min(first().maxClassLimit(), second().maxClassLimit()) - maxConflicts; 329 if (maxConflicts + iTwiggle >= 0.0 && maxConflicts + iTwiggle < 1.0) { 330 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * (maxConflicts + iTwiggle); 331 } else { 332 iJenrlLimit = null; 333 } 334 } 335 } 336 337 public void weaken() { 338 iTwiggle += iJenrlMaxConflictsWeaken; 339 double maxConflicts = iJenrlMaxConflicts + iTwiggle; 340 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 341 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts; 342 } else { 343 iJenrlLimit = null; 344 } 345 } 346 347 public boolean isOverLimit() { 348 return iJenrlLimit != null && iJenrl > iJenrlLimit; 349 } 350 351 public void incLimit(double weight) { 352 if (iJenrlLimit != null) iJenrlLimit += weight; 353 } 354 355 public void decLimit(double weight) { 356 double maxConflicts = iJenrlMaxConflicts + iTwiggle; 357 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 358 iJenrlLimit = Math.max(Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts, iJenrlLimit - weight); 359 } else { 360 iJenrlLimit = null; 361 } 362 } 363 } 364}