001package org.cpsolver.studentsct.constraint; 002 003import java.util.Set; 004 005import org.cpsolver.coursett.Constants; 006import org.cpsolver.coursett.model.TimeLocation; 007import org.cpsolver.ifs.assignment.Assignment; 008import org.cpsolver.ifs.model.GlobalConstraint; 009import org.cpsolver.studentsct.StudentSectioningModel; 010import org.cpsolver.studentsct.extension.StudentQuality; 011import org.cpsolver.studentsct.model.Config; 012import org.cpsolver.studentsct.model.Enrollment; 013import org.cpsolver.studentsct.model.Request; 014import org.cpsolver.studentsct.model.SctAssignment; 015import org.cpsolver.studentsct.model.Section; 016import org.cpsolver.studentsct.model.Student; 017import org.cpsolver.studentsct.model.Unavailability; 018 019/** 020 * Hard distance conflicts constraint. This global constraint checks for distance conflicts 021 * that should not be allowed. These are distance conflicts where the distance betweem the 022 * two sections is longer than HardDistanceConflict.DistanceHardLimitInMinutes minutes (defaults to 60) 023 * and the distance to travel between the two sections is longer than 024 * HardDistanceConflict.AllowedDistanceInMinutes minutes (defaults to 30). 025 * The constraint checks both pairs of sections that the student is to be enrolled in 026 * and distance conflicts with unavailabilities. 027 * 028 * @author Tomáš Müller 029 * @version StudentSct 1.3 (Student Sectioning)<br> 030 * Copyright (C) 2007 - 2015 Tomáš Müller<br> 031 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 032 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 033 * <br> 034 * This library is free software; you can redistribute it and/or modify 035 * it under the terms of the GNU Lesser General Public License as 036 * published by the Free Software Foundation; either version 3 of the 037 * License, or (at your option) any later version. <br> 038 * <br> 039 * This library is distributed in the hope that it will be useful, but 040 * WITHOUT ANY WARRANTY; without even the implied warranty of 041 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 042 * Lesser General Public License for more details. <br> 043 * <br> 044 * You should have received a copy of the GNU Lesser General Public 045 * License along with this library; if not see 046 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 047 */ 048public class HardDistanceConflicts extends GlobalConstraint<Request, Enrollment> { 049 /** 050 * A given enrollment is conflicting, if there is a section that 051 * is disabled and there is not a matching reservation that would allow for that. 052 * 053 * @param enrollment {@link Enrollment} that is being considered 054 * @param conflicts all computed conflicting requests are added into this set 055 */ 056 @Override 057 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) { 058 if (enrollment.variable().getModel() == null || !(enrollment.variable().getModel() instanceof StudentSectioningModel)) return; 059 StudentSectioningModel model = (StudentSectioningModel)enrollment.variable().getModel(); 060 StudentQuality studentQuality = model.getStudentQuality(); 061 if (studentQuality == null) return; 062 StudentQuality.Context cx = studentQuality.getStudentQualityContext(); 063 064 // enrollment's student 065 Student student = enrollment.getStudent(); 066 // no unavailabilities > no distance conflicts 067 if (student.getUnavailabilities().isEmpty()) return; 068 069 // enrollment's config 070 Config config = enrollment.getConfig(); 071 072 // exclude free time requests 073 if (config == null) return; 074 075 // check for an unavailability distance conflict 076 if (cx.getUnavailabilityDistanceMetric().isHardDistanceConflictsEnabled()) { 077 for (Section s1: enrollment.getSections()) { 078 // no time or no room > no conflict 079 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 080 for (Unavailability s2: student.getUnavailabilities()) { 081 // no time or no room > no conflict 082 if (s2.getTime() == null || s2.getNrRooms() == 0) continue; 083 TimeLocation t1 = s1.getTime(); 084 TimeLocation t2 = s2.getTime(); 085 // no shared day > no conflict 086 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue; 087 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 088 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 089 int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2); 090 if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() 091 && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) { 092 conflicts.add(enrollment); 093 return; 094 } 095 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 096 int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2); 097 if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() 098 && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) { 099 conflicts.add(enrollment); 100 return; 101 } 102 } 103 } 104 } 105 } 106 107 // check for distance conflicts within the enrollment 108 if (cx.getDistanceMetric().isHardDistanceConflictsEnabled()) { 109 for (Section s1: enrollment.getSections()) { 110 // no time or no room > no conflict 111 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 112 for (Section s2: enrollment.getSections()) { 113 if (s1.getId() < s2.getId()) { 114 // no time or no room > no conflict 115 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 116 TimeLocation t1 = s1.getTime(); 117 TimeLocation t2 = s2.getTime(); 118 // no shared day > no conflict 119 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue; 120 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 121 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 122 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 123 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 124 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 125 && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 126 conflicts.add(enrollment); 127 return; 128 } 129 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 130 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 131 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 132 && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 133 conflicts.add(enrollment); 134 return; 135 } 136 } 137 } else { 138 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 139 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 140 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 141 && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 142 conflicts.add(enrollment); 143 return; 144 } 145 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 146 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 147 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 148 && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 149 conflicts.add(enrollment); 150 return; 151 } 152 } 153 } 154 } 155 } 156 } 157 158 // check conflicts with other enrollments of the student 159 other: for (Request other: student.getRequests()) { 160 if (other.equals(enrollment.variable())) continue; 161 Enrollment e2 = other.getAssignment(assignment); 162 if (e2 == null || conflicts.contains(e2)) continue; 163 for (Section s1: enrollment.getSections()) { 164 // no time or no room > no conflict 165 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 166 for (Section s2: e2.getSections()) { 167 // no time or no room > no conflict 168 if (!s2.hasTime() || s2.getNrRooms() == 0) continue; 169 TimeLocation t1 = s1.getTime(); 170 TimeLocation t2 = s2.getTime(); 171 // no shared day > no conflict 172 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue; 173 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 174 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 175 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 176 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 177 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 178 && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 179 conflicts.add(e2); 180 continue other; 181 } 182 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 183 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 184 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 185 && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 186 conflicts.add(e2); 187 continue other; 188 } 189 } 190 } else { 191 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 192 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 193 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 194 && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 195 conflicts.add(e2); 196 continue other; 197 } 198 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 199 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 200 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 201 && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) { 202 conflicts.add(e2); 203 continue other; 204 } 205 } 206 } 207 } 208 } 209 } 210 } 211 } 212 213 /** 214 * A given enrollment is conflicting, if there is a section that 215 * is disabled and there is not a matching reservation that would allow for that. 216 * 217 * @param enrollment {@link Enrollment} that is being considered 218 * @return true, if the enrollment does not follow a reservation that must be used 219 */ 220 @Override 221 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 222 if (enrollment.variable().getModel() == null || !(enrollment.variable().getModel() instanceof StudentSectioningModel)) return false; 223 StudentSectioningModel model = (StudentSectioningModel)enrollment.variable().getModel(); 224 StudentQuality studentQuality = model.getStudentQuality(); 225 if (studentQuality == null) return false; 226 StudentQuality.Context cx = studentQuality.getStudentQualityContext(); 227 228 // enrollment's student 229 Student student = enrollment.getStudent(); 230 // no unavailabilities > no distance conflicts 231 if (student.getUnavailabilities().isEmpty()) return false; 232 233 // enrollment's config 234 Config config = enrollment.getConfig(); 235 236 // exclude free time requests 237 if (config == null) return false; 238 239 // check for an unavailability distance conflict 240 if (cx.getUnavailabilityDistanceMetric().isHardDistanceConflictsEnabled()) { 241 for (Section s1: enrollment.getSections()) { 242 // no time or no room > no conflict 243 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 244 for (Unavailability s2: student.getUnavailabilities()) { 245 // no time or no room > no conflict 246 if (s2.getTime() == null || s2.getNrRooms() == 0) continue; 247 TimeLocation t1 = s1.getTime(); 248 TimeLocation t2 = s2.getTime(); 249 // no shared day > no conflict 250 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue; 251 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 252 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 253 int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2); 254 if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() 255 && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) 256 return true; 257 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 258 int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2); 259 if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() 260 && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) 261 return true; 262 } 263 } 264 } 265 } 266 267 // check for distance conflicts within the enrollment 268 if (cx.getDistanceMetric().isHardDistanceConflictsEnabled()) { 269 for (Section s1: enrollment.getSections()) { 270 // no time or no room > no conflict 271 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 272 for (Section s2: enrollment.getSections()) { 273 if (s1.getId() < s2.getId()) { 274 // no time or no room > no conflict 275 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 276 TimeLocation t1 = s1.getTime(); 277 TimeLocation t2 = s2.getTime(); 278 // no shared day > no conflict 279 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue; 280 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 281 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 282 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 283 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 284 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 285 && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 286 return true; 287 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 288 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 289 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 290 && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 291 return true; 292 } 293 } else { 294 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 295 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 296 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 297 && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 298 return true; 299 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 300 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 301 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 302 && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 303 return true; 304 } 305 } 306 } 307 } 308 } 309 310 // check conflicts with other enrollments of the student 311 for (Request other: student.getRequests()) { 312 if (other.equals(enrollment.variable())) continue; 313 Enrollment e2 = other.getAssignment(assignment); 314 if (e2 == null) continue; 315 for (Section s1: enrollment.getSections()) { 316 // no time or no room > no conflict 317 if (!s1.hasTime() || s1.getNrRooms() == 0) continue; 318 for (Section s2: e2.getSections()) { 319 // no time or no room > no conflict 320 if (!s2.hasTime() || s2.getNrRooms() == 0) continue; 321 TimeLocation t1 = s1.getTime(); 322 TimeLocation t2 = s2.getTime(); 323 // no shared day > no conflict 324 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue; 325 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 326 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 327 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 328 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 329 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 330 return true; 331 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 332 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 333 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 334 return true; 335 } 336 } else { 337 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 338 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 339 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 340 return true; 341 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 342 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 343 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 344 return true; 345 } 346 } 347 348 } 349 350 } 351 } 352 } 353 354 return false; 355 } 356 357 public static boolean inConflict(StudentQuality sq, Section s1, Unavailability s2) { 358 if (s1.getPlacement() == null || s2.getTime() == null || s2.getNrRooms() == 0) return false; 359 if (sq == null) return false; 360 StudentQuality.Context cx = sq.getStudentQualityContext(); 361 if (!cx.getUnavailabilityDistanceMetric().isHardDistanceConflictsEnabled()) return false; 362 TimeLocation t1 = s1.getTime(); 363 TimeLocation t2 = s2.getTime(); 364 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 365 return false; 366 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 367 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 368 int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2); 369 if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() && 370 dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) 371 return true; 372 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 373 int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2); 374 if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() && 375 dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) 376 return true; 377 } 378 return false; 379 } 380 381 public static boolean inConflict(StudentQuality sq, Section s1, Section s2) { 382 if (s1.getPlacement() == null || s2.getTime() == null || s2.getNrRooms() == 0) return false; 383 if (sq == null) return false; 384 StudentQuality.Context cx = sq.getStudentQualityContext(); 385 if (!cx.getDistanceMetric().isHardDistanceConflictsEnabled()) return false; 386 TimeLocation t1 = s1.getTime(); 387 TimeLocation t2 = s2.getTime(); 388 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 389 return false; 390 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 391 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 392 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 393 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && 394 dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 395 return true; 396 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 397 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 398 if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && 399 dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) 400 return true; 401 } 402 return false; 403 } 404 405 public static boolean inConflict(StudentQuality sq, SctAssignment s1, Enrollment e) { 406 if (sq == null) return false; 407 if (!sq.getStudentQualityContext().getDistanceMetric().isHardDistanceConflictsEnabled()) return false; 408 if (s1 instanceof Section) 409 for (SctAssignment s2: e.getAssignments()) 410 if (s2 instanceof Section && inConflict(sq, (Section)s1, (Section)s2)) return true; 411 return false; 412 } 413 414 @Override 415 public String toString() { 416 return "DistanceConflict"; 417 } 418}