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