    001package net.sf.cpsolver.studentsct.weights;
    002
    003import java.text.DecimalFormat;
    004import java.util.ArrayList;
    005import java.util.BitSet;
    006import java.util.HashSet;
    007import java.util.Set;
    008
    009import net.sf.cpsolver.coursett.model.Placement;
    010import net.sf.cpsolver.coursett.model.RoomLocation;
    011import net.sf.cpsolver.coursett.model.TimeLocation;
    012import net.sf.cpsolver.ifs.solution.Solution;
    013import net.sf.cpsolver.ifs.util.DataProperties;
    014import net.sf.cpsolver.ifs.util.ToolBox;
    015import net.sf.cpsolver.studentsct.extension.DistanceConflict;
    016import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter;
    017import net.sf.cpsolver.studentsct.model.Assignment;
    018import net.sf.cpsolver.studentsct.model.Config;
    019import net.sf.cpsolver.studentsct.model.Course;
    020import net.sf.cpsolver.studentsct.model.CourseRequest;
    021import net.sf.cpsolver.studentsct.model.Enrollment;
    022import net.sf.cpsolver.studentsct.model.Offering;
    023import net.sf.cpsolver.studentsct.model.Request;
    024import net.sf.cpsolver.studentsct.model.Section;
    025import net.sf.cpsolver.studentsct.model.Student;
    026import net.sf.cpsolver.studentsct.model.Subpart;
    027
    028/**
    029 * New weighting model. It tries to obey the following principles:
    030 * <ul>
    031 *      <li> Total student weight is between zero and one (one means student got the best schedule)
    032 *      <li> Weight of the given priority course is higher than sum of the remaining weights the student can get
    033 *      <li> First alternative is better than the following course
    034 *      <li> Second alternative is better than the second following course
    035 *      <li> Distance conflicts are considered secondary (priorities should be maximized first)
    036 *      <li> If alternative sections are otherwise equal, use the better balanced one
    037 * </ul>
    038 *
    039 * @version StudentSct 1.2 (Student Sectioning)<br>
    040 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    041 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    042 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    043 * <br>
    044 *          This library is free software; you can redistribute it and/or modify
    045 *          it under the terms of the GNU Lesser General Public License as
    046 *          published by the Free Software Foundation; either version 3 of the
    047 *          License, or (at your option) any later version. <br>
    048 * <br>
    049 *          This library is distributed in the hope that it will be useful, but
    050 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    051 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    052 *          Lesser General Public License for more details. <br>
    053 * <br>
    054 *          You should have received a copy of the GNU Lesser General Public
    055 *          License along with this library; if not see
    056 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    057 */
    058
    059public class PriorityStudentWeights implements StudentWeights {
    060    protected double iPriorityFactor = 0.5010;
    061    protected double iFirstAlternativeFactor = 0.5010;
    062    protected double iSecondAlternativeFactor = 0.2510;
    063    protected double iDistanceConflict = 0.0100;
    064    protected double iTimeOverlapFactor = 0.5000;
    065    protected double iTimeOverlapMaxLimit = 0.5000;
    066    protected boolean iLeftoverSpread = false;
    067    protected double iBalancingFactor = 0.0050;
    068    protected double iAlternativeRequestFactor = 0.1260;
    069    protected double iProjectedStudentWeight = 0.0100;
    070
    071    public PriorityStudentWeights(DataProperties config) {
    072        iPriorityFactor = config.getPropertyDouble("StudentWeights.Priority", iPriorityFactor);
    073        iFirstAlternativeFactor = config.getPropertyDouble("StudentWeights.FirstAlternative", iFirstAlternativeFactor);
    074        iSecondAlternativeFactor = config.getPropertyDouble("StudentWeights.SecondAlternative", iSecondAlternativeFactor);
    075        iDistanceConflict = config.getPropertyDouble("StudentWeights.DistanceConflict", iDistanceConflict);
    076        iTimeOverlapFactor = config.getPropertyDouble("StudentWeights.TimeOverlapFactor", iTimeOverlapFactor);
    077        iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit);
    078        iLeftoverSpread = config.getPropertyBoolean("StudentWeights.LeftoverSpread", iLeftoverSpread);
    079        iBalancingFactor = config.getPropertyDouble("StudentWeights.BalancingFactor", iBalancingFactor);
    080        iAlternativeRequestFactor = config.getPropertyDouble("StudentWeights.AlternativeRequestFactor", iAlternativeRequestFactor);
    081        iProjectedStudentWeight = config.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight);
    082    }
    083
    084    public double getWeight(Request request) {
    085        if (request.getStudent().isDummy() && iProjectedStudentWeight >= 0.0) {
    086            double weight = iProjectedStudentWeight;
    087            if (request.isAlternative())
    088                weight *= iAlternativeRequestFactor;
    089            return weight;
    090        }
    091        double total = 10000.0;
    092        int nrReq = request.getStudent().nrRequests();
    093        double remain = (iLeftoverSpread ? Math.floor(10000.0 * Math.pow(iPriorityFactor, nrReq) / nrReq) : 0.0);
    094        for (int idx = 0; idx < request.getStudent().getRequests().size(); idx++) {
    095            Request r = request.getStudent().getRequests().get(idx);
    096            boolean last = (idx + 1 == request.getStudent().getRequests().size());
    097            boolean lastNotAlt = !r.isAlternative() && (last || request.getStudent().getRequests().get(1 + idx).isAlternative());
    098            double w = Math.ceil(iPriorityFactor * total) + remain;
    099            if (lastNotAlt || last) {
    100                w = total;
    101            } else {
    102                total -= w;
    103            }
    104            if (r.equals(request)) {
    105                return w / 10000.0;
    106            }
    107        }
    108        return 0.0;
    109    }
    110
    111    public double getCachedWeight(Request request) {
    112        Double w = (Double)request.getExtra();
    113        if (w == null) {
    114            w = getWeight(request);
    115            request.setExtra(w);
    116        }
    117        return w;
    118    }
    119
    120    @Override
    121    public double getBound(Request request) {
    122        return getCachedWeight(request);
    123    }
    124
    125    protected double round(double value) {
    126        return Math.ceil(10000.0 * value) / 10000.0;
    127    }
    128
    129    @Override
    130    public double getWeight(Enrollment enrollment) {
    131        double weight = getCachedWeight(enrollment.getRequest());
    132        switch (enrollment.getPriority()) {
    133            case 1: weight *= iFirstAlternativeFactor; break;
    134            case 2: weight *= iSecondAlternativeFactor; break;
    135        }
    136        if (enrollment.isCourseRequest() && iBalancingFactor != 0.0) {
    137            double configUsed = enrollment.getConfig().getEnrollmentWeight(enrollment.getRequest()) + enrollment.getRequest().getWeight();
    138            double disbalanced = 0;
    139            double total = 0;
    140            for (Section section: enrollment.getSections()) {
    141                Subpart subpart = section.getSubpart();
    142                if (subpart.getSections().size() <= 1) continue;
    143                double used = section.getEnrollmentWeight(enrollment.getRequest()) + enrollment.getRequest().getWeight();
    144                // sections have limits -> desired size is section limit x (total enrollment / total limit)
    145                // unlimited sections -> desired size is total enrollment / number of sections
    146                double desired = (subpart.getLimit() > 0
    147                        ? section.getLimit() * (configUsed / subpart.getLimit())
    148                        : configUsed / subpart.getSections().size());
    149                if (used > desired)
    150                    disbalanced += Math.min(enrollment.getRequest().getWeight(), used - desired) / enrollment.getRequest().getWeight();
    151                else
    152                    disbalanced -= Math.min(enrollment.getRequest().getWeight(), desired - used) / enrollment.getRequest().getWeight();
    153                total ++;
    154            }
    155            if (disbalanced > 0)
    156                weight *= (1.0 - disbalanced / total * iBalancingFactor);
    157        }
    158        return round(weight);
    159    }
    160
    161    @Override
    162    public double getDistanceConflictWeight(DistanceConflict.Conflict c) {
    163        if (c.getR1().getPriority() < c.getR2().getPriority()) {
    164            return round(getWeight(c.getE2()) * iDistanceConflict);
    165        } else {
    166            return round(getWeight(c.getE1()) * iDistanceConflict);
    167        }
    168    }
    169
    170    @Override
    171    public double getTimeOverlapConflictWeight(Enrollment e, TimeOverlapsCounter.Conflict c) {
    172        double toc = Math.min(iTimeOverlapMaxLimit * c.getShare() / e.getNrSlots(), iTimeOverlapMaxLimit);
    173        return round(getWeight(e) * toc);
    174    }
    175
    176    @Override
    177    public double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
    178        double base = getWeight(enrollment);
    179        double dc = 0.0;
    180        if (distanceConflicts != null) {
    181            for (DistanceConflict.Conflict c: distanceConflicts) {
    182                Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
    183                if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
    184                    dc += base * iDistanceConflict;
    185                else
    186                    dc += getWeight(other) * iDistanceConflict;
    187            }
    188        }
    189        double toc = 0.0;
    190        if (timeOverlappingConflicts != null) {
    191            for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
    192                toc += base * Math.min(iTimeOverlapFactor * c.getShare() / enrollment.getNrSlots(), iTimeOverlapMaxLimit);
    193                Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
    194                toc += getWeight(other) * Math.min(iTimeOverlapFactor * c.getShare() / other.getNrSlots(), iTimeOverlapMaxLimit);
    195            }
    196        }
    197        return round(base - dc - toc);
    198    }
    199
    200
    201    @Override
    202    public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) {
    203        return currentSolution.getBestInfo() == null || currentSolution.getModel().getTotalValue() < currentSolution.getBestValue();
    204    }
    205
    206    @Override
    207    public boolean isFreeTimeAllowOverlaps() {
    208        return false;
    209    }
    210
    211    /**
    212     * Test case -- run to see the weights for a few courses
    213     */
    214    public static void main(String[] args) {
    215        PriorityStudentWeights pw = new PriorityStudentWeights(new DataProperties());
    216        DecimalFormat df = new DecimalFormat("0.0000");
    217        Student s = new Student(0l);
    218        new CourseRequest(1l, 0, false, s, ToolBox.toList(
    219                new Course(1, "A", "1", new Offering(0, "A")),
    220                new Course(1, "A", "2", new Offering(0, "A")),
    221                new Course(1, "A", "3", new Offering(0, "A"))), false, null);
    222        new CourseRequest(2l, 1, false, s, ToolBox.toList(
    223                new Course(1, "B", "1", new Offering(0, "B")),
    224                new Course(1, "B", "2", new Offering(0, "B")),
    225                new Course(1, "B", "3", new Offering(0, "B"))), false, null);
    226        new CourseRequest(3l, 2, false, s, ToolBox.toList(
    227                new Course(1, "C", "1", new Offering(0, "C")),
    228                new Course(1, "C", "2", new Offering(0, "C")),
    229                new Course(1, "C", "3", new Offering(0, "C"))), false, null);
    230        new CourseRequest(4l, 3, false, s, ToolBox.toList(
    231                new Course(1, "D", "1", new Offering(0, "D")),
    232                new Course(1, "D", "2", new Offering(0, "D")),
    233                new Course(1, "D", "3", new Offering(0, "D"))), false, null);
    234        new CourseRequest(5l, 4, false, s, ToolBox.toList(
    235                new Course(1, "E", "1", new Offering(0, "E")),
    236                new Course(1, "E", "2", new Offering(0, "E")),
    237                new Course(1, "E", "3", new Offering(0, "E"))), false, null);
    238        new CourseRequest(6l, 5, true, s, ToolBox.toList(
    239                new Course(1, "F", "1", new Offering(0, "F")),
    240                new Course(1, "F", "2", new Offering(0, "F")),
    241                new Course(1, "F", "3", new Offering(0, "F"))), false, null);
    242        new CourseRequest(7l, 6, true, s, ToolBox.toList(
    243                new Course(1, "G", "1", new Offering(0, "G")),
    244                new Course(1, "G", "2", new Offering(0, "G")),
    245                new Course(1, "G", "3", new Offering(0, "G"))), false, null);
    246
    247        Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>());
    248        for (Request r: s.getRequests()) {
    249            CourseRequest cr = (CourseRequest)r;
    250            double[] w = new double[] {0.0, 0.0, 0.0};
    251            for (int i = 0; i < cr.getCourses().size(); i++) {
    252                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
    253                Set<Assignment> sections = new HashSet<Assignment>();
    254                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
    255                Enrollment e = new Enrollment(cr, i, cfg, sections);
    256                w[i] = pw.getWeight(e, null, null);
    257            }
    258            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
    259        }
    260
    261        System.out.println("With one distance conflict:");
    262        for (Request r: s.getRequests()) {
    263            CourseRequest cr = (CourseRequest)r;
    264            double[] w = new double[] {0.0, 0.0, 0.0};
    265            for (int i = 0; i < cr.getCourses().size(); i++) {
    266                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
    267                Set<Assignment> sections = new HashSet<Assignment>();
    268                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
    269                Enrollment e = new Enrollment(cr, i, cfg, sections);
    270                Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
    271                dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
    272                w[i] = pw.getWeight(e, dc, null);
    273            }
    274            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
    275        }
    276
    277        System.out.println("With two distance conflicts:");
    278        for (Request r: s.getRequests()) {
    279            CourseRequest cr = (CourseRequest)r;
    280            double[] w = new double[] {0.0, 0.0, 0.0};
    281            for (int i = 0; i < cr.getCourses().size(); i++) {
    282                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
    283                Set<Assignment> sections = new HashSet<Assignment>();
    284                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
    285                Enrollment e = new Enrollment(cr, i, cfg, sections);
    286                Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
    287                dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
    288                dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e,
    289                        new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)));
    290                w[i] = pw.getWeight(e, dc, null);
    291            }
    292            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
    293        }
    294
    295        System.out.println("With 25% time overlapping conflict:");
    296        for (Request r: s.getRequests()) {
    297            CourseRequest cr = (CourseRequest)r;
    298            double[] w = new double[] {0.0, 0.0, 0.0};
    299            for (int i = 0; i < cr.getCourses().size(); i++) {
    300                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
    301                Set<Assignment> sections = new HashSet<Assignment>();
    302                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
    303                Enrollment e = new Enrollment(cr, i, cfg, sections);
    304                Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>();
    305                toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next()));
    306                w[i] = pw.getWeight(e, null, toc);
    307            }
    308            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
    309        }
    310
    311        System.out.println("Disbalanced sections (by 2 / 10 students):");
    312        for (Request r: s.getRequests()) {
    313            CourseRequest cr = (CourseRequest)r;
    314            double[] w = new double[] {0.0, 0.0, 0.0};
    315            for (int i = 0; i < cr.getCourses().size(); i++) {
    316                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
    317                Set<Assignment> sections = new HashSet<Assignment>();
    318                Subpart x = new Subpart(0, "Lec", "Lec", cfg, null);
    319                Section a = new Section(0, 10, "x", x, p, null, null, null);
    320                new Section(1, 10, "y", x, p, null, null, null);
    321                sections.add(a);
    322                a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
    323                a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
    324                cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
    325                cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
    326                Enrollment e = new Enrollment(cr, i, cfg, sections);
    327                w[i] = pw.getWeight(e, null, null);
    328            }
    329            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
    330        }
    331    }
    332}