001package net.sf.cpsolver.coursett.criteria; 002 003import java.util.Collection; 004import java.util.HashSet; 005import java.util.Set; 006 007import net.sf.cpsolver.coursett.Constants; 008import net.sf.cpsolver.coursett.constraint.JenrlConstraint; 009import net.sf.cpsolver.coursett.model.Lecture; 010import net.sf.cpsolver.coursett.model.Placement; 011import net.sf.cpsolver.coursett.model.Student; 012import net.sf.cpsolver.coursett.model.TimeLocation; 013import net.sf.cpsolver.coursett.model.TimetableModel; 014import net.sf.cpsolver.ifs.solver.Solver; 015import 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 Tomáš Müller<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 */ 043public 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}