001package org.cpsolver.studentsct.weights; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.BitSet; 006import java.util.HashSet; 007import java.util.Set; 008 009import org.cpsolver.coursett.model.Placement; 010import org.cpsolver.coursett.model.RoomLocation; 011import org.cpsolver.coursett.model.TimeLocation; 012import org.cpsolver.ifs.assignment.Assignment; 013import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 014import org.cpsolver.ifs.solution.Solution; 015import org.cpsolver.ifs.util.DataProperties; 016import org.cpsolver.ifs.util.ToolBox; 017import org.cpsolver.studentsct.StudentSectioningModel; 018import org.cpsolver.studentsct.extension.DistanceConflict; 019import org.cpsolver.studentsct.extension.StudentQuality; 020import org.cpsolver.studentsct.extension.StudentQuality.Conflict; 021import org.cpsolver.studentsct.extension.TimeOverlapsCounter; 022import org.cpsolver.studentsct.model.Choice; 023import org.cpsolver.studentsct.model.Config; 024import org.cpsolver.studentsct.model.Course; 025import org.cpsolver.studentsct.model.CourseRequest; 026import org.cpsolver.studentsct.model.Enrollment; 027import org.cpsolver.studentsct.model.Instructor; 028import org.cpsolver.studentsct.model.Offering; 029import org.cpsolver.studentsct.model.Request; 030import org.cpsolver.studentsct.model.RequestGroup; 031import org.cpsolver.studentsct.model.SctAssignment; 032import org.cpsolver.studentsct.model.Section; 033import org.cpsolver.studentsct.model.Student; 034import org.cpsolver.studentsct.model.Subpart; 035 036 037/** 038 * New weighting model. It tries to obey the following principles: 039 * <ul> 040 * <li> Total student weight is between zero and one (one means student got the best schedule) 041 * <li> Weight of the given priority course is higher than sum of the remaining weights the student can get 042 * <li> First alternative is better than the following course 043 * <li> Second alternative is better than the second following course 044 * <li> Distance conflicts are considered secondary (priorities should be maximized first) 045 * <li> If alternative sections are otherwise equal, use the better balanced one 046 * </ul> 047 * 048 * @version StudentSct 1.3 (Student Sectioning)<br> 049 * Copyright (C) 2007 - 2014 Tomas Muller<br> 050 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 051 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 052 * <br> 053 * This library is free software; you can redistribute it and/or modify 054 * it under the terms of the GNU Lesser General Public License as 055 * published by the Free Software Foundation; either version 3 of the 056 * License, or (at your option) any later version. <br> 057 * <br> 058 * This library is distributed in the hope that it will be useful, but 059 * WITHOUT ANY WARRANTY; without even the implied warranty of 060 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 061 * Lesser General Public License for more details. <br> 062 * <br> 063 * You should have received a copy of the GNU Lesser General Public 064 * License along with this library; if not see 065 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 066 */ 067 068public class PriorityStudentWeights implements StudentWeights { 069 protected double iPriorityFactor = 0.5010; 070 protected double iFirstAlternativeFactor = 0.5010; 071 protected double iSecondAlternativeFactor = 0.2510; 072 protected double iDistanceConflict = 0.0100; 073 protected double iShortDistanceConflict = 0.1000; 074 protected double iTimeOverlapFactor = 0.5000; 075 protected double iTimeOverlapMaxLimit = 0.5000; 076 protected boolean iLeftoverSpread = false; 077 protected double iBalancingFactor = 0.0050; 078 protected double iNoTimeFactor = 0.0100; 079 protected double iOnlineFactor = 0.0100; 080 protected double iReservationNotFollowedFactor = 0.1000; 081 protected double iAlternativeRequestFactor = 0.1260; 082 protected double iProjectedStudentWeight = 0.0100; 083 protected boolean iMPP = false; 084 protected double iPerturbationFactor = 0.100; 085 protected double iSelectionFactor = 0.100; 086 protected double iSameChoiceWeight = 0.900; 087 protected double iSameTimeWeight = 0.700; 088 protected double iSameConfigWeight = 0.500; 089 protected double iGroupFactor = 0.100; 090 protected double iGroupBestRatio = 0.95; 091 protected double iGroupFillRatio = 0.05; 092 protected boolean iAdditiveWeights = false; 093 protected boolean iMaximizeAssignment = false; 094 protected boolean iPreciseComparison = false; 095 protected double[] iQalityWeights; 096 protected boolean iImprovedBound = true; 097 protected double iCriticalBoost = 1.0; 098 protected double iPriortyBoost = 1.0; 099 100 public PriorityStudentWeights(DataProperties config) { 101 iPriorityFactor = config.getPropertyDouble("StudentWeights.Priority", iPriorityFactor); 102 iFirstAlternativeFactor = config.getPropertyDouble("StudentWeights.FirstAlternative", iFirstAlternativeFactor); 103 iSecondAlternativeFactor = config.getPropertyDouble("StudentWeights.SecondAlternative", iSecondAlternativeFactor); 104 iDistanceConflict = config.getPropertyDouble("StudentWeights.DistanceConflict", iDistanceConflict); 105 iShortDistanceConflict = config.getPropertyDouble("StudentWeights.ShortDistanceConflict", iShortDistanceConflict); 106 iTimeOverlapFactor = config.getPropertyDouble("StudentWeights.TimeOverlapFactor", iTimeOverlapFactor); 107 iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit); 108 iLeftoverSpread = config.getPropertyBoolean("StudentWeights.LeftoverSpread", iLeftoverSpread); 109 iBalancingFactor = config.getPropertyDouble("StudentWeights.BalancingFactor", iBalancingFactor); 110 iAlternativeRequestFactor = config.getPropertyDouble("StudentWeights.AlternativeRequestFactor", iAlternativeRequestFactor); 111 iProjectedStudentWeight = config.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight); 112 iMPP = config.getPropertyBoolean("General.MPP", false); 113 iPerturbationFactor = config.getPropertyDouble("StudentWeights.Perturbation", iPerturbationFactor); 114 iSelectionFactor = config.getPropertyDouble("StudentWeights.Selection", iSelectionFactor); 115 iSameChoiceWeight = config.getPropertyDouble("StudentWeights.SameChoice", iSameChoiceWeight); 116 iSameTimeWeight = config.getPropertyDouble("StudentWeights.SameTime", iSameTimeWeight); 117 iSameConfigWeight = config.getPropertyDouble("StudentWeights.SameConfig", iSameConfigWeight); 118 iGroupFactor = config.getPropertyDouble("StudentWeights.SameGroup", iGroupFactor); 119 iGroupBestRatio = config.getPropertyDouble("StudentWeights.GroupBestRatio", iGroupBestRatio); 120 iGroupFillRatio = config.getPropertyDouble("StudentWeights.GroupFillRatio", iGroupFillRatio); 121 iNoTimeFactor = config.getPropertyDouble("StudentWeights.NoTimeFactor", iNoTimeFactor); 122 iOnlineFactor = config.getPropertyDouble("StudentWeights.OnlineFactor", iOnlineFactor); 123 iReservationNotFollowedFactor = config.getPropertyDouble("StudentWeights.ReservationNotFollowedFactor", iReservationNotFollowedFactor); 124 iAdditiveWeights = config.getPropertyBoolean("StudentWeights.AdditiveWeights", iAdditiveWeights); 125 iMaximizeAssignment = config.getPropertyBoolean("StudentWeights.MaximizeAssignment", iMaximizeAssignment); 126 iPreciseComparison = config.getPropertyBoolean("StudentWeights.PreciseComparison", iPreciseComparison); 127 iQalityWeights = new double[StudentQuality.Type.values().length]; 128 for (StudentQuality.Type type: StudentQuality.Type.values()) { 129 iQalityWeights[type.ordinal()] = config.getPropertyDouble(type.getWeightName(), type.getWeightDefault()); 130 } 131 iImprovedBound = config.getPropertyBoolean("StudentWeights.ImprovedBound", iImprovedBound); 132 iPriortyBoost = config.getPropertyDouble("StudentWeights.PriortyBoost", 1.0); 133 iCriticalBoost = config.getPropertyDouble("StudentWeights.CriticalBoost", 1.0); 134 } 135 136 public double getWeight(Request request) { 137 if (request.getStudent().isDummy() && iProjectedStudentWeight >= 0.0) { 138 double weight = iProjectedStudentWeight; 139 if (request.isAlternative()) 140 weight *= iAlternativeRequestFactor; 141 return weight; 142 } 143 double total = 1000000.0; 144 int nrReq = request.getStudent().nrRequests(); 145 double remain = (iLeftoverSpread ? Math.floor(1000000.0 * Math.pow(iPriorityFactor, nrReq) / nrReq) : 0.0); 146 for (int idx = 0; idx < request.getStudent().getRequests().size(); idx++) { 147 Request r = request.getStudent().getRequests().get(idx); 148 boolean last = (idx + 1 == request.getStudent().getRequests().size()); 149 boolean lastNotAlt = !r.isAlternative() && (last || request.getStudent().getRequests().get(1 + idx).isAlternative()); 150 double w = Math.ceil(iPriorityFactor * total) + remain; 151 if (!iLeftoverSpread && lastNotAlt) { 152 w = total; 153 } else { 154 total -= w; 155 } 156 if (r.equals(request)) { 157 return w / 1000000.0; 158 } 159 } 160 return 0.0; 161 } 162 163 public double getBoostedWeight(Request request) { 164 double weight = getWeight(request); 165 if (iPriortyBoost != 1.0) { 166 Double boost = request.getStudent().getPriority().getBoost(); 167 if (boost != null) 168 weight *= boost * iPriortyBoost; 169 } 170 if (iCriticalBoost != 1.0) { 171 Double boost = request.getRequestPriority().getBoost(); 172 if (boost != null) 173 weight *= boost * iCriticalBoost; 174 } 175 return weight; 176 } 177 178 public double getCachedWeight(Request request) { 179 double[] cache = (double[])request.getExtra(); 180 if (cache == null) { 181 double base = getBoostedWeight(request); 182 cache = new double[]{base, computeBound(base, request)}; 183 request.setExtra(cache); 184 } 185 return cache[0]; 186 } 187 188 /** 189 * Return how much the given enrollment is different from the initial enrollment 190 * @param enrollment given enrollment 191 * @return 0.0 when all the sections are the same, 1.0 when all the section are different (including different times) 192 */ 193 protected double getDifference(Enrollment enrollment) { 194 if (enrollment.getStudent().isDummy() || !enrollment.isCourseRequest()) return 1.0; 195 Enrollment other = enrollment.getRequest().getInitialAssignment(); 196 if (other != null) { 197 double similarSections = 0.0; 198 if (enrollment.getConfig().equals(other.getConfig())) { 199 // same configurations -- compare sections of matching subpart 200 for (Section section: enrollment.getSections()) { 201 for (Section initial: other.getSections()) { 202 if (section.getSubpart().equals(initial.getSubpart())) { 203 if (section.equals(initial)) { 204 similarSections += 1.0; 205 } else if (section.sameChoice(initial)) { 206 similarSections += iSameChoiceWeight; 207 } else if (section.sameTime(initial)) { 208 similarSections += iSameTimeWeight; 209 } 210 break; 211 } 212 } 213 } 214 } else { 215 // different configurations -- compare sections of matching itype 216 for (Section section: enrollment.getSections()) { 217 for (Section initial: other.getSections()) { 218 if (section.sameChoice(initial)) { 219 similarSections += iSameChoiceWeight; 220 break; 221 } else if (section.sameInstructionalType(initial) && section.sameTime(initial)) { 222 similarSections += iSameTimeWeight; 223 break; 224 } 225 } 226 } 227 } 228 return 1.0 - similarSections / enrollment.getAssignments().size(); 229 } 230 return 1.0; 231 } 232 233 /** 234 * Return how much the given enrollment is different from the selection (if any) 235 * @param enrollment given enrollment 236 * @return 0.0 when all the sections are the same, 1.0 when all the section are different (including different times) 237 */ 238 public double getSelection(Enrollment enrollment) { 239 if (enrollment.getStudent().isDummy()) return 1.0; 240 if (enrollment.isCourseRequest()) { 241 CourseRequest cr = (CourseRequest)enrollment.getRequest(); 242 if (!cr.getSelectedChoices().isEmpty()) { 243 double similarSections = 0.0; 244 for (Section section: enrollment.getSections()) { 245 double bestChoice = 0.0; 246 for (Choice ch: cr.getSelectedChoices()) { 247 if (bestChoice < 1.0 && ch.sameSection(section)) { 248 bestChoice = 1.0; 249 } else if (bestChoice < iSameChoiceWeight && ch.sameChoice(section)) { 250 bestChoice = iSameChoiceWeight; 251 } else if (bestChoice < iSameTimeWeight && ch.sameOffering(section) && ch.sameInstructionalType(section) && ch.sameTime(section)) { 252 bestChoice = iSameTimeWeight; 253 } else if (bestChoice < iSameConfigWeight && ch.sameConfiguration(section)) { 254 bestChoice = iSameConfigWeight; 255 } 256 } 257 similarSections += bestChoice; 258 } 259 return 1.0 - similarSections / enrollment.getAssignments().size(); 260 } else { 261 return 1.0; 262 } 263 } else { 264 return 1.0; 265 } 266 } 267 268 269 @Override 270 public double getBound(Request request) { 271 double[] cache = (double[])request.getExtra(); 272 if (cache == null) { 273 double base = getBoostedWeight(request); 274 cache = new double[]{base, computeBound(base, request)}; 275 request.setExtra(cache); 276 } 277 return cache[1]; 278 } 279 280 protected double computeBound(double base, Request request) { 281 if (!iImprovedBound) return base; 282 if (iAdditiveWeights) { 283 double weight = 0.0; 284 if (request instanceof CourseRequest) { 285 CourseRequest cr = (CourseRequest)request; 286 if (iNoTimeFactor != 0.0 && !cr.getCourses().isEmpty()) { 287 weight += iNoTimeFactor * cr.getCourses().get(0).getArrHrsBound(); 288 } 289 if (iOnlineFactor != 0.0 && !cr.getCourses().isEmpty()) { 290 weight += iOnlineFactor * cr.getCourses().get(0).getOnlineBound(); 291 } 292 if (iMPP && cr.getInitialAssignment() == null) { 293 weight += iPerturbationFactor; 294 } 295 if (iSelectionFactor != 0.0 && cr.getSelectedChoices().isEmpty()) { 296 weight += iSelectionFactor; 297 } 298 } 299 return round(base * (1.0 - weight)); 300 } else { 301 double weight = base; 302 if (request instanceof CourseRequest) { 303 CourseRequest cr = (CourseRequest)request; 304 if (iNoTimeFactor != 0.0 && !cr.getCourses().isEmpty()) { 305 weight *= (1.0 - iNoTimeFactor * cr.getCourses().get(0).getArrHrsBound()); 306 } 307 if (iOnlineFactor != 0.0 && !cr.getCourses().isEmpty()) { 308 weight *= (1.0 - iOnlineFactor * cr.getCourses().get(0).getOnlineBound()); 309 } 310 if (iMPP && cr.getInitialAssignment() == null) { 311 weight *= (1.0 - iPerturbationFactor); 312 } 313 if (iSelectionFactor != 0.0 && cr.getSelectedChoices().isEmpty()) { 314 weight *= (1.0 - iSelectionFactor); 315 } 316 } 317 return round(weight); 318 } 319 } 320 321 protected double round(double value) { 322 return Math.ceil(1000000.0 * value) / 1000000.0; 323 } 324 325 protected double getBaseWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 326 double weight = getCachedWeight(enrollment.getRequest()); 327 switch (enrollment.getTruePriority()) { 328 case 0: break; 329 case 1: weight *= iFirstAlternativeFactor; break; 330 case 2: weight *= iSecondAlternativeFactor; break; 331 default: 332 weight *= Math.pow(iFirstAlternativeFactor, enrollment.getTruePriority()); 333 } 334 return weight; 335 } 336 337 @Override 338 public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 339 if (iAdditiveWeights) 340 return getWeightAdditive(assignment, enrollment); 341 else 342 return getWeightMultiplicative(assignment, enrollment); 343 } 344 345 public double getWeightMultiplicative(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 346 double weight = getBaseWeight(assignment, enrollment); 347 if (enrollment.isCourseRequest() && iNoTimeFactor != 0.0) { 348 int noTimeSections = 0, total = 0; 349 for (Section section: enrollment.getSections()) { 350 if (section.getTime() == null) noTimeSections ++; 351 total ++; 352 } 353 if (noTimeSections > 0) 354 weight *= (1.0 - iNoTimeFactor * noTimeSections / total); 355 } 356 if (enrollment.isCourseRequest() && iOnlineFactor != 0.0) { 357 int onlineSections = 0, total = 0; 358 for (Section section: enrollment.getSections()) { 359 if (section.isOnline()) onlineSections ++; 360 total ++; 361 } 362 if (onlineSections > 0) 363 weight *= (1.0 - iOnlineFactor * onlineSections / total); 364 } 365 if (enrollment.getTruePriority() < enrollment.getPriority()) { 366 weight *= (1.0 - iReservationNotFollowedFactor); 367 } 368 if (enrollment.isCourseRequest() && iBalancingFactor != 0.0) { 369 double configUsed = enrollment.getConfig().getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight(); 370 double disbalanced = 0; 371 double total = 0; 372 for (Section section: enrollment.getSections()) { 373 Subpart subpart = section.getSubpart(); 374 if (subpart.getSections().size() <= 1) continue; 375 double used = section.getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight(); 376 // sections have limits -> desired size is section limit x (total enrollment / total limit) 377 // unlimited sections -> desired size is total enrollment / number of sections 378 double desired = (subpart.getLimit() > 0 379 ? section.getLimit() * (configUsed / subpart.getLimit()) 380 : configUsed / subpart.getSections().size()); 381 if (used > desired) 382 disbalanced += Math.min(enrollment.getRequest().getWeight(), used - desired) / enrollment.getRequest().getWeight(); 383 else 384 disbalanced -= Math.min(enrollment.getRequest().getWeight(), desired - used) / enrollment.getRequest().getWeight(); 385 total ++; 386 } 387 if (disbalanced > 0) 388 weight *= (1.0 - disbalanced / total * iBalancingFactor); 389 } 390 if (iMPP) { 391 double difference = getDifference(enrollment); 392 if (difference > 0.0) 393 weight *= (1.0 - difference * iPerturbationFactor); 394 } 395 if (iSelectionFactor != 0.0) { 396 double selection = getSelection(enrollment); 397 if (selection > 0.0) 398 weight *= (1.0 - selection * iSelectionFactor); 399 } 400 if (enrollment.isCourseRequest() && iGroupFactor != 0.0) { 401 double sameGroup = 0.0; int groupCount = 0; 402 for (RequestGroup g: ((CourseRequest)enrollment.getRequest()).getRequestGroups()) { 403 if (g.getCourse().equals(enrollment.getCourse())) { 404 sameGroup += g.getEnrollmentSpread(assignment, enrollment, iGroupBestRatio, iGroupFillRatio); 405 groupCount ++; 406 } 407 } 408 if (groupCount > 0) { 409 double difference = 1.0 - sameGroup / groupCount; 410 weight *= (1.0 - difference * iGroupFactor); 411 } 412 } 413 return round(weight); 414 } 415 416 public double getWeightAdditive(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 417 double base = getBaseWeight(assignment, enrollment); 418 double weight = 0.0; 419 if (enrollment.isCourseRequest() && iNoTimeFactor != 0.0) { 420 int noTimeSections = 0, total = 0; 421 for (Section section: enrollment.getSections()) { 422 if (section.getTime() == null) noTimeSections ++; 423 total ++; 424 } 425 if (noTimeSections > 0) 426 weight += iNoTimeFactor * noTimeSections / total; 427 } 428 if (enrollment.isCourseRequest() && iOnlineFactor != 0.0) { 429 int onlineSections = 0, total = 0; 430 for (Section section: enrollment.getSections()) { 431 if (section.isOnline()) onlineSections ++; 432 total ++; 433 } 434 if (onlineSections > 0) 435 weight += iOnlineFactor * onlineSections / total; 436 } 437 if (enrollment.getTruePriority() < enrollment.getPriority()) { 438 weight += iReservationNotFollowedFactor; 439 } 440 if (enrollment.isCourseRequest() && iBalancingFactor != 0.0) { 441 double configUsed = enrollment.getConfig().getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight(); 442 double disbalanced = 0; 443 double total = 0; 444 for (Section section: enrollment.getSections()) { 445 Subpart subpart = section.getSubpart(); 446 if (subpart.getSections().size() <= 1) continue; 447 double used = section.getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight(); 448 // sections have limits -> desired size is section limit x (total enrollment / total limit) 449 // unlimited sections -> desired size is total enrollment / number of sections 450 double desired = (subpart.getLimit() > 0 451 ? section.getLimit() * (configUsed / subpart.getLimit()) 452 : configUsed / subpart.getSections().size()); 453 if (used > desired) 454 disbalanced += Math.min(enrollment.getRequest().getWeight(), used - desired) / enrollment.getRequest().getWeight(); 455 else 456 disbalanced -= Math.min(enrollment.getRequest().getWeight(), desired - used) / enrollment.getRequest().getWeight(); 457 total ++; 458 } 459 if (disbalanced > 0) 460 weight += disbalanced / total * iBalancingFactor; 461 } 462 if (iMPP) { 463 double difference = getDifference(enrollment); 464 if (difference > 0.0) 465 weight += difference * iPerturbationFactor; 466 } 467 if (iSelectionFactor != 0.0) { 468 double selection = getSelection(enrollment); 469 if (selection > 0.0) 470 weight += selection * iSelectionFactor; 471 } 472 if (enrollment.isCourseRequest() && iGroupFactor != 0.0) { 473 double sameGroup = 0.0; int groupCount = 0; 474 for (RequestGroup g: ((CourseRequest)enrollment.getRequest()).getRequestGroups()) { 475 if (g.getCourse().equals(enrollment.getCourse())) { 476 sameGroup += g.getEnrollmentSpread(assignment, enrollment, iGroupBestRatio, iGroupFillRatio); 477 groupCount ++; 478 } 479 } 480 if (groupCount > 0) { 481 double difference = 1.0 - sameGroup / groupCount; 482 weight += difference * iGroupFactor; 483 } 484 } 485 return round(base * (1.0 - weight)); 486 } 487 488 @Override 489 public double getDistanceConflictWeight(Assignment<Request, Enrollment> assignment, DistanceConflict.Conflict c) { 490 if (iAdditiveWeights) { 491 if (c.getR1().getPriority() < c.getR2().getPriority()) { 492 return round(getBaseWeight(assignment, c.getE2()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict)); 493 } else { 494 return round(getBaseWeight(assignment, c.getE1()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict)); 495 } 496 } else { 497 if (c.getR1().getPriority() < c.getR2().getPriority()) { 498 return round(getWeightMultiplicative(assignment, c.getE2()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict)); 499 } else { 500 return round(getWeightMultiplicative(assignment, c.getE1()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict)); 501 } 502 } 503 } 504 505 @Override 506 public double getTimeOverlapConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment e, TimeOverlapsCounter.Conflict c) { 507 if (e == null || e.getRequest() == null) return 0.0; 508 double toc = Math.min(iTimeOverlapFactor * c.getShare() / e.getNrSlots(), iTimeOverlapMaxLimit); 509 if (iAdditiveWeights) { 510 return round(getBaseWeight(assignment, e) * toc); 511 } else { 512 return round(getWeightMultiplicative(assignment, e) * toc); 513 } 514 } 515 516 @Override 517 public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 518 if (iAdditiveWeights) { 519 double base = getBaseWeight(assignment, enrollment); 520 double dc = 0.0; 521 if (distanceConflicts != null) { 522 for (DistanceConflict.Conflict c: distanceConflicts) { 523 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 524 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 525 dc += base * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict); 526 else 527 dc += getBaseWeight(assignment, other) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict); 528 } 529 } 530 double toc = 0.0; 531 if (timeOverlappingConflicts != null) { 532 for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) { 533 toc += base * Math.min(iTimeOverlapFactor * c.getShare() / enrollment.getNrSlots(), iTimeOverlapMaxLimit); 534 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 535 if (other.getRequest() != null) 536 toc += getBaseWeight(assignment, other) * Math.min(iTimeOverlapFactor * c.getShare() / other.getNrSlots(), iTimeOverlapMaxLimit); 537 } 538 } 539 return round(getWeight(assignment, enrollment) - dc - toc); 540 } else { 541 double base = getWeightMultiplicative(assignment, enrollment); 542 double dc = 0.0; 543 if (distanceConflicts != null) { 544 for (DistanceConflict.Conflict c: distanceConflicts) { 545 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 546 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 547 dc += base * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict); 548 else 549 dc += getWeightMultiplicative(assignment, other) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict); 550 } 551 } 552 double toc = 0.0; 553 if (timeOverlappingConflicts != null) { 554 for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) { 555 toc += base * Math.min(iTimeOverlapFactor * c.getShare() / enrollment.getNrSlots(), iTimeOverlapMaxLimit); 556 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 557 if (other.getRequest() != null) 558 toc += getWeightMultiplicative(assignment, other) * Math.min(iTimeOverlapFactor * c.getShare() / other.getNrSlots(), iTimeOverlapMaxLimit); 559 } 560 } 561 return round(base - dc - toc); 562 } 563 } 564 565 566 @Override 567 public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) { 568 if (currentSolution.getBestInfo() == null) return true; 569 if (iMaximizeAssignment) { 570 long acr = Math.round(((StudentSectioningModel)currentSolution.getModel()).getContext(currentSolution.getAssignment()).getAssignedCourseRequestWeight()); 571 long bcr = Math.round(((StudentSectioningModel)currentSolution.getModel()).getBestAssignedCourseRequestWeight()); 572 if (acr != bcr) 573 return acr > bcr; 574 } 575 return ((StudentSectioningModel)currentSolution.getModel()).getTotalValue(currentSolution.getAssignment(), iPreciseComparison) < currentSolution.getBestValue(); 576 } 577 578 @Override 579 public boolean isFreeTimeAllowOverlaps() { 580 return false; 581 } 582 583 /** 584 * Test case -- run to see the weights for a few courses 585 * @param args program arguments 586 */ 587 public static void main(String[] args) { 588 PriorityStudentWeights pw = new PriorityStudentWeights(new DataProperties()); 589 DecimalFormat df = new DecimalFormat("0.000000"); 590 Student s = new Student(0l); 591 new CourseRequest(1l, 0, false, s, ToolBox.toList( 592 new Course(1, "A", "1", new Offering(0, "A")), 593 new Course(1, "A", "2", new Offering(0, "A")), 594 new Course(1, "A", "3", new Offering(0, "A"))), false, null); 595 new CourseRequest(2l, 1, false, s, ToolBox.toList( 596 new Course(1, "B", "1", new Offering(0, "B")), 597 new Course(1, "B", "2", new Offering(0, "B")), 598 new Course(1, "B", "3", new Offering(0, "B"))), false, null); 599 new CourseRequest(3l, 2, false, s, ToolBox.toList( 600 new Course(1, "C", "1", new Offering(0, "C")), 601 new Course(1, "C", "2", new Offering(0, "C")), 602 new Course(1, "C", "3", new Offering(0, "C"))), false, null); 603 new CourseRequest(4l, 3, false, s, ToolBox.toList( 604 new Course(1, "D", "1", new Offering(0, "D")), 605 new Course(1, "D", "2", new Offering(0, "D")), 606 new Course(1, "D", "3", new Offering(0, "D"))), false, null); 607 new CourseRequest(5l, 4, false, s, ToolBox.toList( 608 new Course(1, "E", "1", new Offering(0, "E")), 609 new Course(1, "E", "2", new Offering(0, "E")), 610 new Course(1, "E", "3", new Offering(0, "E"))), false, null); 611 new CourseRequest(6l, 5, true, s, ToolBox.toList( 612 new Course(1, "F", "1", new Offering(0, "F")), 613 new Course(1, "F", "2", new Offering(0, "F")), 614 new Course(1, "F", "3", new Offering(0, "F"))), false, null); 615 new CourseRequest(7l, 6, true, s, ToolBox.toList( 616 new Course(1, "G", "1", new Offering(0, "G")), 617 new Course(1, "G", "2", new Offering(0, "G")), 618 new Course(1, "G", "3", new Offering(0, "G"))), false, null); 619 620 Assignment<Request, Enrollment> assignment = new DefaultSingleAssignment<Request, Enrollment>(); 621 Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>()); 622 for (Request r: s.getRequests()) { 623 CourseRequest cr = (CourseRequest)r; 624 double[] w = new double[] {0.0, 0.0, 0.0}; 625 for (int i = 0; i < cr.getCourses().size(); i++) { 626 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 627 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 628 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 629 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 630 w[i] = pw.getWeight(assignment, e, null, null); 631 } 632 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 633 } 634 635 System.out.println("With one distance conflict:"); 636 for (Request r: s.getRequests()) { 637 CourseRequest cr = (CourseRequest)r; 638 double[] w = new double[] {0.0, 0.0, 0.0}; 639 for (int i = 0; i < cr.getCourses().size(); i++) { 640 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 641 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 642 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 643 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 644 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 645 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 646 w[i] = pw.getWeight(assignment, e, dc, null); 647 } 648 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 649 } 650 651 System.out.println("With two distance conflicts:"); 652 for (Request r: s.getRequests()) { 653 CourseRequest cr = (CourseRequest)r; 654 double[] w = new double[] {0.0, 0.0, 0.0}; 655 for (int i = 0; i < cr.getCourses().size(); i++) { 656 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 657 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 658 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 659 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 660 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 661 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 662 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, 663 new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null))); 664 w[i] = pw.getWeight(assignment, e, dc, null); 665 } 666 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 667 } 668 669 System.out.println("With 25% time overlapping conflict:"); 670 for (Request r: s.getRequests()) { 671 CourseRequest cr = (CourseRequest)r; 672 double[] w = new double[] {0.0, 0.0, 0.0}; 673 for (int i = 0; i < cr.getCourses().size(); i++) { 674 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 675 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 676 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 677 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 678 Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>(); 679 toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next())); 680 w[i] = pw.getWeight(assignment, e, null, toc); 681 } 682 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 683 } 684 685 System.out.println("Disbalanced sections (by 2 / 10 students):"); 686 for (Request r: s.getRequests()) { 687 CourseRequest cr = (CourseRequest)r; 688 double[] w = new double[] {0.0, 0.0, 0.0}; 689 for (int i = 0; i < cr.getCourses().size(); i++) { 690 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 691 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 692 Subpart x = new Subpart(0, "Lec", "Lec", cfg, null); 693 Section a = new Section(0, 10, "x", x, p, null); 694 new Section(1, 10, "y", x, p, null); 695 sections.add(a); 696 a.assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment)); 697 a.assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment)); 698 cfg.getContext(assignment).assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment)); 699 cfg.getContext(assignment).assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment)); 700 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 701 w[i] = pw.getWeight(assignment, e, null, null); 702 } 703 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 704 } 705 706 System.out.println("Same choice sections:"); 707 pw.iMPP = true; 708 for (Request r: s.getRequests()) { 709 CourseRequest cr = (CourseRequest)r; 710 double[] w = new double[] {0.0, 0.0, 0.0}; 711 for (int i = 0; i < cr.getCourses().size(); i++) { 712 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 713 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 714 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 715 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 716 Set<SctAssignment> other = new HashSet<SctAssignment>(); 717 other.add(new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 718 cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment)); 719 w[i] = pw.getWeight(assignment, e, null, null); 720 } 721 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 722 } 723 724 System.out.println("Same time sections:"); 725 for (Request r: s.getRequests()) { 726 CourseRequest cr = (CourseRequest)r; 727 double[] w = new double[] {0.0, 0.0, 0.0}; 728 for (int i = 0; i < cr.getCourses().size(); i++) { 729 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 730 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 731 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 732 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 733 Set<SctAssignment> other = new HashSet<SctAssignment>(); 734 other.add(new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, new Instructor(1l, null, "Josef Novak", null))); 735 cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment)); 736 w[i] = pw.getWeight(assignment, e, null, null); 737 } 738 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 739 } 740 741 System.out.println("Different time sections:"); 742 Placement q = new Placement(null, new TimeLocation(1, 102, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>()); 743 for (Request r: s.getRequests()) { 744 CourseRequest cr = (CourseRequest)r; 745 double[] w = new double[] {0.0, 0.0, 0.0}; 746 for (int i = 0; i < cr.getCourses().size(); i++) { 747 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 748 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 749 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 750 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 751 Set<SctAssignment> other = new HashSet<SctAssignment>(); 752 other.add(new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), q, null)); 753 cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment)); 754 w[i] = pw.getWeight(assignment, e, null, null); 755 } 756 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 757 } 758 759 System.out.println("Two sections, one same choice, one same time:"); 760 for (Request r: s.getRequests()) { 761 CourseRequest cr = (CourseRequest)r; 762 double[] w = new double[] {0.0, 0.0, 0.0}; 763 for (int i = 0; i < cr.getCourses().size(); i++) { 764 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 765 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 766 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 767 sections.add(new Section(1, 1, "y", new Subpart(1, "Rec", "Rec", cfg, null), p, null)); 768 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 769 Set<SctAssignment> other = new HashSet<SctAssignment>(); 770 other.add(new Section(2, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 771 other.add(new Section(3, 1, "y", new Subpart(1, "Rec", "Rec", cfg, null), p, null, new Instructor(1l, null, "Josef Novak", null))); 772 cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment)); 773 w[i] = pw.getWeight(assignment, e, null, null); 774 } 775 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 776 } 777 778 } 779 780 @Override 781 public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<StudentQuality.Conflict> qualityConflicts) { 782 if (iAdditiveWeights) { 783 double base = getBaseWeight(assignment, enrollment); 784 double penalty = 0.0; 785 if (qualityConflicts != null) { 786 for (StudentQuality.Conflict c: qualityConflicts) { 787 switch (c.getType().getType()) { 788 case REQUEST: 789 if (enrollment.isCourseRequest()) 790 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 791 break; 792 case BOTH: 793 Enrollment other = c.getOther(enrollment); 794 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 795 penalty += getBaseWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 796 break; 797 case LOWER: 798 other = c.getOther(enrollment); 799 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 800 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 801 else 802 penalty += getBaseWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 803 break; 804 case HIGHER: 805 other = c.getOther(enrollment); 806 if (other.getRequest().getPriority() >= enrollment.getRequest().getPriority()) 807 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 808 else 809 penalty += getBaseWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 810 } 811 } 812 } 813 return round(getWeight(assignment, enrollment) - penalty); 814 } else { 815 double base = getWeightMultiplicative(assignment, enrollment); 816 double penalty = 0.0; 817 if (qualityConflicts != null) { 818 for (StudentQuality.Conflict c: qualityConflicts) { 819 Enrollment other = c.getOther(enrollment); 820 switch (c.getType().getType()) { 821 case REQUEST: 822 if (enrollment.isCourseRequest()) 823 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 824 else if (other.isCourseRequest()) 825 penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 826 break; 827 case BOTH: 828 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 829 if (other.getRequest() != null) 830 penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 831 break; 832 case LOWER: 833 other = c.getOther(enrollment); 834 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 835 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 836 else if (other.getRequest() != null) 837 penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 838 break; 839 case HIGHER: 840 other = c.getOther(enrollment); 841 if (other.getRequest().getPriority() >= enrollment.getRequest().getPriority()) 842 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 843 else if (other.getRequest() != null) 844 penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 845 } 846 } 847 } 848 return round(base - penalty); 849 } 850 } 851 852 @Override 853 public double getStudentQualityConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Conflict conflict) { 854 switch (conflict.getType().getType()) { 855 case BOTH: 856 if (enrollment == null || enrollment.getRequest() == null) return 0.0; 857 if (iAdditiveWeights) { 858 return round(getBaseWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment)); 859 } else { 860 return round(getWeightMultiplicative(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment)); 861 } 862 case REQUEST: 863 if (enrollment == null || enrollment.getRequest() == null || !enrollment.isCourseRequest()) return 0.0; 864 if (iAdditiveWeights) { 865 return round(getBaseWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment)); 866 } else { 867 return round(getWeightMultiplicative(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment)); 868 } 869 case LOWER: 870 if (iAdditiveWeights) { 871 if (conflict.getR1().getPriority() < conflict.getR2().getPriority()) { 872 return round(getBaseWeight(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2())); 873 } else { 874 return round(getBaseWeight(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1())); 875 } 876 } else { 877 if (conflict.getR1().getPriority() < conflict.getR2().getPriority()) { 878 return round(getWeightMultiplicative(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2())); 879 } else { 880 return round(getWeightMultiplicative(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1())); 881 } 882 } 883 case HIGHER: 884 if (iAdditiveWeights) { 885 if (conflict.getR1().getPriority() > conflict.getR2().getPriority()) { 886 return round(getBaseWeight(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2())); 887 } else { 888 return round(getBaseWeight(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1())); 889 } 890 } else { 891 if (conflict.getR1().getPriority() < conflict.getR2().getPriority()) { 892 return round(getWeightMultiplicative(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2())); 893 } else { 894 return round(getWeightMultiplicative(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1())); 895 } 896 } 897 default: 898 return 0.0; 899 } 900 } 901}