001package net.sf.cpsolver.coursett.constraint; 002 003import java.util.HashSet; 004import java.util.Set; 005 006import net.sf.cpsolver.coursett.criteria.StudentConflict; 007import net.sf.cpsolver.coursett.model.Lecture; 008import net.sf.cpsolver.coursett.model.Placement; 009import net.sf.cpsolver.coursett.model.Student; 010import net.sf.cpsolver.coursett.model.TimetableModel; 011import net.sf.cpsolver.ifs.criteria.Criterion; 012import net.sf.cpsolver.ifs.model.BinaryConstraint; 013import net.sf.cpsolver.ifs.model.WeakeningConstraint; 014import net.sf.cpsolver.ifs.util.DistanceMetric; 015import net.sf.cpsolver.ifs.util.ToolBox; 016 017/** 018 * Join student enrollment constraint. <br> 019 * This constraint is placed between all pairs of classes where there is at 020 * least one student attending both classes. It represents a number of student 021 * conflicts (number of joined enrollments), if the given two classes overlap in 022 * time. <br> 023 * Also, it dynamically maintains the counter of all student conflicts. It is a 024 * soft constraint. 025 * 026 * 027 * @version CourseTT 1.2 (University Course Timetabling)<br> 028 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * 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. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see 044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 045 */ 046 047public class JenrlConstraint extends BinaryConstraint<Lecture, Placement> implements WeakeningConstraint<Lecture, Placement> { 048 private double iJenrl = 0.0; 049 private double iPriority = 0.0; 050 private Set<Student> iStudents = new HashSet<Student>(); 051 private Set<Student> iInstructors = new HashSet<Student>(); 052 private boolean iAdded = false; 053 private Double iJenrlLimit = null; 054 private double iTwiggle = 0.0; 055 056 /** 057 * Constructor 058 */ 059 public JenrlConstraint() { 060 super(); 061 } 062 063 @Override 064 public void addVariable(Lecture variable) { 065 super.addVariable(variable); 066 if (second() != null && variable.getModel() != null && variable.getModel() instanceof TimetableModel) { 067 double maxConflicts = ((TimetableModel)variable.getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0); 068 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 069 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts; 070 } 071 } 072 } 073 074 @Override 075 public void computeConflicts(Placement value, Set<Placement> conflicts) { 076 if (inConflict(value)) 077 conflicts.add(another(value.variable()).getAssignment()); 078 } 079 080 @Override 081 public boolean inConflict(Placement value) { 082 if (!isOverLimit()) return false; 083 Lecture other = another(value.variable()); 084 return other != null && other.getAssignment() != null && !other.isCommitted() && isInConflict(value, other.getAssignment(), getDistanceMetric()); 085 } 086 087 @Override 088 public boolean isConsistent(Placement value1, Placement value2) { 089 return !isOverLimit() || !isInConflict(value1, value2, getDistanceMetric()); 090 } 091 092 @Override 093 public void unassigned(long iteration, Placement value) { 094 super.unassigned(iteration, value); 095 if (iAdded) { 096 iAdded = false; 097 (first()).removeActiveJenrl(this); 098 (second()).removeActiveJenrl(this); 099 } 100 } 101 102 /** 103 * Returns true if the given placements are overlapping or they are 104 * back-to-back and too far for students. 105 */ 106 public static boolean isInConflict(Placement p1, Placement p2, DistanceMetric m) { 107 return !StudentConflict.ignore(p1, p2) && (StudentConflict.distance(m, p1, p2) || StudentConflict.overlaps(p1, p2)); 108 } 109 110 @Override 111 public void assigned(long iteration, Placement value) { 112 super.assigned(iteration, value); 113 if (second() == null || first().getAssignment() == null || second().getAssignment() == null) 114 return; 115 if (isInConflict(first().getAssignment(), second().getAssignment(), getDistanceMetric())) { 116 iAdded = true; 117 (first()).addActiveJenrl(this); 118 (second()).addActiveJenrl(this); 119 } 120 } 121 122 /** 123 * Number of joined enrollments if the given value is assigned to the given 124 * variable 125 */ 126 public long jenrl(Lecture variable, Placement value) { 127 Lecture anotherLecture = (first().equals(variable) ? second() : first()); 128 if (anotherLecture.getAssignment() == null) 129 return 0; 130 return (isInConflict(anotherLecture.getAssignment(), value, getDistanceMetric()) ? Math.round(iJenrl) : 0); 131 } 132 133 private DistanceMetric getDistanceMetric() { 134 return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric()); 135 } 136 137 /** True if the given two lectures overlap in time */ 138 public boolean isInConflict() { 139 return iAdded; 140 } 141 142 /** 143 * Increment the number of joined enrollments (during student final 144 * sectioning) 145 */ 146 public void incJenrl(Student student) { 147 boolean hard = 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(this, jenrlWeight, conflictPriority, student); 159 if (!hard && isOverLimit() && isInConflict()) { 160 iJenrlLimit += 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 */ 172 public void decJenrl(Student student) { 173 boolean hard = isOverLimit(); 174 double jenrlWeight = student.getJenrlWeight(first(), second()); 175 iJenrl -= jenrlWeight; 176 Double conflictPriority = student.getConflictingPriorty(first(), second()); 177 if (conflictPriority != null) iPriority -= conflictPriority * jenrlWeight; 178 iStudents.remove(student); 179 iInstructors.remove(student); 180 for (Criterion<Lecture, Placement> criterion: getModel().getCriteria()) 181 if (criterion instanceof StudentConflict) 182 ((StudentConflict)criterion).incJenrl(this, -jenrlWeight, conflictPriority, student); 183 if (hard && !isOverLimit()) { 184 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle; 185 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 186 iJenrlLimit = Math.max(Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts, iJenrlLimit - jenrlWeight); 187 } else { 188 iJenrlLimit = null; 189 } 190 } 191 } 192 193 /** Number of joined enrollments (during student final sectioning) */ 194 public long getJenrl() { 195 return Math.round(iJenrl); 196 } 197 198 public double jenrl() { 199 return iJenrl; 200 } 201 202 public double priority() { 203 return iPriority; 204 } 205 206 public int getNrStudents() { 207 return iStudents.size(); 208 } 209 210 public Set<Student> getStudents() { 211 return iStudents; 212 } 213 214 public int getNrInstructors() { 215 return iInstructors.size(); 216 } 217 218 public Set<Student> getInstructors() { 219 return iInstructors; 220 } 221 222 @Override 223 public boolean isHard() { 224 return true; 225 } 226 227 public boolean isOverLimit() { 228 return iJenrlLimit != null && iJenrl > iJenrlLimit; 229 } 230 231 @Override 232 public String getName() { 233 return "Join Enrollment"; 234 } 235 236 @Override 237 public String toString() { 238 return "Join Enrollment between " + first().getName() + " and " + second().getName(); 239 } 240 241 public boolean areStudentConflictsHard() { 242 return StudentConflict.hard(first(), second()); 243 } 244 245 public boolean areStudentConflictsDistance() { 246 return StudentConflict.distance(getDistanceMetric(), first().getAssignment(), second().getAssignment()); 247 } 248 249 public boolean areStudentConflictsCommitted() { 250 return StudentConflict.committed(first(), second()); 251 } 252 253 public boolean areStudentConflictsDistance(Placement value) { 254 return StudentConflict.distance(getDistanceMetric(), value, another(value.variable()).getAssignment()); 255 } 256 257 public boolean isOfTheSameProblem() { 258 return ToolBox.equals(first().getSolverGroupId(), second().getSolverGroupId()); 259 } 260 261 @Override 262 public void weaken() { 263 if (second() == null) return; 264 iTwiggle += ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflictsWeaken", 0.001); 265 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle; 266 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 267 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts; 268 } else { 269 iJenrlLimit = null; 270 } 271 } 272 273 @Override 274 public void weaken(Placement value) { 275 if (second() != null && inConflict(value)) { 276 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle; 277 iTwiggle = (iJenrl + 0.00001) / Math.min(first().maxClassLimit(), second().maxClassLimit()) - maxConflicts; 278 if (maxConflicts + iTwiggle >= 0.0 && maxConflicts + iTwiggle < 1.0) { 279 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * (maxConflicts + iTwiggle); 280 } else { 281 iJenrlLimit = null; 282 } 283 } 284 } 285 286 /** 287 * Returns true if there is {@link IgnoreStudentConflictsConstraint} between the two lectures. 288 */ 289 public boolean isToBeIgnored() { 290 return first().isToIgnoreStudentConflictsWith(second()); 291 } 292}