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 boolean iAdded = false; 051 private Double iJenrlLimit = null; 052 private double iTwiggle = 0.0; 053 054 /** 055 * Constructor 056 */ 057 public JenrlConstraint() { 058 super(); 059 } 060 061 @Override 062 public void addVariable(Lecture variable) { 063 super.addVariable(variable); 064 if (second() != null && variable.getModel() != null && variable.getModel() instanceof TimetableModel) { 065 double maxConflicts = ((TimetableModel)variable.getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0); 066 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 067 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts; 068 } 069 } 070 } 071 072 @Override 073 public void computeConflicts(Placement value, Set<Placement> conflicts) { 074 if (inConflict(value)) 075 conflicts.add(another(value.variable()).getAssignment()); 076 } 077 078 @Override 079 public boolean inConflict(Placement value) { 080 if (!isOverLimit()) return false; 081 Lecture other = another(value.variable()); 082 return other != null && other.getAssignment() != null && !other.isCommitted() && isInConflict(value, other.getAssignment(), getDistanceMetric()); 083 } 084 085 @Override 086 public boolean isConsistent(Placement value1, Placement value2) { 087 return !isOverLimit() || !isInConflict(value1, value2, getDistanceMetric()); 088 } 089 090 @Override 091 public void unassigned(long iteration, Placement value) { 092 super.unassigned(iteration, value); 093 if (iAdded) { 094 iAdded = false; 095 (first()).removeActiveJenrl(this); 096 (second()).removeActiveJenrl(this); 097 } 098 } 099 100 /** 101 * Returns true if the given placements are overlapping or they are 102 * back-to-back and too far for students. 103 */ 104 public static boolean isInConflict(Placement p1, Placement p2, DistanceMetric m) { 105 return StudentConflict.distance(m, p1, p2) || StudentConflict.overlaps(p1, p2); 106 } 107 108 @Override 109 public void assigned(long iteration, Placement value) { 110 super.assigned(iteration, value); 111 if (second() == null || first().getAssignment() == null || second().getAssignment() == null) 112 return; 113 if (isInConflict(first().getAssignment(), second().getAssignment(), getDistanceMetric())) { 114 iAdded = true; 115 (first()).addActiveJenrl(this); 116 (second()).addActiveJenrl(this); 117 } 118 } 119 120 /** 121 * Number of joined enrollments if the given value is assigned to the given 122 * variable 123 */ 124 public long jenrl(Lecture variable, Placement value) { 125 Lecture anotherLecture = (first().equals(variable) ? second() : first()); 126 if (anotherLecture.getAssignment() == null) 127 return 0; 128 return (isInConflict(anotherLecture.getAssignment(), value, getDistanceMetric()) ? Math.round(iJenrl) : 0); 129 } 130 131 private DistanceMetric getDistanceMetric() { 132 return ((TimetableModel)getModel()).getDistanceMetric(); 133 } 134 135 /** True if the given two lectures overlap in time */ 136 public boolean isInConflict() { 137 return iAdded; 138 } 139 140 /** 141 * Increment the number of joined enrollments (during student final 142 * sectioning) 143 */ 144 public void incJenrl(Student student) { 145 boolean hard = isOverLimit(); 146 double jenrlWeight = student.getJenrlWeight(first(), second()); 147 iJenrl += jenrlWeight; 148 Double conflictPriority = student.getConflictingPriorty(first(), second()); 149 if (conflictPriority != null) iPriority += conflictPriority * jenrlWeight; 150 iStudents.add(student); 151 for (Criterion<Lecture, Placement> criterion: getModel().getCriteria()) 152 if (criterion instanceof StudentConflict) 153 ((StudentConflict)criterion).incJenrl(this, jenrlWeight, conflictPriority); 154 if (!hard && isOverLimit() && first() != null && first().getAssignment() != null && second() != null && second().getAssignment() != null) 155 iJenrlLimit += jenrlWeight; 156 } 157 158 public double getJenrlWeight(Student student) { 159 return student.getJenrlWeight(first(), second()); 160 } 161 162 /** 163 * Decrement the number of joined enrollments (during student final 164 * sectioning) 165 */ 166 public void decJenrl(Student student) { 167 boolean hard = isOverLimit(); 168 double jenrlWeight = student.getJenrlWeight(first(), second()); 169 iJenrl -= jenrlWeight; 170 Double conflictPriority = student.getConflictingPriorty(first(), second()); 171 if (conflictPriority != null) iPriority -= conflictPriority * jenrlWeight; 172 iStudents.remove(student); 173 for (Criterion<Lecture, Placement> criterion: getModel().getCriteria()) 174 if (criterion instanceof StudentConflict) 175 ((StudentConflict)criterion).incJenrl(this, -jenrlWeight, conflictPriority); 176 if (hard && !isOverLimit()) { 177 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle; 178 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 179 iJenrlLimit = Math.max(Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts, iJenrlLimit - jenrlWeight); 180 } else { 181 iJenrlLimit = null; 182 } 183 } 184 } 185 186 /** Number of joined enrollments (during student final sectioning) */ 187 public long getJenrl() { 188 return Math.round(iJenrl); 189 } 190 191 public double jenrl() { 192 return iJenrl; 193 } 194 195 public double priority() { 196 return iPriority; 197 } 198 199 public int getNrStudents() { 200 return iStudents.size(); 201 } 202 203 public Set<Student> getStudents() { 204 return iStudents; 205 } 206 207 @Override 208 public boolean isHard() { 209 return true; 210 } 211 212 public boolean isOverLimit() { 213 return iJenrlLimit != null && iJenrl > iJenrlLimit; 214 } 215 216 @Override 217 public String getName() { 218 return "Join Enrollment"; 219 } 220 221 @Override 222 public String toString() { 223 return "Join Enrollment between " + first().getName() + " and " + second().getName(); 224 } 225 226 public boolean areStudentConflictsHard() { 227 return StudentConflict.hard(first(), second()); 228 } 229 230 public boolean areStudentConflictsDistance() { 231 return StudentConflict.distance(getDistanceMetric(), first().getAssignment(), second().getAssignment()); 232 } 233 234 public boolean areStudentConflictsCommitted() { 235 return StudentConflict.committed(first(), second()); 236 } 237 238 public boolean areStudentConflictsDistance(Placement value) { 239 return StudentConflict.distance(getDistanceMetric(), value, another(value.variable()).getAssignment()); 240 } 241 242 public boolean isOfTheSameProblem() { 243 return ToolBox.equals(first().getSolverGroupId(), second().getSolverGroupId()); 244 } 245 246 @Override 247 public void weaken() { 248 iTwiggle += ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflictsWeaken", 0.001); 249 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle; 250 if (maxConflicts >= 0.0 && maxConflicts < 1.0) { 251 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts; 252 } else { 253 iJenrlLimit = null; 254 } 255 } 256 257 @Override 258 public void weaken(Placement value) { 259 if (inConflict(value)) { 260 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle; 261 iTwiggle = (iJenrl + 0.00001) / Math.min(first().maxClassLimit(), second().maxClassLimit()) - maxConflicts; 262 if (maxConflicts + iTwiggle >= 0.0 && maxConflicts + iTwiggle < 1.0) { 263 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * (maxConflicts + iTwiggle); 264 } else { 265 iJenrlLimit = null; 266 } 267 } 268 } 269 270 }