    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}