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 Tomas Muller<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())) 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()); 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 * @return true if there is a student conflict between the two placements 103 */ 104 public static boolean isInConflict(Placement p1, Placement p2, DistanceMetric m) { 105 return p1 != null && p2 != null && !StudentConflict.ignore(p1.variable(), p2.variable()) && (StudentConflict.distance(m, p1, p2) || StudentConflict.overlaps(p1, p2)); 106 } 107 108 /** 109 * Number of joined enrollments if the given value is assigned to the given 110 * variable 111 * @param assignment current assignment 112 * @param variable a class 113 * @param value class placement under consideration 114 * @return number of student conflicts caused by this constraint if assigned 115 */ 116 public long jenrl(Assignment<Lecture, Placement> assignment, Lecture variable, Placement value) { 117 Lecture other = (first().equals(variable) ? second() : first()); 118 Placement otherPlacement = (other == null ? null : assignment.getValue(other)); 119 return (otherPlacement != null && isInConflict(value, otherPlacement, getDistanceMetric()) ? Math.round(iJenrl) : 0); 120 } 121 122 private DistanceMetric getDistanceMetric() { 123 return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric()); 124 } 125 126 /** True if the given two lectures overlap in time 127 * @param assignment current assignment 128 * @return true if this constraint is conflicting 129 **/ 130 public boolean isInConflict(Assignment<Lecture, Placement> assignment) { 131 return getContext(assignment).isConflicting(); 132 } 133 134 /** 135 * Increment the number of joined enrollments (during student final 136 * sectioning) 137 * @param assignment current assignment 138 * @param student student added in between the two classes of this constraint 139 */ 140 public void incJenrl(Assignment<Lecture, Placement> assignment, Student student) { 141 JenrlConstraintContext context = getContext(assignment); 142 boolean hard = context.isOverLimit(); 143 double jenrlWeight = student.getJenrlWeight(first(), second()); 144 iJenrl += jenrlWeight; 145 Double conflictPriority = student.getConflictingPriorty(first(), second()); 146 if (conflictPriority != null) iPriority += conflictPriority * jenrlWeight; 147 iStudents.add(student); 148 if (student.getInstructor() != null && (student.getInstructor().variables().contains(first()) || 149 student.getInstructor().variables().contains(second()))) 150 iInstructors.add(student); 151 for (Criterion<Lecture, Placement> criterion: getModel().getCriteria()) 152 if (criterion instanceof StudentConflict) 153 ((StudentConflict)criterion).incJenrl(assignment, this, jenrlWeight, conflictPriority, student); 154 if (!hard && context.isOverLimit() && isInConflict(assignment)) { 155 context.incLimit(jenrlWeight); 156 } 157 } 158 159 public double getJenrlWeight(Student student) { 160 return student.getJenrlWeight(first(), second()); 161 } 162 163 /** 164 * Decrement the number of joined enrollments (during student final 165 * sectioning) 166 * @param assignment current assignment 167 * @param student student removed from between the two classes of this constraint 168 */ 169 public void decJenrl(Assignment<Lecture, Placement> assignment, Student student) { 170 JenrlConstraintContext context = getContext(assignment); 171 boolean hard = context.isOverLimit(); 172 double jenrlWeight = student.getJenrlWeight(first(), second()); 173 iJenrl -= jenrlWeight; 174 Double conflictPriority = student.getConflictingPriorty(first(), second()); 175 if (conflictPriority != null) iPriority -= conflictPriority * jenrlWeight; 176 iStudents.remove(student); 177 iInstructors.remove(student); 178 for (Criterion<Lecture, Placement> criterion: getModel().getCriteria()) 179 if (criterion instanceof StudentConflict) 180 ((StudentConflict)criterion).incJenrl(assignment, this, -jenrlWeight, conflictPriority, student); 181 if (hard && !context.isOverLimit()) 182 context.decLimit(jenrlWeight); 183 } 184 185 /** Number of joined enrollments (during student final sectioning) 186 * @return number of joined enrollments 187 **/ 188 public long getJenrl() { 189 return Math.round(iJenrl); 190 } 191 192 public double jenrl() { 193 return iJenrl; 194 } 195 196 public double priority() { 197 return iPriority; 198 } 199 200 public int getNrStudents() { 201 return iStudents.size(); 202 } 203 204 public Set<Student> getStudents() { 205 return iStudents; 206 } 207 208 public int getNrInstructors() { 209 return iInstructors.size(); 210 } 211 212 public Set<Student> getInstructors() { 213 return iInstructors; 214 } 215 216 @Override 217 public boolean isHard() { 218 return true; 219 } 220 221 @Override 222 public String getName() { 223 return "Join Enrollment"; 224 } 225 226 @Override 227 public String toString() { 228 return "Join Enrollment between " + first().getName() + " and " + second().getName(); 229 } 230 231 public boolean areStudentConflictsHard() { 232 return StudentConflict.hard(first(), second()); 233 } 234 235 public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment) { 236 return StudentConflict.distance(getDistanceMetric(), assignment.getValue(first()), assignment.getValue(second())); 237 } 238 239 public boolean areStudentConflictsCommitted() { 240 return StudentConflict.committed(first(), second()); 241 } 242 243 public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment, Placement value) { 244 return StudentConflict.distance(getDistanceMetric(), value, assignment.getValue(another(value.variable()))); 245 } 246 247 public boolean isOfTheSameProblem() { 248 return ToolBox.equals(first().getSolverGroupId(), second().getSolverGroupId()); 249 } 250 251 @Override 252 public void weaken(Assignment<Lecture, Placement> assignment) { 253 getContext(assignment).weaken(); 254 } 255 256 @Override 257 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 258 getContext(assignment).weaken(assignment, value); 259 } 260 261 /** 262 * Returns true if there is {@link IgnoreStudentConflictsConstraint} between the two lectures. 263 * @return true if this constraint is to be ignored 264 */ 265 public boolean isToBeIgnored() { 266 return first().isToIgnoreStudentConflictsWith(second()); 267 } 268 269 @Override 270 public JenrlConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 271 return new JenrlConstraintContext(assignment); 272 } 273 274 public class JenrlConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 275 private boolean iAdded = false; 276 private Double iJenrlLimit = null; 277 private double iTwiggle = 0.0; 278 279 public JenrlConstraintContext(Assignment<Lecture, Placement> assignment) { 280 Placement p1 = assignment.getValue(first()); 281 Placement p2 = assignment.getValue(second()); 282 if (p1 != null && p2 != null && isInConflict(p1, p2, getDistanceMetric())) { 283 iAdded = true; 284 first().addActiveJenrl(assignment, JenrlConstraint.this); 285 second().addActiveJenrl(assignment, JenrlConstraint.this); 286 } 287 if (iJenrlMaxConflicts >= 0.0 && iJenrlMaxConflicts < 1.0) 288 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * iJenrlMaxConflicts; 289 } 290 291 @Override 292 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 293 Lecture other = another(value.variable()); 294 if (other == null) return; 295 Placement otherValue = assignment.getValue(other); 296 if (!iAdded && otherValue != null && isInConflict(value, otherValue, getDistanceMetric())) { 297 iAdded = true; 298 first().addActiveJenrl(assignment, JenrlConstraint.this); 299 second().addActiveJenrl(assignment, JenrlConstraint.this); 300 } 301 } 302 303 @Override 304 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 305 if (iAdded) { 306 iAdded = false; 307 first().removeActiveJenrl(assignment, JenrlConstraint.this); 308 second().removeActiveJenrl(assignment, JenrlConstraint.this); 309 } 310 } 311 312 public boolean isConflicting() { 313 return iAdded; 314 } 315 316 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 317 if (inConflict(assignment, value)) { 318 double maxConflicts = iJenrlMaxConflicts + iTwiggle; 319 iTwiggle = (iJenrl + 0.00001) / Math.min(first().maxClassLimit(), second().maxClassLimit()) - maxConflicts; 320 if (maxConflicts + iTwiggle >= 0.0 && maxConflicts + iTwiggle < 1.0) { 321 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * (maxConflicts + iTwiggle); 322 } else { 323 iJenrlLimit = null; 324 } 325 } 326 } 327 328 public void weaken() { 329 iTwiggle += iJenrlMaxConflictsWeaken; 330 double maxConflicts = iJenrlMaxConflicts + iTwiggle; 331 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 332 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts; 333 } else { 334 iJenrlLimit = null; 335 } 336 } 337 338 public boolean isOverLimit() { 339 return iJenrlLimit != null && iJenrl > iJenrlLimit; 340 } 341 342 public void incLimit(double weight) { 343 if (iJenrlLimit != null) iJenrlLimit += weight; 344 } 345 346 public void decLimit(double weight) { 347 double maxConflicts = iJenrlMaxConflicts + iTwiggle; 348 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 349 iJenrlLimit = Math.max(Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts, iJenrlLimit - weight); 350 } else { 351 iJenrlLimit = null; 352 } 353 } 354 } 355}