001package org.cpsolver.coursett.criteria.additional; 002 003import java.util.Arrays; 004import java.util.Collection; 005import java.util.HashSet; 006import java.util.List; 007import java.util.Map; 008import java.util.Set; 009import java.util.TreeMap; 010import org.cpsolver.coursett.constraint.InstructorConstraint; 011import org.cpsolver.coursett.criteria.TimePreferences; 012import org.cpsolver.coursett.criteria.TimetablingCriterion; 013import org.cpsolver.coursett.model.Lecture; 014import org.cpsolver.coursett.model.Placement; 015import org.cpsolver.ifs.assignment.Assignment; 016import org.cpsolver.ifs.util.DataProperties; 017 018/** 019 * This class represent fairness criterion for instructors. 020 * Criterion iteratively evaluate instructors fairness, based on absolute 021 * deviation of the individual satisfaction of instructors time (or time and 022 * room) requirements. 023 * @author Rostislav Burget <BurgetRostislav@gmail.com> <br> 024 * implemented criterion: Instructor Fairness <br> 025 * @version CourseTT 1.3 (University Course Timetabling)<br> 026 * Copyright (C) 2015 Rostislav Burget <BurgetRostislav@gmail.com><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/ 041 * </a>. 042 */ 043public class InstructorFairness extends TimetablingCriterion { 044 045 /** 046 * 047 */ 048 public InstructorFairness() { 049 setValueUpdateType(ValueUpdateType.BeforeUnassignedAfterAssigned); 050 } 051 052 @Override 053 public double getWeightDefault(DataProperties config) { 054 return config.getPropertyDouble("Comparator.InstructorFairnessPreferenceWeight", 1.0); 055 } 056 057 @Override 058 public String getPlacementSelectionWeightName() { 059 return "Placement.InstructorFairnessPreferenceWeight"; 060 } 061 062 @Override 063 public void bestSaved(Assignment<Lecture, Placement> assignment) { 064 iBest = getValue(assignment); 065 } 066 067 @Override 068 public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 069 double ret = 0.0; 070 InstructorFairnessContext context = (InstructorFairnessContext) getContext(assignment); 071 if (context.allInstructorsAssigned(assignment) && !value.variable().getInstructorConstraints().isEmpty()) { 072 List<InstructorConstraint> insConstraints = value.variable().getInstructorConstraints(); 073 ret = (context.getDiffInstrValue(insConstraints, context.fairnessDouble(assignment, value))) / insConstraints.size(); 074 if (conflicts != null) { 075 for (Placement conflict : conflicts) { 076 if (!conflict.variable().getInstructorConstraints().isEmpty()) { 077 List<InstructorConstraint> insConstraints2 = conflict.variable().getInstructorConstraints(); 078 ret -= (context.getDiffInstrValue(insConstraints2, context.fairnessDouble(assignment, conflict))) / insConstraints2.size(); 079 } 080 } 081 } 082 } 083 return ret; 084 } 085 086 @Override 087 public double getValue(Assignment<Lecture, Placement> assignment) { 088 InstructorFairnessContext context = (InstructorFairnessContext) getContext(assignment); 089 if (context.allInstructorsAssigned(assignment)) 090 return context.getObjectiveValue(); 091 return 0.0; 092 } 093 094 @Override 095 public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 096 InstructorFairnessContext context = (InstructorFairnessContext) getContext(assignment); 097 if (context.allInstructorsAssigned(assignment)) { 098 Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>(); 099 for (Lecture lecture : variables) { 100 constraints.addAll(lecture.getInstructorConstraints()); 101 } 102 return context.getObjectiveValue(constraints); 103 } 104 return 0.0; 105 } 106 107 @Override 108 public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) { 109 double value = getValue(assignment); 110 if (value != 0.0) 111 info.put(getName(), sDoubleFormat.format(value)); 112 } 113 114 @Override 115 public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info, Collection<Lecture> variables) { 116 double value = getValue(assignment, variables); 117 if (value != 0.0) 118 info.put(getName(), sDoubleFormat.format(value)); 119 } 120 121 @Override 122 public void getExtendedInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) { 123 if (iDebug) { 124 InstructorFairnessContext context = (InstructorFairnessContext) getContext(assignment); 125 String[] fairnessInfo = context.testFairness(assignment); 126 info.put(getName() + " Details", 127 fairnessInfo[8] + " (avg: " + fairnessInfo[0] + ", rms: " + fairnessInfo[1] + 128 ", Pmax: " + fairnessInfo[2] + ", Pdev: " + fairnessInfo[3] + ", Perror: " + fairnessInfo[4] + 129 ", Pss: " + fairnessInfo[5] + ", Jain's index: " + fairnessInfo[6] + ", max: " + fairnessInfo[7] + ")"); 130 } 131 } 132 133 /** 134 * Context for InstructorFairness 135 */ 136 public class InstructorFairnessContext extends ValueContext { 137 private TreeMap<Long, Instructor> iId2Instructor = new TreeMap<Long, Instructor>(); 138 private double iInstrMeanFairValue = 0.0; 139 private boolean iFullTreeMap = false; 140 private boolean iFirstIterDone = false; 141 142 /** 143 * 144 * @param assignment 145 * current assignment 146 */ 147 public InstructorFairnessContext(Assignment<Lecture, Placement> assignment) { 148 countInstructorFair(assignment); 149 } 150 151 @Override 152 protected void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 153 if (isFirstIterDone()) { 154 countInstructorAssignedFair(assignment, value); 155 } else { 156 countInstructorFair(assignment); 157 } 158 } 159 160 @Override 161 protected void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 162 if (isFirstIterDone()) { 163 countInstructorUnassignedFair(assignment, value); 164 } else { 165 if (countInstructorFair(assignment)) 166 countInstructorUnassignedFair(assignment, value); 167 } 168 } 169 170 /** 171 * This method set fairness values to all instructors 172 * 173 * @param assignment 174 * @return false if complete solution wasn't found 175 */ 176 public boolean countInstructorFair(Assignment<Lecture, Placement> assignment) { 177 if (allInstructorsAssigned(assignment)) { 178 iId2Instructor.clear(); 179 for (Lecture lecture : getModel().variables()) { 180 Double bestPossibleValue = null; 181 182 for (Placement t : lecture.values(assignment)) { 183 double f = fairnessDouble(assignment, t); 184 if (bestPossibleValue == null || f < bestPossibleValue) 185 bestPossibleValue = f; 186 } 187 188 Placement placement = assignment.getValue(lecture); 189 for (InstructorConstraint ic : lecture.getInstructorConstraints()) { 190 Instructor s = iId2Instructor.get(ic.getResourceId()); 191 if (s == null) { 192 s = new Instructor(ic.getResourceId()); 193 iId2Instructor.put(ic.getResourceId(), s); 194 } 195 if (bestPossibleValue != null) 196 s.addBestValue(bestPossibleValue); 197 if (placement != null) { 198 s.addValue(fairnessDouble(assignment, placement)); 199 s.incNumOfClasses(); 200 } 201 } 202 } 203 countInstrMeanFairValue(); 204 setFirstIterDone(); 205 return true; 206 } else { 207 return false; 208 } 209 } 210 211 /** 212 * Method actualize values of instructors whose lecture was just 213 * assigned 214 * 215 * @param assignment 216 * @param value placement of lecture 217 */ 218 219 public void countInstructorAssignedFair(Assignment<Lecture, Placement> assignment, Placement value) { 220 Lecture lec = value.variable(); 221 if (lec.getInstructorConstraints() != null) { 222 List<InstructorConstraint> insConstraints = lec.getInstructorConstraints(); 223 double critValue = fairnessDouble(assignment, lec.getAssignment(assignment)); 224 for (InstructorConstraint ic : insConstraints) { 225 if (!addInstructorValue(ic.getResourceId(), critValue)) { 226 throw new IllegalArgumentException("Instructor " + ic.getResourceId() + " is not present in the context."); 227 } 228 } 229 } 230 countInstrMeanFairValue(); 231 } 232 233 /** 234 * Method actualize values of instructors whose lecture will be 235 * unassigned 236 * 237 * @param assignment 238 * @param value placement of lecture 239 */ 240 241 public void countInstructorUnassignedFair(Assignment<Lecture, Placement> assignment, Placement value) { 242 Lecture lec = value.variable(); 243 if (lec.getInstructorConstraints() != null) { 244 List<InstructorConstraint> insConstraints = lec.getInstructorConstraints(); 245 double critValue = fairnessDouble(assignment, lec.getAssignment(assignment)); 246 for (InstructorConstraint ic : insConstraints) { 247 if (!decreaseInstructorValue(ic.getResourceId(), critValue)) { 248 throw new IllegalArgumentException("Instructor " + ic.getResourceId() + " is not present in the context."); 249 } 250 } 251 } 252 countInstrMeanFairValue(); 253 } 254 255 /** 256 * 257 * @return instructor mean fair value 258 */ 259 public double getInstrMeanFairValue() { 260 return iInstrMeanFairValue; 261 } 262 263 /** 264 * 265 * @return if first iteration was done 266 */ 267 public boolean isFirstIterDone() { 268 return iFirstIterDone; 269 } 270 271 /** 272 * set first iteration done to true 273 */ 274 public void setFirstIterDone() { 275 this.iFirstIterDone = true; 276 } 277 278 /** 279 * 280 * @return number of instructors 281 */ 282 public int getNumOfIstructors() { 283 return iId2Instructor.size(); 284 } 285 286 /** 287 * 288 * @return Collection of instructors in context 289 */ 290 public Collection<Instructor> getInstructorsWithAssig() { 291 return iId2Instructor.values(); 292 } 293 294 /** 295 * Return if complete solution (all variables assigned) was found 296 * in this context 297 * @param assignment 298 * @return true if in this context were all variables assigned 299 * false otherwise 300 */ 301 public boolean allInstructorsAssigned(Assignment<Lecture, Placement> assignment) { 302 if (!iFullTreeMap) { 303 iFullTreeMap = (assignment.nrAssignedVariables() > 0 && assignment.nrUnassignedVariables(getModel()) == 0 && getModel().getBestUnassignedVariables() == 0); 304 } 305 return iFullTreeMap; 306 } 307 308 /** 309 * adding value to instructor in stringInstMap 310 * 311 * @param insID instructor ID 312 * @param value that should be added 313 * @return false if instructor is not in iId2Instructor 314 */ 315 316 public boolean addInstructorValue(Long insID, double value) { 317 Instructor s = iId2Instructor.get(insID); 318 if (s != null) { 319 s.addValue(value); 320 s.incNumOfClasses(); 321 return true; 322 } else { 323 return false; 324 } 325 } 326 327 /** 328 * adding value to instructor in stringInstMap 329 * 330 * @param insID instructor ID 331 * @param value value that should be subtracted 332 * @return false if instructor is not iId2Instructor 333 */ 334 335 public boolean decreaseInstructorValue(Long insID, double value) { 336 Instructor s = iId2Instructor.get(insID); 337 if (s != null) { 338 s.removeValue(value); 339 s.decNumOfClasses(); 340 return true; 341 } else { 342 return false; 343 } 344 } 345 346 /** 347 * compute and return mean fair value of instructors in iId2Instructor 348 */ 349 350 public void countInstrMeanFairValue() { 351 if (!iId2Instructor.isEmpty()) { 352 double sum = 0.0; 353 for (Instructor ins: iId2Instructor.values()) { 354 sum += ins.getFinalValue(); 355 } 356 iInstrMeanFairValue = sum / iId2Instructor.size(); 357 } 358 } 359 360 /** 361 * Method estimates value of placement for instructors in entry list 362 * 363 * @param instructorsList 364 * @param placementValue 365 * @return estimated value of placement for instructors in entry list 366 */ 367 368 public double getDiffInstrValue(List<InstructorConstraint> instructorsList, double placementValue) { 369 double ret = 0.0; 370 for (InstructorConstraint ic : instructorsList) { 371 Instructor i = iId2Instructor.get(ic.getResourceId()); 372 if (i != null) { 373 if (i.getFinalValue() > iInstrMeanFairValue) { 374 ret += ((i.getFinalValue() - iInstrMeanFairValue) / i.getNumOfClasses()) + (placementValue - iInstrMeanFairValue); 375 } else { 376 ret -= ((iInstrMeanFairValue - i.getFinalValue()) / i.getNumOfClasses()) + (iInstrMeanFairValue - placementValue); 377 } 378 } 379 } 380 return ret; 381 } 382 383 /** 384 * Fairness value based on pdev (pdev sec. part) of all instructors 385 * 386 * @return Objective value of all instructors 387 */ 388 389 public double getObjectiveValue() { 390 double ret = 0.0; 391 for (Map.Entry<Long, Instructor> entry : iId2Instructor.entrySet()) { 392 Instructor ins = entry.getValue(); 393 ret += Math.abs(ins.getFinalValue() - iInstrMeanFairValue); 394 } 395 return ret; 396 } 397 398 /** 399 * Fairness value based on pdev (pdev sec. part) of instructors 400 * @param instructors 401 * @return Objective value of instructors 402 */ 403 public double getObjectiveValue(Collection<InstructorConstraint> instructors) { 404 double ret = 0.0; 405 for (InstructorConstraint ic : instructors) { 406 Instructor ins = iId2Instructor.get(ic.getResourceId()); 407 if (ins != null) 408 ret += Math.abs(ins.getFinalValue() - iInstrMeanFairValue); 409 } 410 return ret; 411 } 412 413 /** 414 * fairness value with squared P and avg.P 415 * 416 * @return fairness value with squared P and avg.P 417 */ 418 419 public double getDiffAllInstrValueSquared() { 420 double ret = 0.0; 421 for (Map.Entry<Long, Instructor> entry : iId2Instructor.entrySet()) { 422 Instructor ins = entry.getValue(); 423 ret += Math.sqrt(Math.abs(ins.getFinalValue() * ins.getFinalValue() - iInstrMeanFairValue * iInstrMeanFairValue)); 424 } 425 return ret; 426 } 427 428 /** 429 * refresh of all instructors in iId2Instructor 430 * 431 */ 432 433 public void refreshInstructors() { 434 for (Map.Entry<Long, Instructor> entry : iId2Instructor.entrySet()) { 435 Instructor ins = entry.getValue(); 436 ins.refresh(); 437 } 438 } 439 440 /** 441 * Metod count and return time (and room) preferences in placement 442 * 443 * @param assignment 444 * @param placement 445 * @return time (and room) preferences in placement 446 */ 447 448 public double fairnessDouble(Assignment<Lecture, Placement> assignment, Placement placement) { 449 double critValue = 0.0; 450 // critValue += getModel().getCriterion(RoomPreferences.class).getWeightedValue(assignment,placement,null); 451 critValue += getModel().getCriterion(TimePreferences.class).getWeightedValue(assignment, placement, null); 452 return critValue; 453 } 454 455 /** 456 * Method for whole evaluation of fairness criteria 457 * 458 * @param assignment 459 * @return String[] with informations about solution [0-Avarage 460 * instructor penalty, 1-Sum of squared penalities, 2-Pmax, 461 * 3-Pdev, 4-Perror, 5-Pss, 6-Jain, 7-worst instructor fairness 462 * value,8-Instructors fairness value] 463 */ 464 465 public String[] testFairness(Assignment<Lecture, Placement> assignment) { 466 String[] dataForEval = new String[9]; 467 Collection<Lecture> assignedLectures = assignment.assignedVariables(); 468 refreshInstructors(); 469 for (Lecture lec : assignedLectures) { 470 if (lec.getInstructorConstraints() != null) { 471 List<InstructorConstraint> insConstraints = lec.getInstructorConstraints(); 472 double critValue = fairnessDouble(assignment, lec.getAssignment(assignment)); 473 for (InstructorConstraint ic : insConstraints) { 474 addInstructorValue(ic.getResourceId(), critValue); 475 } 476 } 477 } 478 countInstrMeanFairValue(); 479 dataForEval[8] = sDoubleFormat.format(getObjectiveValue()); 480 481 double[] instructorsValue = new double[iId2Instructor.values().size()]; 482 int counter = 0; 483 double sumOfSquaredPen = 0.0; 484 double min = 100000; 485 double max = -100000; 486 double sum = 0.0; 487 double pdevSecPart = 0.0; 488 double pssSecPart = 0.0; 489 490 for (Instructor s : iId2Instructor.values()) { 491 instructorsValue[counter] = s.getFinalValue(); 492 sumOfSquaredPen = sumOfSquaredPen + (s.getFinalValue() * s.getFinalValue()); 493 if (min > s.getFinalValue()) { 494 min = s.getFinalValue(); 495 } 496 if (max < s.getFinalValue()) { 497 max = s.getFinalValue(); 498 } 499 sum += s.getFinalValue(); 500 counter++; 501 } 502 Arrays.sort(instructorsValue); 503 504 for (double d : instructorsValue) { 505 pdevSecPart += Math.abs(d - sum / instructorsValue.length); 506 pssSecPart += d * d; 507 } 508 509 // Worst instructor penalty: 510 dataForEval[7] = sDoubleFormat.format(max); 511 // "Avarage instructor penalty: 512 dataForEval[0] = sDoubleFormat.format(sum / instructorsValue.length); 513 // Sum of squared penalities: 514 dataForEval[1] = sDoubleFormat.format(Math.sqrt(sumOfSquaredPen)); 515 // Fairness W1: 516 // Pmax 517 dataForEval[2] = sDoubleFormat.format(iBest - pdevSecPart * iWeight + (instructorsValue.length) * max); 518 // Pdev 519 dataForEval[3] = sDoubleFormat.format(iBest); 520 // PError 521 dataForEval[4] = sDoubleFormat.format(iBest - pdevSecPart * iWeight + sum + ((instructorsValue.length) * (max - min))); 522 // Pss: 523 dataForEval[5] = sDoubleFormat.format(Math.sqrt(((iBest - pdevSecPart * iWeight) * iBest - pdevSecPart * iWeight) + pssSecPart)); 524 525 if (sumOfSquaredPen != 0.0) { 526 // Jain's index: 527 dataForEval[6] = sDoubleFormat.format((sum * sum) / ((instructorsValue.length) * sumOfSquaredPen)); 528 } else { 529 dataForEval[6] = sDoubleFormat.format(1); 530 } 531 return dataForEval; 532 } 533 534 /** 535 * Class representing instructor 536 * 537 */ 538 public class Instructor { 539 private Long iId; 540 private double iValue = 0.0; 541 private double iBestValue = 0.0; 542 private int iNumOfClasses = 0; 543 544 // could be used to change how important instructors requiremets are 545 private double coef = 1; 546 547 /** 548 * Create instructor with ID(instructorId) 549 * @param instructorId instructor ID 550 */ 551 public Instructor(Long instructorId) { 552 iId = instructorId; 553 } 554 555 /** 556 * representation how well instructors requirements are met 557 * 558 * @return Instructor final value 559 */ 560 561 public double getFinalValue() { 562 if (iNumOfClasses == 0) return 0.0; 563 return ((iValue - iBestValue) / iNumOfClasses) * coef; 564 } 565 566 /** 567 * 568 * @return iId - instructor ID 569 */ 570 public Long getId() { 571 return iId; 572 } 573 574 /** 575 * 576 * @return iValue - instructor value 577 */ 578 public double getValue() { 579 return iValue; 580 } 581 582 /** 583 * Add value to instructor value 584 * @param value value that should be added to instructor value 585 */ 586 public void addValue(double value) { 587 iValue += value; 588 } 589 590 /** 591 * Subtract value from instructor value 592 * @param value value that should be subtracted from instructor value 593 */ 594 public void removeValue(double value) { 595 iValue -= value; 596 } 597 598 /** 599 * 600 * @return iBestValue - instructor best value 601 */ 602 public double getBestValue() { 603 return iBestValue; 604 } 605 606 /** 607 * Add value to instructor best value 608 * @param bestValue value that should be added to instructor best value 609 */ 610 public void addBestValue(double bestValue) { 611 iBestValue += bestValue; 612 } 613 614 /** 615 * 616 * @return iNumOfClasses - number of instructor classes 617 */ 618 public int getNumOfClasses() { 619 return iNumOfClasses; 620 } 621 622 /** 623 * Increase number of classes by 1 624 */ 625 public void incNumOfClasses() { 626 this.iNumOfClasses += 1; 627 } 628 629 /** 630 * Decrease number of instructor classes by 1 631 */ 632 public void decNumOfClasses() { 633 this.iNumOfClasses -= 1; 634 } 635 636 /** 637 * 638 * @return coef - coefficient of instructor 639 */ 640 public double getCoef() { 641 return coef; 642 } 643 644 /** 645 * Set instructor coefficient to double value 646 * @param coef coefficient of instructor 647 */ 648 public void setCoef(double coef) { 649 this.coef = coef; 650 } 651 652 /** 653 * Set instructor value and number of classes to 0 654 */ 655 public void refresh() { 656 iValue = 0.0; 657 iNumOfClasses = 0; 658 } 659 660 @Override 661 public int hashCode() { 662 return iId.hashCode(); 663 } 664 665 @Override 666 public boolean equals(Object obj) { 667 if (obj == null || !(obj instanceof Instructor)) return false; 668 return iId.equals(((Instructor) obj).iId); 669 } 670 } 671 } 672 673 @Override 674 public ValueContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 675 return new InstructorFairnessContext(assignment); 676 } 677}