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