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}