    001package org.cpsolver.studentsct.online.selection;
    002
    003import java.util.ArrayList;
    004import java.util.HashSet;
    005import java.util.Hashtable;
    006import java.util.List;
    007import java.util.Set;
    008
    009import org.cpsolver.coursett.model.TimeLocation;
    010import org.cpsolver.ifs.assignment.Assignment;
    011import org.cpsolver.studentsct.extension.DistanceConflict;
    012import org.cpsolver.studentsct.extension.StudentQuality;
    013import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
    014import org.cpsolver.studentsct.model.CourseRequest;
    015import org.cpsolver.studentsct.model.Enrollment;
    016import org.cpsolver.studentsct.model.FreeTimeRequest;
    017import org.cpsolver.studentsct.model.Request;
    018import org.cpsolver.studentsct.model.Section;
    019import org.cpsolver.studentsct.model.Student;
    020import org.cpsolver.studentsct.model.Subpart;
    021import org.cpsolver.studentsct.model.Unavailability;
    022import org.cpsolver.studentsct.online.OnlineSectioningModel;
    023import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionCriterion;
    024import org.cpsolver.studentsct.weights.StudentWeights;
    025
    026/**
    027* Multi-criteria selection criterion. This provides a lexicographical order of solutions using the
    028* following criteria:
    029* <ul>
    030* <li>best priority &amp; alternativity ignoring free time requests (a better solution has a higher priority course assigned or does not use alternative request if possible)
    031* <li>avoid or minimize course time overlaps
    032* <li>minimise use of over-expected classes (this prevents students of getting into classes that we know will be needed later in the process)
    033* <li>best priority &amp; alternativity including free time requests (this is to prevent students of gaming the system by adding free time requests)
    034* <li>maximise selection (preferred sections)
    035* <li>avoid or minimise time overlaps (for classes that are allowed to overlap and for free time requests)
    036* <li>avoid or minimise distance conflicts
    037* <li>avoid classes that have no time assignment (arranged hours)
    038* <li>balance sections
    039* <li>minimise class penalties (expressing how much a class is over-expected)
    040* </ul>
    041*
    042* @version StudentSct 1.3 (Student Sectioning)<br>
    043*          Copyright (C) 2014 Tomáš Müller<br>
    044*          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    045*          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    046* <br>
    047*          This library is free software; you can redistribute it and/or modify
    048*          it under the terms of the GNU Lesser General Public License as
    049*          published by the Free Software Foundation; either version 3 of the
    050*          License, or (at your option) any later version. <br>
    051* <br>
    052*          This library is distributed in the hope that it will be useful, but
    053*          WITHOUT ANY WARRANTY; without even the implied warranty of
    054*          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    055*          Lesser General Public License for more details. <br>
    056* <br>
    057*          You should have received a copy of the GNU Lesser General Public
    058*          License along with this library; if not see <a
    059*          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
    060*
    061*/
    062public class OnlineSectioningCriterion implements SelectionCriterion {
    063    private Hashtable<CourseRequest, Set<Section>> iPreferredSections = null;
    064    private List<TimeToAvoid> iTimesToAvoid = null;
    065    private OnlineSectioningModel iModel;
    066    private Student iStudent;
    067    protected double[] iQalityWeights;
    068
    069    /**
    070     * Constructor
    071     * @param student current student
    072     * @param model online student sectioning model
    073     * @param assignment current assignment
    074     * @param preferredSections preferred sections
    075     */
    076    public OnlineSectioningCriterion(Student student, OnlineSectioningModel model,
    077            Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) {
    078        iStudent = student;
    079        iModel = model;
    080        iPreferredSections = preferredSections;
    081        if (model.getProperties().getPropertyBoolean("OnlineStudentSectioning.TimesToAvoidHeuristics", true)) {
    082            iTimesToAvoid = new ArrayList<TimeToAvoid>();
    083            for (Request r : iStudent.getRequests()) {
    084                if (r instanceof CourseRequest) {
    085                    List<Enrollment> enrollments = ((CourseRequest) r).getAvaiableEnrollmentsSkipSameTime(assignment, false);
    086                    if (enrollments.size() <= 5) {
    087                        int penalty = (7 - enrollments.size()) * (r.isAlternative() ? 1 : 7 - enrollments.size());
    088                        for (Enrollment enrollment : enrollments)
    089                            for (Section section : enrollment.getSections())
    090                                if (section.getTime() != null)
    091                                    iTimesToAvoid.add(new TimeToAvoid(section.getTime(), penalty, r.getPriority()));
    092                    }
    093                } else if (r instanceof FreeTimeRequest) {
    094                    iTimesToAvoid.add(new TimeToAvoid(((FreeTimeRequest) r).getTime(), 1, Integer.MAX_VALUE));
    095                }
    096            }
    097            for (Unavailability unavailability: iStudent.getUnavailabilities())
    098                if (unavailability.getTime() != null)
    099                    iTimesToAvoid.add(new TimeToAvoid(unavailability.getTime(), 1, Integer.MAX_VALUE));
    100        }
    101        iQalityWeights = new double[StudentQuality.Type.values().length];
    102        for (StudentQuality.Type type: StudentQuality.Type.values()) {
    103            iQalityWeights[type.ordinal()] = model.getProperties().getPropertyDouble(type.getWeightName(), type.getWeightDefault());
    104        }
    105    }
    106
    107    protected OnlineSectioningModel getModel() {
    108        return iModel;
    109    }
    110
    111    protected Student getStudent() {
    112        return iStudent;
    113    }
    114
    115    protected Set<Section> getPreferredSections(Request request) {
    116        return iPreferredSections.get(request);
    117    }
    118
    119    protected List<TimeToAvoid> getTimesToAvoid() {
    120        return iTimesToAvoid;
    121    }
    122
    123    /**
    124     * Distance conflicts of idx-th assignment of the current schedule
    125     */
    126    public Set<DistanceConflict.Conflict> getDistanceConflicts(Enrollment[] assignment, int idx) {
    127        if (getModel().getDistanceConflict() == null || assignment[idx] == null)
    128            return null;
    129        Set<DistanceConflict.Conflict> dist = getModel().getDistanceConflict().conflicts(assignment[idx]);
    130        for (int x = 0; x < idx; x++)
    131            if (assignment[x] != null)
    132                dist.addAll(getModel().getDistanceConflict().conflicts(assignment[x], assignment[idx]));
    133        return dist;
    134    }
    135
    136    /**
    137     * Time overlapping conflicts of idx-th assignment of the current schedule
    138     */
    139    public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(Enrollment[] assignment, int idx) {
    140        if (getModel().getTimeOverlaps() == null || assignment[idx] == null)
    141            return null;
    142        Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>();
    143        for (int x = 0; x < idx; x++)
    144            if (assignment[x] != null) {
    145                overlaps.addAll(getModel().getTimeOverlaps().conflicts(assignment[x], assignment[idx]));
    146            } else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    147                overlaps.addAll(getModel().getTimeOverlaps().conflicts(
    148                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), assignment[idx]));
    149        overlaps.addAll(getModel().getTimeOverlaps().notAvailableTimeConflicts(assignment[idx]));
    150        return overlaps;
    151    }
    152
    153    public Set<StudentQuality.Conflict> getStudentQualityConflicts(Enrollment[] assignment, int idx) {
    154        if (getModel().getStudentQuality() == null || assignment[idx] == null)
    155            return null;
    156        Set<StudentQuality.Conflict> conflicts = new HashSet<StudentQuality.Conflict>();
    157        for (StudentQuality.Type t: StudentQuality.Type.values()) {
    158            for (int x = 0; x < idx; x++)
    159                if (assignment[x] != null)
    160                    conflicts.addAll(getModel().getStudentQuality().conflicts(t, assignment[x], assignment[idx]));
    161            conflicts.addAll(getModel().getStudentQuality().conflicts(t, assignment[idx]));
    162        }
    163        return conflicts;
    164    }
    165
    166    /**
    167     * Weight of an assignment. Unlike
    168     * {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this
    169     * side of distance conflicts and time overlaps.
    170     **/
    171    @Deprecated
    172    protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment,
    173            Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
    174        double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment);
    175        if (distanceConflicts != null)
    176            for (DistanceConflict.Conflict c : distanceConflicts) {
    177                Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
    178                if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
    179                    weight += getModel().getStudentWeights().getDistanceConflictWeight(assignment, c);
    180            }
    181        if (timeOverlappingConflicts != null)
    182            for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) {
    183                weight += getModel().getStudentWeights().getTimeOverlapConflictWeight(assignment, enrollment, c);
    184            }
    185        return enrollment.getRequest().getWeight() * weight;
    186    }
    187
    188    protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<StudentQuality.Conflict> conflicts) {
    189        double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment);
    190        if (conflicts != null)
    191            for (StudentQuality.Conflict c : conflicts) {
    192                weight += getModel().getStudentWeights().getStudentQualityConflictWeight(assignment, enrollment, c);
    193            }
    194        return enrollment.getRequest().getWeight() * weight;
    195    }
    196
    197    public Request getRequest(int index) {
    198        return (index < 0 || index >= getStudent().getRequests().size() ? null : getStudent().getRequests().get(index));
    199    }
    200
    201    public boolean isFreeTime(int index) {
    202        Request r = getRequest(index);
    203        return r != null && r instanceof FreeTimeRequest;
    204    }
    205
    206    @Override
    207    public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) {
    208        if (best == null)
    209            return -1;
    210
    211        // 0. best priority & alternativity ignoring free time requests
    212        boolean ft = false;
    213        boolean res = false;
    214        for (int idx = 0; idx < current.length; idx++) {
    215            if (isFreeTime(idx)) {
    216                ft = true;
    217                continue;
    218            }
    219            Request request = getRequest(idx);
    220            if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true;
    221            if (best[idx] != null && best[idx].getAssignments() != null) {
    222                if (current[idx] == null || current[idx].getSections() == null)
    223                    return 1; // higher priority request assigned
    224                if (best[idx].getTruePriority() < current[idx].getTruePriority())
    225                    return 1; // less alternative request assigned
    226                if (best[idx].getTruePriority() > current[idx].getTruePriority())
    227                    return -1; // less alternative request assigned
    228            } else {
    229                if (current[idx] != null && current[idx].getAssignments() != null)
    230                    return -1; // higher priority request assigned
    231            }
    232        }
    233
    234        // 0.1. allowed, but not available sections
    235        int bestNotAvailable = 0, currentNotAvailable = 0;
    236        for (int idx = 0; idx < current.length; idx++) {
    237            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
    238                for (Section section: best[idx].getSections()) {
    239                    if (section.getLimit() == 0)
    240                        bestNotAvailable ++;
    241                }
    242            }
    243            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
    244                for (Section section: current[idx].getSections()) {
    245                    if (section.getLimit() == 0)
    246                        currentNotAvailable ++;
    247                }
    248            }
    249        }
    250        if (bestNotAvailable > currentNotAvailable) return -1;
    251        if (bestNotAvailable < currentNotAvailable) return 1;
    252
    253        // 0.5. avoid course time overlaps & unavailabilities
    254        if (getModel().getStudentQuality() != null) {
    255            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    256            for (int idx = 0; idx < current.length; idx++) {
    257                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest) {
    258                    for (int x = 0; x < idx; x++) {
    259                        if (best[x] != null && best[x].getAssignments() != null && best[x].getRequest() instanceof CourseRequest)
    260                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
    261                    }
    262                }
    263                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest) {
    264                    for (int x = 0; x < idx; x++) {
    265                        if (current[x] != null && current[x].getAssignments() != null && current[x].getRequest() instanceof CourseRequest)
    266                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
    267                    }
    268                }
    269            }
    270            for (int idx = 0; idx < current.length; idx++) {
    271                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    272                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
    273                }
    274                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    275                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
    276                }
    277            }
    278            if (currentTimeOverlaps < bestTimeOverlaps)
    279                return -1;
    280            if (bestTimeOverlaps < currentTimeOverlaps)
    281                return 1;
    282        } else if (getModel().getTimeOverlaps() != null) {
    283            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    284            for (int idx = 0; idx < current.length; idx++) {
    285                if (best[idx] != null && best[idx].getAssignments() != null
    286                                && best[idx].getRequest() instanceof CourseRequest) {
    287                    for (int x = 0; x < idx; x++) {
    288                        if (best[x] != null && best[x].getAssignments() != null
    289                                        && best[x].getRequest() instanceof CourseRequest)
    290                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
    291                    }
    292                    for (int x = 0; x < idx; x++) {
    293                        if (current[x] != null && current[x].getAssignments() != null
    294                                        && current[x].getRequest() instanceof CourseRequest)
    295                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
    296                    }
    297                }
    298            }
    299            for (int idx = 0; idx < current.length; idx++) {
    300                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    301                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
    302                }
    303                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    304                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
    305                }
    306            }
    307            if (currentTimeOverlaps < bestTimeOverlaps)
    308                return -1;
    309            if (bestTimeOverlaps < currentTimeOverlaps)
    310                return 1;
    311        }
    312
    313        // 1. minimize number of penalties
    314        double bestPenalties = 0, currentPenalties = 0;
    315        for (int idx = 0; idx < current.length; idx++) {
    316            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    317                for (Section section : best[idx].getSections())
    318                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
    319                for (Section section : current[idx].getSections())
    320                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
    321            }
    322        }
    323        if (currentPenalties < bestPenalties)
    324            return -1;
    325        if (bestPenalties < currentPenalties)
    326            return 1;
    327
    328        // 2. best priority & alternativity including free time requests
    329        if (ft) {
    330            for (int idx = 0; idx < current.length; idx++) {
    331                if (best[idx] != null && best[idx].getAssignments() != null) {
    332                    if (current[idx] == null || current[idx].getSections() == null)
    333                        return 1; // higher priority request assigned
    334                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
    335                        return 1; // less alternative request assigned
    336                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
    337                        return -1; // less alternative request assigned
    338                } else {
    339                    if (current[idx] != null && current[idx].getAssignments() != null)
    340                        return -1; // higher priority request assigned
    341                }
    342            }
    343        }
    344
    345        // 3. maximize selection
    346        int bestSelected = 0, currentSelected = 0;
    347        for (int idx = 0; idx < current.length; idx++) {
    348            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    349                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
    350                if (preferred != null && !preferred.isEmpty()) {
    351                    for (Section section : best[idx].getSections())
    352                        if (preferred.contains(section))
    353                            bestSelected++;
    354                    for (Section section : current[idx].getSections())
    355                        if (preferred.contains(section))
    356                            currentSelected++;
    357                }
    358            }
    359        }
    360        if (currentSelected > bestSelected)
    361            return -1;
    362        if (bestSelected > currentSelected)
    363            return 1;
    364
    365        // 3.5 maximize preferences
    366        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
    367        double bestSelectedSections = 0, currentSelectedSections = 0;
    368        for (int idx = 0; idx < current.length; idx++) {
    369            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    370                bestSelectedSections += best[idx].percentSelectedSameSection();
    371                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
    372            }
    373            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    374                currentSelectedSections += current[idx].percentSelectedSameSection();
    375                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
    376            }
    377        }
    378        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1;
    379        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1;
    380
    381        // 3.9 maximize selection with penalization for not followed reservations
    382        if (res) {
    383            for (int idx = 0; idx < current.length; idx++) {
    384                if (best[idx] != null && best[idx].getAssignments() != null) {
    385                    if (current[idx] == null || current[idx].getSections() == null)
    386                        return 1; // higher priority request assigned
    387                    if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority())
    388                        return 1; // less alternative request assigned
    389                    if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority())
    390                        return -1; // less alternative request assigned
    391                } else {
    392                    if (current[idx] != null && current[idx].getAssignments() != null)
    393                        return -1; // higher priority request assigned
    394                }
    395            }
    396        }
    397
    398        // 3.95 avoid past sections
    399        double bestPast = 0.0, currentPast = 0.0;
    400        for (int idx = 0; idx < current.length; idx++) {
    401            if (best[idx] != null && best[idx].getAssignments() != null) {
    402                for (Section section : best[idx].getSections()) {
    403                    if (section.isPast())
    404                        bestPast += 1.0 / best[idx].getSections().size();
    405                }
    406            }
    407            if (current[idx] != null && current[idx].getAssignments() != null) {
    408                for (Section section : current[idx].getSections()) {
    409                    if (section.isPast())
    410                        currentPast += 1.0 / current[idx].getSections().size();
    411                }
    412            }
    413        }
    414        if (Math.abs(currentPast - bestPast) > 0.0001) {
    415            if (currentPast < bestPast)
    416                return -1;
    417            if (bestPast < currentPast)
    418                return 1;
    419        }
    420
    421        // 4-5. student quality
    422        if (getModel().getStudentQuality() != null) {
    423            double bestQuality = 0, currentQuality = 0;
    424            for (StudentQuality.Type type: StudentQuality.Type.values()) {
    425                for (int idx = 0; idx < current.length; idx++) {
    426                    if (best[idx] != null && best[idx].getAssignments() != null) {
    427                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
    428                        for (int x = 0; x < idx; x++) {
    429                            if (best[x] != null && best[x].getAssignments() != null)
    430                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
    431                        }
    432                    }
    433                    if (current[idx] != null && current[idx].getAssignments() != null) {
    434                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
    435                        for (int x = 0; x < idx; x++) {
    436                            if (current[x] != null && current[x].getAssignments() != null)
    437                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
    438                        }
    439                    }
    440                }
    441            }
    442            if (currentQuality < bestQuality)
    443                return -1;
    444            if (bestQuality < currentQuality)
    445                return 1;
    446        } else {
    447            // 4. avoid time overlaps
    448            if (getModel().getTimeOverlaps() != null) {
    449                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    450                for (int idx = 0; idx < current.length; idx++) {
    451                    if (best[idx] != null && best[idx].getAssignments() != null) {
    452                        for (int x = 0; x < idx; x++) {
    453                            if (best[x] != null && best[x].getAssignments() != null)
    454                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
    455                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    456                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), best[idx]);
    457                        }
    458                        for (int x = 0; x < idx; x++) {
    459                            if (current[x] != null && current[x].getAssignments() != null)
    460                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
    461                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    462                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), current[idx]);
    463                        }
    464                    }
    465                }
    466                for (int idx = 0; idx < current.length; idx++) {
    467                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    468                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
    469                    }
    470                    if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    471                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
    472                    }
    473                }
    474                if (currentTimeOverlaps < bestTimeOverlaps)
    475                    return -1;
    476                if (bestTimeOverlaps < currentTimeOverlaps)
    477                    return 1;
    478            }
    479
    480            // 5. avoid distance conflicts
    481            if (getModel().getDistanceConflict() != null) {
    482                int bestDistanceConf = 0, currentDistanceConf = 0;
    483                for (int idx = 0; idx < current.length; idx++) {
    484                    if (best[idx] != null && best[idx].getAssignments() != null) {
    485                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
    486                        for (int x = 0; x < idx; x++) {
    487                            if (best[x] != null && best[x].getAssignments() != null)
    488                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
    489                        }
    490                    }
    491                    if (current[idx] != null && current[idx].getAssignments() != null) {
    492                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
    493                        for (int x = 0; x < idx; x++) {
    494                            if (current[x] != null && current[x].getAssignments() != null)
    495                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]);
    496                        }
    497                    }
    498                }
    499                if (currentDistanceConf < bestDistanceConf)
    500                    return -1;
    501                if (bestDistanceConf < currentDistanceConf)
    502                    return 1;
    503            }
    504        }
    505
    506        // 6. avoid no-time and online sections (no-time first, online second)
    507        int bestNoTime = 0, currentNoTime = 0;
    508        int bestOnline = 0, currentOnline = 0;
    509        for (int idx = 0; idx < current.length; idx++) {
    510            if (best[idx] != null && best[idx].getAssignments() != null) {
    511                for (Section section : best[idx].getSections()) {
    512                    if (!section.hasTime())
    513                        bestNoTime++;
    514                    if (section.isOnline())
    515                        bestOnline++;
    516                }
    517                for (Section section : current[idx].getSections()) {
    518                    if (!section.hasTime())
    519                        currentNoTime++;
    520                    if (section.isOnline())
    521                        currentOnline++;
    522                }
    523            }
    524        }
    525        if (currentNoTime < bestNoTime)
    526            return -1;
    527        if (bestNoTime < currentNoTime)
    528            return 1;
    529        if (currentOnline < bestOnline)
    530            return -1;
    531        if (bestOnline < currentOnline)
    532            return 1;
    533
    534        // 7. balance sections
    535        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
    536        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
    537        for (int idx = 0; idx < current.length; idx++) {
    538            if (best[idx] != null && best[idx].getAssignments() != null) {
    539                for (Section section : best[idx].getSections()) {
    540                    Subpart subpart = section.getSubpart();
    541                    // skip unlimited and single section subparts
    542                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    543                        continue;
    544                    // average size
    545                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    546                    // section is below average
    547                    if (section.getLimit() < averageSize)
    548                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    549                    bestAltSectionsWithLimit++;
    550                }
    551                for (Section section : current[idx].getSections()) {
    552                    Subpart subpart = section.getSubpart();
    553                    // skip unlimited and single section subparts
    554                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    555                        continue;
    556                    // average size
    557                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    558                    // section is below average
    559                    if (section.getLimit() < averageSize)
    560                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    561                    currentAltSectionsWithLimit++;
    562                }
    563            }
    564        }
    565        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
    566                : 0.0);
    567        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
    568                / currentAltSectionsWithLimit : 0.0);
    569        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
    570            return -1;
    571        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
    572            return 1;
    573
    574        // 8. average penalty sections
    575        double bestPenalty = 0.0, currentPenalty = 0.0;
    576        for (int idx = 0; idx < current.length; idx++) {
    577            if (best[idx] != null && best[idx].getAssignments() != null) {
    578                for (Section section : best[idx].getSections())
    579                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
    580                for (Section section : current[idx].getSections())
    581                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
    582            }
    583        }
    584        if (currentPenalty < bestPenalty)
    585            return -1;
    586        if (bestPenalty < currentPenalty)
    587            return 1;
    588
    589        return 0;
    590    }
    591
    592    @Override
    593    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
    594            Enrollment[] best) {
    595        // 0. best priority & alternativity ignoring free time requests
    596        int alt = 0;
    597        boolean ft = false;
    598        boolean res = false;
    599        for (int idx = 0; idx < current.length; idx++) {
    600            if (isFreeTime(idx)) {
    601                ft = true;
    602                continue;
    603            }
    604            Request request = getRequest(idx);
    605            if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true;
    606            if (idx < maxIdx) {
    607                if (best[idx] != null) {
    608                    if (current[idx] == null)
    609                        return false; // higher priority request assigned
    610                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
    611                        return false; // less alternative request assigned
    612                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
    613                        return true; // less alternative request assigned
    614                    if (request.isAlternative())
    615                        alt--;
    616                } else {
    617                    if (current[idx] != null)
    618                        return true; // higher priority request assigned
    619                    if (!request.isAlternative())
    620                        alt++;
    621                }
    622            } else {
    623                if (best[idx] != null) {
    624                    if (best[idx].getTruePriority() > 0)
    625                        return true; // alternativity can be improved
    626                } else {
    627                    if (!request.isAlternative() || alt > 0)
    628                        return true; // priority can be improved
    629                }
    630            }
    631        }
    632
    633        // 0.1. allowed, but not available sections
    634        int notAvailable = 0;
    635        for (int idx = 0; idx < current.length; idx++) {
    636            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
    637                for (Section section: best[idx].getSections()) {
    638                    if (section.getLimit() == 0)
    639                        notAvailable ++;
    640                }
    641            }
    642            if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
    643                for (Section section: current[idx].getSections()) {
    644                    if (section.getLimit() == 0)
    645                        notAvailable --;
    646                }
    647            }
    648        }
    649        if (notAvailable > 0) {
    650            return true;
    651        }
    652
    653        // 0.5. avoid course time overlaps & unavailability overlaps
    654        if (getModel().getStudentQuality() != null) {
    655            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    656            for (int idx = 0; idx < current.length; idx++) {
    657                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
    658                    for (int x = 0; x < idx; x++) {
    659                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
    660                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
    661                    }
    662                }
    663                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
    664                    for (int x = 0; x < idx; x++) {
    665                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
    666                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
    667                    }
    668                }
    669            }
    670            for (int idx = 0; idx < current.length; idx++) {
    671                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    672                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
    673                }
    674                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    675                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
    676                }
    677            }
    678            if (currentTimeOverlaps < bestTimeOverlaps)
    679                return true;
    680            if (bestTimeOverlaps < currentTimeOverlaps)
    681                return false;
    682        } else if (getModel().getTimeOverlaps() != null) {
    683            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    684            for (int idx = 0; idx < current.length; idx++) {
    685                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
    686                    for (int x = 0; x < idx; x++) {
    687                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
    688                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
    689                    }
    690                }
    691                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
    692                    for (int x = 0; x < idx; x++) {
    693                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
    694                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
    695                    }
    696                }
    697            }
    698            for (int idx = 0; idx < current.length; idx++) {
    699                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    700                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
    701                }
    702                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    703                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
    704                }
    705            }
    706            if (currentTimeOverlaps < bestTimeOverlaps)
    707                return true;
    708            if (bestTimeOverlaps < currentTimeOverlaps)
    709                return false;
    710        }
    711
    712        // 1. maximize number of penalties
    713        double bestPenalties = 0, currentPenalties = 0;
    714        for (int idx = 0; idx < current.length; idx++) {
    715            if (best[idx] != null) {
    716                for (Section section : best[idx].getSections())
    717                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
    718            }
    719            if (current[idx] != null && idx < maxIdx) {
    720                for (Section section : current[idx].getSections())
    721                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
    722            }
    723        }
    724        if (currentPenalties < bestPenalties)
    725            return true;
    726        if (bestPenalties < currentPenalties)
    727            return false;
    728
    729        // 2. best priority & alternativity including free times
    730        if (ft) {
    731            alt = 0;
    732            for (int idx = 0; idx < current.length; idx++) {
    733                Request request = getStudent().getRequests().get(idx);
    734                if (idx < maxIdx) {
    735                    if (best[idx] != null) {
    736                        if (current[idx] == null)
    737                            return false; // higher priority request assigned
    738                        if (best[idx].getTruePriority() < current[idx].getTruePriority())
    739                            return false; // less alternative request assigned
    740                        if (best[idx].getTruePriority() > current[idx].getTruePriority())
    741                            return true; // less alternative request assigned
    742                        if (request.isAlternative())
    743                            alt--;
    744                    } else {
    745                        if (current[idx] != null)
    746                            return true; // higher priority request assigned
    747                        if (request instanceof CourseRequest && !request.isAlternative())
    748                            alt++;
    749                    }
    750                } else {
    751                    if (best[idx] != null) {
    752                        if (best[idx].getTruePriority() > 0)
    753                            return true; // alternativity can be improved
    754                    } else {
    755                        if (!request.isAlternative() || alt > 0)
    756                            return true; // priority can be improved
    757                    }
    758                }
    759            }
    760        }
    761
    762        // 3. maximize selection
    763        int bestSelected = 0, currentSelected = 0;
    764        for (int idx = 0; idx < current.length; idx++) {
    765            if (best[idx] != null && best[idx].isCourseRequest()) {
    766                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
    767                if (preferred != null && !preferred.isEmpty()) {
    768                    for (Section section : best[idx].getSections())
    769                        if (preferred.contains(section)) {
    770                            if (idx < maxIdx)
    771                                bestSelected++;
    772                        } else if (idx >= maxIdx)
    773                            bestSelected--;
    774                }
    775            }
    776            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
    777                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
    778                if (preferred != null && !preferred.isEmpty()) {
    779                    for (Section section : current[idx].getSections())
    780                        if (preferred.contains(section))
    781                            currentSelected++;
    782                }
    783            }
    784        }
    785        if (currentSelected > bestSelected)
    786            return true;
    787        if (bestSelected > currentSelected)
    788            return false;
    789
    790        // 3.5 maximize preferences
    791        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
    792        double bestSelectedSections = 0, currentSelectedSections = 0;
    793        for (int idx = 0; idx < current.length; idx++) {
    794            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    795                bestSelectedSections += best[idx].percentSelectedSameSection();
    796                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
    797                if (idx >= maxIdx) {
    798                    bestSelectedSections -= 1.0;
    799                    bestSelectedConfigs -= 1.0;
    800                }
    801            }
    802            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    803                currentSelectedSections += current[idx].percentSelectedSameSection();
    804                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
    805            }
    806        }
    807        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
    808        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
    809
    810        // 3.9 maximize selection with penalization for not followed reservations
    811        if (res) {
    812            alt = 0;
    813            for (int idx = 0; idx < current.length; idx++) {
    814                Request request = getStudent().getRequests().get(idx);
    815                if (idx < maxIdx) {
    816                    if (best[idx] != null) {
    817                        if (current[idx] == null)
    818                            return false; // higher priority request assigned
    819                        if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority())
    820                            return false; // less alternative request assigned
    821                        if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority())
    822                            return true; // less alternative request assigned
    823                        if (request.isAlternative())
    824                            alt--;
    825                    } else {
    826                        if (current[idx] != null)
    827                            return true; // higher priority request assigned
    828                        if (request instanceof CourseRequest && !request.isAlternative())
    829                            alt++;
    830                    }
    831                } else {
    832                    if (best[idx] != null) {
    833                        if (best[idx].getTruePriority() > 0)
    834                            return true; // alternativity can be improved
    835                    } else {
    836                        if (!request.isAlternative() || alt > 0)
    837                            return true; // priority can be improved
    838                    }
    839                }
    840            }
    841        }
    842
    843        // 3.95 avoid past sections
    844        double bestPast = 0.0, currentPast = 0.0;
    845        for (int idx = 0; idx < current.length; idx++) {
    846            if (best[idx] != null && best[idx].getAssignments() != null) {
    847                for (Section section : best[idx].getSections()) {
    848                    if (section.isPast())
    849                        bestPast += 1.0 / best[idx].getSections().size();
    850                }
    851            }
    852            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null) {
    853                for (Section section : current[idx].getSections()) {
    854                    if (section.isPast())
    855                        currentPast += 1.0 / current[idx].getSections().size();
    856                }
    857            }
    858        }
    859        if (Math.abs(currentPast - bestPast) > 0.0001) {
    860            if (currentPast < bestPast)
    861                return true;
    862            if (bestPast < currentPast)
    863                return false;
    864        }
    865
    866        // 4-5. student quality
    867        if (getModel().getStudentQuality() != null) {
    868            double bestQuality = 0, currentQuality = 0;
    869            for (StudentQuality.Type type: StudentQuality.Type.values()) {
    870                for (int idx = 0; idx < current.length; idx++) {
    871                    if (best[idx] != null) {
    872                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
    873                        for (int x = 0; x < idx; x++) {
    874                            if (best[x] != null)
    875                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
    876                        }
    877                    }
    878                    if (current[idx] != null && idx < maxIdx) {
    879                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
    880                        for (int x = 0; x < idx; x++) {
    881                            if (current[x] != null)
    882                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
    883                        }
    884                    }
    885                }
    886            }
    887            if (currentQuality < bestQuality)
    888                return true;
    889            if (bestQuality < currentQuality)
    890                return false;
    891        } else {
    892            // 4. avoid time overlaps
    893            if (getModel().getTimeOverlaps() != null) {
    894                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    895                for (int idx = 0; idx < current.length; idx++) {
    896                    if (best[idx] != null) {
    897                        for (int x = 0; x < idx; x++) {
    898                            if (best[x] != null)
    899                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
    900                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    901                                bestTimeOverlaps += getModel().getTimeOverlaps()
    902                                        .nrConflicts(
    903                                                ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
    904                                                best[idx]);
    905                        }
    906                    }
    907                    if (current[idx] != null && idx < maxIdx) {
    908                        for (int x = 0; x < idx; x++) {
    909                            if (current[x] != null)
    910                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
    911                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    912                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
    913                                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
    914                                        current[idx]);
    915                        }
    916                    }
    917                }
    918                for (int idx = 0; idx < current.length; idx++) {
    919                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    920                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
    921                    }
    922                    if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    923                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
    924                    }
    925                }
    926                if (currentTimeOverlaps < bestTimeOverlaps)
    927                    return true;
    928                if (bestTimeOverlaps < currentTimeOverlaps)
    929                    return false;
    930            }
    931
    932            // 5. avoid distance conflicts
    933            if (getModel().getDistanceConflict() != null) {
    934                int bestDistanceConf = 0, currentDistanceConf = 0;
    935                for (int idx = 0; idx < current.length; idx++) {
    936                    if (best[idx] != null) {
    937                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
    938                        for (int x = 0; x < idx; x++) {
    939                            if (best[x] != null)
    940                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
    941                        }
    942                    }
    943                    if (current[idx] != null && idx < maxIdx) {
    944                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
    945                        for (int x = 0; x < idx; x++) {
    946                            if (current[x] != null)
    947                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
    948                                        current[idx]);
    949                        }
    950                    }
    951                }
    952                if (currentDistanceConf < bestDistanceConf)
    953                    return true;
    954                if (bestDistanceConf < currentDistanceConf)
    955                    return false;
    956            }
    957        }
    958
    959        // 6. avoid no-time and online sections (no-time first, online second)
    960        int bestNoTime = 0, currentNoTime = 0;
    961        int bestOnline = 0, currentOnline = 0;
    962        for (int idx = 0; idx < current.length; idx++) {
    963            if (best[idx] != null) {
    964                for (Section section : best[idx].getSections()) {
    965                    if (!section.hasTime())
    966                        bestNoTime++;
    967                    if (section.isOnline())
    968                        bestOnline++;
    969                }
    970            }
    971            if (current[idx] != null && idx < maxIdx) {
    972                for (Section section : current[idx].getSections()) {
    973                    if (!section.hasTime())
    974                        currentNoTime++;
    975                    if (section.isOnline())
    976                        currentOnline++;
    977                }
    978            }
    979        }
    980        if (currentNoTime < bestNoTime)
    981            return true;
    982        if (bestNoTime < currentNoTime)
    983            return false;
    984        if (currentOnline < bestOnline)
    985            return true;
    986        if (bestOnline < currentOnline)
    987            return false;
    988
    989        // 7. balance sections
    990        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
    991        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
    992        for (int idx = 0; idx < current.length; idx++) {
    993            if (best[idx] != null) {
    994                for (Section section : best[idx].getSections()) {
    995                    Subpart subpart = section.getSubpart();
    996                    // skip unlimited and single section subparts
    997                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    998                        continue;
    999                    // average size
    1000                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    1001                    // section is below average
    1002                    if (section.getLimit() < averageSize)
    1003                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    1004                    bestAltSectionsWithLimit++;
    1005                }
    1006            }
    1007            if (current[idx] != null && idx < maxIdx) {
    1008                for (Section section : current[idx].getSections()) {
    1009                    Subpart subpart = section.getSubpart();
    1010                    // skip unlimited and single section subparts
    1011                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    1012                        continue;
    1013                    // average size
    1014                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    1015                    // section is below average
    1016                    if (section.getLimit() < averageSize)
    1017                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    1018                    currentAltSectionsWithLimit++;
    1019                }
    1020            }
    1021        }
    1022        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
    1023                : 0.0);
    1024        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
    1025                / currentAltSectionsWithLimit : 0.0);
    1026        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
    1027            return true;
    1028        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
    1029            return false;
    1030
    1031        // 8. average penalty sections
    1032        double bestPenalty = 0.0, currentPenalty = 0.0;
    1033        for (int idx = 0; idx < current.length; idx++) {
    1034            if (best[idx] != null) {
    1035                for (Section section : best[idx].getSections())
    1036                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
    1037                if (idx >= maxIdx && best[idx].isCourseRequest())
    1038                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
    1039            }
    1040            if (current[idx] != null && idx < maxIdx) {
    1041                for (Section section : current[idx].getSections())
    1042                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
    1043            }
    1044        }
    1045        if (currentPenalty < bestPenalty)
    1046            return true;
    1047        if (bestPenalty < currentPenalty)
    1048            return false;
    1049
    1050        return true;
    1051    }
    1052
    1053    @Override
    1054    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
    1055        if (enrollemnts == null)
    1056            return 0.0;
    1057        double value = 0.0;
    1058        for (int idx = 0; idx < enrollemnts.length; idx++) {
    1059            if (enrollemnts[idx] != null)
    1060                if (getModel().getStudentQuality() != null) {
    1061                    value += getWeight(assignment, enrollemnts[idx], getStudentQualityConflicts(enrollemnts, idx));
    1062                } else {
    1063                    value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), getTimeOverlappingConflicts(enrollemnts, idx));
    1064                }
    1065        }
    1066        return value;
    1067    }
    1068
    1069    @Override
    1070    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
    1071        // 1. alternativity
    1072        if (e1.getTruePriority() < e2.getTruePriority())
    1073            return -1;
    1074        if (e1.getTruePriority() > e2.getTruePriority())
    1075            return 1;
    1076
    1077        // 1.5 not available sections
    1078        int na1 = 0, na2 = 0;
    1079        for (Section section: e1.getSections())
    1080            if (section.getLimit() == 0) na1++;
    1081        for (Section section: e2.getSections())
    1082            if (section.getLimit() == 0) na2++;
    1083        if (na1 < na2) return -1;
    1084        if (na1 > na2) return 1;
    1085
    1086        // 2. maximize number of penalties
    1087        double p1 = 0, p2 = 0;
    1088        for (Section section : e1.getSections())
    1089            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
    1090        for (Section section : e2.getSections())
    1091            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
    1092        if (p1 < p2)
    1093            return -1;
    1094        if (p2 < p1)
    1095            return 1;
    1096
    1097        // 3. maximize selection
    1098        if (e1.isCourseRequest()) {
    1099            Set<Section> preferred = getPreferredSections(e1.getRequest());
    1100            if (preferred != null && !preferred.isEmpty()) {
    1101                int s1 = 0, s2 = 0;
    1102                for (Section section : e1.getSections())
    1103                    if (preferred.contains(section))
    1104                        s1++;
    1105                for (Section section : e2.getSections())
    1106                    if (preferred.contains(section))
    1107                        s2++;
    1108                if (s2 > s1)
    1109                    return -1;
    1110                if (s1 > s2)
    1111                    return 1;
    1112            }
    1113        }
    1114
    1115        // 3.5 maximize preferences
    1116        if (e1.isCourseRequest()) {
    1117            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
    1118            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
    1119            if (s1 > s2) return -1;
    1120            if (s2 > s1) return 1;
    1121        }
    1122
    1123        // 3.9 maximize selection with penalization for not followed reservations
    1124        if (e1.getAdjustedPriority() < e2.getAdjustedPriority())
    1125            return -1;
    1126        if (e1.getAdjustedPriority() > e2.getAdjustedPriority())
    1127            return 1;
    1128
    1129        // 3.95 avoid past sections
    1130        double w1 = 0, w2 = 0;
    1131        for (Section section : e1.getSections()) {
    1132            if (section.isPast())
    1133                w1 += 1.0 / e1.getSections().size();
    1134        }
    1135        for (Section section : e2.getSections()) {
    1136            if (section.isPast())
    1137                w2 += 1.0 / e2.getSections().size();
    1138        }
    1139        if (Math.abs(w1 - w2) > 0.0001) {
    1140            if (w1 < w2)
    1141                return -1;
    1142            if (w2 < w1)
    1143                return 1;
    1144        }
    1145
    1146        // 4. avoid time overlaps
    1147        if (getTimesToAvoid() == null) {
    1148            if (getModel().getStudentQuality() != null) {
    1149                int o1 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e1) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e1);
    1150                int o2 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e2) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e2);
    1151                if (o1 < o2)
    1152                    return -1;
    1153                if (o2 < o1)
    1154                    return 1;
    1155            } else if (getModel().getTimeOverlaps() != null) {
    1156                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1);
    1157                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2);
    1158                if (o1 < o2)
    1159                    return -1;
    1160                if (o2 < o1)
    1161                    return 1;
    1162            }
    1163        } else {
    1164            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
    1165                double o1 = 0.0, o2 = 0.0;
    1166                for (Section s : e1.getSections()) {
    1167                    if (s.getTime() != null)
    1168                        for (TimeToAvoid avoid : getTimesToAvoid()) {
    1169                            if (avoid.priority() > e1.getRequest().getPriority())
    1170                                o1 += avoid.overlap(s.getTime());
    1171                        }
    1172                }
    1173                for (Section s : e2.getSections()) {
    1174                    if (s.getTime() != null)
    1175                        for (TimeToAvoid avoid : getTimesToAvoid()) {
    1176                            if (avoid.priority() > e2.getRequest().getPriority())
    1177                                o2 += avoid.overlap(s.getTime());
    1178                        }
    1179                }
    1180                if (o1 < o2)
    1181                    return -1;
    1182                if (o2 < o1)
    1183                    return 1;
    1184            }
    1185        }
    1186
    1187        // 5. avoid distance conflicts
    1188        if (getModel().getDistanceConflict() != null) {
    1189            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
    1190            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
    1191            if (c1 < c2)
    1192                return -1;
    1193            if (c2 < c1)
    1194                return 1;
    1195        }
    1196
    1197        // 6. avoid no-time and online sections (no-time first, online second)
    1198        int n1 = 0, n2 = 0;
    1199        int o1 = 0, o2 = 0;
    1200        for (Section section : e1.getSections()) {
    1201            if (!section.hasTime())
    1202                n1++;
    1203            if (section.isOnline())
    1204                o1++;
    1205        }
    1206        for (Section section : e2.getSections()) {
    1207            if (!section.hasTime())
    1208                n2++;
    1209            if (section.isOnline())
    1210                o2++;
    1211        }
    1212        if (n1 < n2)
    1213            return -1;
    1214        if (n2 < n1)
    1215            return 1;
    1216        if (o1 < o2)
    1217            return -1;
    1218        if (o2 < o1)
    1219            return 1;
    1220
    1221        // 7. balance sections
    1222        double u1 = 0.0, u2 = 0.0;
    1223        int a1 = 0, a2 = 0;
    1224        for (Section section : e1.getSections()) {
    1225            Subpart subpart = section.getSubpart();
    1226            // skip unlimited and single section subparts
    1227            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    1228                continue;
    1229            // average size
    1230            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    1231            // section is below average
    1232            if (section.getLimit() < averageSize)
    1233                u1 += (averageSize - section.getLimit()) / averageSize;
    1234            a1++;
    1235        }
    1236        for (Section section : e2.getSections()) {
    1237            Subpart subpart = section.getSubpart();
    1238            // skip unlimited and single section subparts
    1239            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    1240                continue;
    1241            // average size
    1242            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    1243            // section is below average
    1244            if (section.getLimit() < averageSize)
    1245                u2 += (averageSize - section.getLimit()) / averageSize;
    1246            a2++;
    1247        }
    1248        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
    1249        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
    1250        if (f1 < f2)
    1251            return -1;
    1252        if (f2 < f1)
    1253            return 1;
    1254
    1255        // 8. average penalty sections
    1256        double x1 = 0.0, x2 = 0.0;
    1257        for (Section section : e1.getSections())
    1258            x1 += section.getPenalty() / e1.getSections().size();
    1259        for (Section section : e2.getSections())
    1260            x2 += section.getPenalty() / e2.getSections().size();
    1261        if (x1 < x2)
    1262            return -1;
    1263        if (x2 < x1)
    1264            return 1;
    1265
    1266        return 0;
    1267    }
    1268
    1269    /**
    1270     * Time to be avoided.
    1271     */
    1272    public static class TimeToAvoid {
    1273        private TimeLocation iTime;
    1274        private double iPenalty;
    1275        private int iPriority;
    1276
    1277        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
    1278            iTime = time;
    1279            iPenalty = penalty;
    1280            iPriority = priority;
    1281        }
    1282
    1283        public int priority() {
    1284            return iPriority;
    1285        }
    1286
    1287        public double overlap(TimeLocation time) {
    1288            if (time.hasIntersection(iTime)) {
    1289                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedHours(iTime))
    1290                        / (iTime.getNrMeetings() * iTime.getLength());
    1291            } else {
    1292                return 0.0;
    1293            }
    1294        }
    1295
    1296        @Override
    1297        public String toString() {
    1298            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
    1299        }
    1300    }
    1301}