001 package net.sf.cpsolver.coursett.criteria;
002
003 import java.util.Collection;
004 import java.util.HashSet;
005 import java.util.Set;
006
007 import net.sf.cpsolver.coursett.Constants;
008 import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
009 import net.sf.cpsolver.coursett.model.Lecture;
010 import net.sf.cpsolver.coursett.model.Placement;
011 import net.sf.cpsolver.coursett.model.Student;
012 import net.sf.cpsolver.coursett.model.TimeLocation;
013 import net.sf.cpsolver.coursett.model.TimetableModel;
014 import net.sf.cpsolver.ifs.solver.Solver;
015 import net.sf.cpsolver.ifs.util.DistanceMetric;
016
017 /**
018 * Student conflicts. This criterion counts student conflicts between classes. A conflict
019 * occurs when two classes that are attended by the same student (or students) are overlapping
020 * in time or place back-to-back in rooms that are too far a part. The combinations of classes
021 * that share students are maintained by {@link JenrlConstraint}.
022 * <br>
023 *
024 * @version CourseTT 1.2 (University Course Timetabling)<br>
025 * Copyright (C) 2006 - 2011 Tomas Muller<br>
026 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
028 * <br>
029 * This library is free software; you can redistribute it and/or modify
030 * it under the terms of the GNU Lesser General Public License as
031 * published by the Free Software Foundation; either version 3 of the
032 * License, or (at your option) any later version. <br>
033 * <br>
034 * This library is distributed in the hope that it will be useful, but
035 * WITHOUT ANY WARRANTY; without even the implied warranty of
036 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 * Lesser General Public License for more details. <br>
038 * <br>
039 * You should have received a copy of the GNU Lesser General Public
040 * License along with this library; if not see
041 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042 */
043 public class StudentConflict extends TimetablingCriterion {
044 protected boolean iIncludeConflicts = false;
045
046 public StudentConflict() {
047 iValueUpdateType = ValueUpdateType.BeforeUnassignedBeforeAssigned;
048 }
049
050 @Override
051 public boolean init(Solver<Lecture, Placement> solver) {
052 iIncludeConflicts = solver.getProperties().getPropertyBoolean("StudentConflict.IncludeConflicts", false);
053 return super.init(solver);
054 }
055
056 @Override
057 public String getPlacementSelectionWeightName() {
058 return null;
059 }
060
061 @Override
062 public double getValue() {
063 return super.getValue();
064 }
065
066 public DistanceMetric getMetrics() {
067 return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric());
068 }
069
070 public static boolean overlaps(Placement p1, Placement p2) {
071 return p1 != null && p2 != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()) && (!p1.variable().isCommitted() || !p2.variable().isCommitted());
072 }
073
074 protected double jointEnrollment(JenrlConstraint jenrl) {
075 return jenrl.jenrl();
076 }
077
078 public static boolean distance(DistanceMetric m, Placement p1, Placement p2) {
079 if (m == null && p1 != null) m = ((TimetableModel)p1.variable().getModel()).getDistanceMetric();
080 if (m == null && p2 != null) m = ((TimetableModel)p2.variable().getModel()).getDistanceMetric();
081 if (p1 == null || p2 == null || m == null) return false;
082 if (p1.variable().isCommitted() && p2.variable().isCommitted()) return false;
083 TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
084 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
085 if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) {
086 if (t1.getStartSlot() + t1.getLength() <= t2.getStartSlot()) {
087 return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength());
088 } else if (t2.getStartSlot() + t2.getLength() <= t1.getStartSlot()) {
089 return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength());
090 }
091 } else {
092 if (t1.getStartSlot() + t1.getLength() == t2.getStartSlot()) {
093 return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime();
094 } else if (t2.getStartSlot() + t2.getLength() == t1.getStartSlot()) {
095 return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime();
096 }
097 }
098 return false;
099 }
100
101 public static boolean ignore(Placement p1, Placement p2) {
102 return p1 != null && p2 != null && p1.variable().isToIgnoreStudentConflictsWith(p2.variable());
103 }
104
105 public static boolean ignore(Lecture l1, Lecture l2) {
106 return l1 != null && l2 != null && l1.isToIgnoreStudentConflictsWith(l2);
107 }
108
109 public static boolean committed(Placement p1, Placement p2) {
110 return p1 != null && p2 != null && committed(p1.variable(), p2.variable());
111 }
112
113 public static boolean committed(Lecture l1, Lecture l2) {
114 return l1 != null && l2 != null && (l1.isCommitted() || l2.isCommitted()) && (!l1.isCommitted() || !l2.isCommitted());
115 }
116
117 public static boolean applicable(Placement p1, Placement p2) {
118 return p1 != null && p2 != null && applicable(p1.variable(), p2.variable());
119 }
120
121 public static boolean applicable(Lecture l1, Lecture l2) {
122 return l1 != null && l2 != null && (!l1.isCommitted() || !l2.isCommitted());
123 }
124
125 public static boolean hard(Placement p1, Placement p2) {
126 return p1 != null && p2 != null && hard(p1.variable(), p2.variable());
127 }
128
129 public static boolean hard(Lecture l1, Lecture l2) {
130 return l1 != null && l2 != null && l1.isSingleSection() && l2.isSingleSection() && (!l1.isCommitted() || !l2.isCommitted());
131 }
132
133 public boolean isApplicable(Lecture l1, Lecture l2) {
134 return !ignore(l1, l2) && applicable(l1, l2) && !committed(l1, l2); // exclude committed and outside student conflicts
135 }
136
137 public boolean inConflict(Placement p1, Placement p2) {
138 return !ignore(p1, p2) && (overlaps(p1, p2) || distance(getMetrics(), p1, p2)) && isApplicable(p1.variable(), p2.variable());
139 }
140
141 @Override
142 public double getValue(Placement value, Set<Placement> conflicts) {
143 double ret = 0.0;
144 for (JenrlConstraint jenrl: value.variable().jenrlConstraints()) {
145 Placement another = jenrl.another(value.variable()).getAssignment();
146 if (another == null) continue;
147 if (conflicts != null && conflicts.contains(another)) continue;
148 if (inConflict(value, another))
149 ret += jointEnrollment(jenrl);
150 }
151 if (iIncludeConflicts && conflicts != null)
152 for (Placement conflict: conflicts) {
153 for (JenrlConstraint jenrl: conflict.variable().jenrlConstraints()) {
154 Placement another = jenrl.another(conflict.variable()).getAssignment();
155 if (another == null || another.variable().equals(value.variable())) continue;
156 if (conflicts != null && conflicts.contains(another)) continue;
157 if (inConflict(conflict, another))
158 ret -= jointEnrollment(jenrl);
159 }
160 }
161 return ret;
162 }
163
164 @Override
165 public double getValue(Collection<Lecture> variables) {
166 double ret = 0.0;
167 Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
168 for (Lecture lect: variables) {
169 if (lect.getAssignment() == null) continue;
170 for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
171 if (!constraints.add(jenrl)) continue;
172 if (!jenrl.another(lect).isCommitted() && !variables.contains(jenrl.another(lect))) continue;
173 if (inConflict(lect.getAssignment(), jenrl.another(lect).getAssignment()))
174 ret += jointEnrollment(jenrl);
175 }
176 }
177 return ret;
178 }
179
180 @Override
181 public double[] getBounds() {
182 double[] bounds = { 0.0, 0.0 };
183 for (JenrlConstraint jenrl: ((TimetableModel)getModel()).getJenrlConstraints())
184 if (isApplicable(jenrl.first(), jenrl.second()))
185 bounds[0] += jointEnrollment(jenrl);
186 return bounds;
187 }
188
189 @Override
190 public double[] getBounds(Collection<Lecture> variables) {
191 double[] bounds = { 0.0, 0.0 };
192 Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
193 for (Lecture lect: variables) {
194 if (lect.getAssignment() == null) continue;
195 for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
196 if (isApplicable(jenrl.first(), jenrl.second()) && constraints.add(jenrl) && (jenrl.another(lect).isCommitted() || variables.contains(jenrl.another(lect))))
197 bounds[0] += jointEnrollment(jenrl);
198 }
199 }
200 return bounds;
201 }
202
203 public void incJenrl(JenrlConstraint jenrl, double studentWeight, Double conflictPriority, Student student) {
204 if (inConflict(jenrl.first().getAssignment(), jenrl.second().getAssignment()))
205 iValue += studentWeight;
206 }
207
208 @Override
209 public void bestRestored() {
210 super.bestRestored();
211 iValue = getValue(getModel().variables());
212 }
213 }