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.model.WeakeningConstraint;
014 import net.sf.cpsolver.ifs.util.DistanceMetric;
015 import 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 Tomas Muller<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
047 public 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 iTwiggle += ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflictsWeaken", 0.001);
264 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle;
265 if (maxConflicts >= 0.0 && maxConflicts < 1.0) {
266 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts;
267 } else {
268 iJenrlLimit = null;
269 }
270 }
271
272 @Override
273 public void weaken(Placement value) {
274 if (inConflict(value)) {
275 double maxConflicts = ((TimetableModel)second().getModel()).getProperties().getPropertyDouble("General.JenrlMaxConflicts", 1.0) + iTwiggle;
276 iTwiggle = (iJenrl + 0.00001) / Math.min(first().maxClassLimit(), second().maxClassLimit()) - maxConflicts;
277 if (maxConflicts + iTwiggle >= 0.0 && maxConflicts + iTwiggle < 1.0) {
278 iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * (maxConflicts + iTwiggle);
279 } else {
280 iJenrlLimit = null;
281 }
282 }
283 }
284
285 /**
286 * Returns true if there is {@link IgnoreStudentConflictsConstraint} between the two lectures.
287 */
288 public boolean isToBeIgnored() {
289 return first().isToIgnoreStudentConflictsWith(second());
290 }
291 }