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