    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 & 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 & 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);
    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        int bestPast = 0, currentPast = 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++;
    405                }
    406            }
    407            if (current[idx] != null && current[idx].getAssignments() != null) {
    408                for (Section section : current[idx].getSections()) {
    409                    if (section.isPast())
    410                        currentPast++;
    411                }
    412            }
    413        }
    414        if (currentPast < bestPast)
    415            return -1;
    416        if (bestPast < currentPast)
    417            return 1;
    418
    419        // 4-5. student quality
    420        if (getModel().getStudentQuality() != null) {
    421            double bestQuality = 0, currentQuality = 0;
    422            for (StudentQuality.Type type: StudentQuality.Type.values()) {
    423                for (int idx = 0; idx < current.length; idx++) {
    424                    if (best[idx] != null && best[idx].getAssignments() != null) {
    425                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
    426                        for (int x = 0; x < idx; x++) {
    427                            if (best[x] != null && best[x].getAssignments() != null)
    428                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
    429                        }
    430                    }
    431                    if (current[idx] != null && current[idx].getAssignments() != null) {
    432                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
    433                        for (int x = 0; x < idx; x++) {
    434                            if (current[x] != null && current[x].getAssignments() != null)
    435                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
    436                        }
    437                    }
    438                }
    439            }
    440            if (currentQuality < bestQuality)
    441                return -1;
    442            if (bestQuality < currentQuality)
    443                return 1;
    444        } else {
    445            // 4. avoid time overlaps
    446            if (getModel().getTimeOverlaps() != null) {
    447                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    448                for (int idx = 0; idx < current.length; idx++) {
    449                    if (best[idx] != null && best[idx].getAssignments() != null) {
    450                        for (int x = 0; x < idx; x++) {
    451                            if (best[x] != null && best[x].getAssignments() != null)
    452                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
    453                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    454                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), best[idx]);
    455                        }
    456                        for (int x = 0; x < idx; x++) {
    457                            if (current[x] != null && current[x].getAssignments() != null)
    458                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
    459                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    460                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), current[idx]);
    461                        }
    462                    }
    463                }
    464                for (int idx = 0; idx < current.length; idx++) {
    465                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    466                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
    467                    }
    468                    if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    469                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
    470                    }
    471                }
    472                if (currentTimeOverlaps < bestTimeOverlaps)
    473                    return -1;
    474                if (bestTimeOverlaps < currentTimeOverlaps)
    475                    return 1;
    476            }
    477
    478            // 5. avoid distance conflicts
    479            if (getModel().getDistanceConflict() != null) {
    480                int bestDistanceConf = 0, currentDistanceConf = 0;
    481                for (int idx = 0; idx < current.length; idx++) {
    482                    if (best[idx] != null && best[idx].getAssignments() != null) {
    483                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
    484                        for (int x = 0; x < idx; x++) {
    485                            if (best[x] != null && best[x].getAssignments() != null)
    486                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
    487                        }
    488                    }
    489                    if (current[idx] != null && current[idx].getAssignments() != null) {
    490                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
    491                        for (int x = 0; x < idx; x++) {
    492                            if (current[x] != null && current[x].getAssignments() != null)
    493                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]);
    494                        }
    495                    }
    496                }
    497                if (currentDistanceConf < bestDistanceConf)
    498                    return -1;
    499                if (bestDistanceConf < currentDistanceConf)
    500                    return 1;
    501            }
    502        }
    503
    504        // 6. avoid no-time and online sections (no-time first, online second)
    505        int bestNoTime = 0, currentNoTime = 0;
    506        int bestOnline = 0, currentOnline = 0;
    507        for (int idx = 0; idx < current.length; idx++) {
    508            if (best[idx] != null && best[idx].getAssignments() != null) {
    509                for (Section section : best[idx].getSections()) {
    510                    if (!section.hasTime())
    511                        bestNoTime++;
    512                    if (section.isOnline())
    513                        bestOnline++;
    514                }
    515                for (Section section : current[idx].getSections()) {
    516                    if (!section.hasTime())
    517                        currentNoTime++;
    518                    if (section.isOnline())
    519                        currentOnline++;
    520                }
    521            }
    522        }
    523        if (currentNoTime < bestNoTime)
    524            return -1;
    525        if (bestNoTime < currentNoTime)
    526            return 1;
    527        if (currentOnline < bestOnline)
    528            return -1;
    529        if (bestOnline < currentOnline)
    530            return 1;
    531
    532        // 7. balance sections
    533        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
    534        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
    535        for (int idx = 0; idx < current.length; idx++) {
    536            if (best[idx] != null && best[idx].getAssignments() != null) {
    537                for (Section section : best[idx].getSections()) {
    538                    Subpart subpart = section.getSubpart();
    539                    // skip unlimited and single section subparts
    540                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    541                        continue;
    542                    // average size
    543                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    544                    // section is below average
    545                    if (section.getLimit() < averageSize)
    546                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    547                    bestAltSectionsWithLimit++;
    548                }
    549                for (Section section : current[idx].getSections()) {
    550                    Subpart subpart = section.getSubpart();
    551                    // skip unlimited and single section subparts
    552                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    553                        continue;
    554                    // average size
    555                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    556                    // section is below average
    557                    if (section.getLimit() < averageSize)
    558                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    559                    currentAltSectionsWithLimit++;
    560                }
    561            }
    562        }
    563        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
    564                : 0.0);
    565        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
    566                / currentAltSectionsWithLimit : 0.0);
    567        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
    568            return -1;
    569        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
    570            return 1;
    571
    572        // 8. average penalty sections
    573        double bestPenalty = 0.0, currentPenalty = 0.0;
    574        for (int idx = 0; idx < current.length; idx++) {
    575            if (best[idx] != null && best[idx].getAssignments() != null) {
    576                for (Section section : best[idx].getSections())
    577                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
    578                for (Section section : current[idx].getSections())
    579                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
    580            }
    581        }
    582        if (currentPenalty < bestPenalty)
    583            return -1;
    584        if (bestPenalty < currentPenalty)
    585            return 1;
    586
    587        return 0;
    588    }
    589
    590    @Override
    591    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
    592            Enrollment[] best) {
    593        // 0. best priority & alternativity ignoring free time requests
    594        int alt = 0;
    595        boolean ft = false;
    596        boolean res = false;
    597        for (int idx = 0; idx < current.length; idx++) {
    598            if (isFreeTime(idx)) {
    599                ft = true;
    600                continue;
    601            }
    602            Request request = getRequest(idx);
    603            if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true;
    604            if (idx < maxIdx) {
    605                if (best[idx] != null) {
    606                    if (current[idx] == null)
    607                        return false; // higher priority request assigned
    608                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
    609                        return false; // less alternative request assigned
    610                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
    611                        return true; // less alternative request assigned
    612                    if (request.isAlternative())
    613                        alt--;
    614                } else {
    615                    if (current[idx] != null)
    616                        return true; // higher priority request assigned
    617                    if (!request.isAlternative())
    618                        alt++;
    619                }
    620            } else {
    621                if (best[idx] != null) {
    622                    if (best[idx].getTruePriority() > 0)
    623                        return true; // alternativity can be improved
    624                } else {
    625                    if (!request.isAlternative() || alt > 0)
    626                        return true; // priority can be improved
    627                }
    628            }
    629        }
    630
    631        // 0.1. allowed, but not available sections
    632        int notAvailable = 0;
    633        for (int idx = 0; idx < current.length; idx++) {
    634            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
    635                for (Section section: best[idx].getSections()) {
    636                    if (section.getLimit() == 0)
    637                        notAvailable ++;
    638                }
    639            }
    640            if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
    641                for (Section section: current[idx].getSections()) {
    642                    if (section.getLimit() == 0)
    643                        notAvailable --;
    644                }
    645            }
    646        }
    647        if (notAvailable > 0) {
    648            return true;
    649        }
    650
    651        // 0.5. avoid course time overlaps & unavailability overlaps
    652        if (getModel().getStudentQuality() != null) {
    653            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    654            for (int idx = 0; idx < current.length; idx++) {
    655                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
    656                    for (int x = 0; x < idx; x++) {
    657                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
    658                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
    659                    }
    660                }
    661                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
    662                    for (int x = 0; x < idx; x++) {
    663                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
    664                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
    665                    }
    666                }
    667            }
    668            for (int idx = 0; idx < current.length; idx++) {
    669                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    670                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
    671                }
    672                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    673                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
    674                }
    675            }
    676            if (currentTimeOverlaps < bestTimeOverlaps)
    677                return true;
    678            if (bestTimeOverlaps < currentTimeOverlaps)
    679                return false;
    680        } else if (getModel().getTimeOverlaps() != null) {
    681            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    682            for (int idx = 0; idx < current.length; idx++) {
    683                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
    684                    for (int x = 0; x < idx; x++) {
    685                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
    686                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
    687                    }
    688                }
    689                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
    690                    for (int x = 0; x < idx; x++) {
    691                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
    692                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
    693                    }
    694                }
    695            }
    696            for (int idx = 0; idx < current.length; idx++) {
    697                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    698                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
    699                }
    700                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    701                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
    702                }
    703            }
    704            if (currentTimeOverlaps < bestTimeOverlaps)
    705                return true;
    706            if (bestTimeOverlaps < currentTimeOverlaps)
    707                return false;
    708        }
    709
    710        // 1. maximize number of penalties
    711        double bestPenalties = 0, currentPenalties = 0;
    712        for (int idx = 0; idx < current.length; idx++) {
    713            if (best[idx] != null) {
    714                for (Section section : best[idx].getSections())
    715                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
    716            }
    717            if (current[idx] != null && idx < maxIdx) {
    718                for (Section section : current[idx].getSections())
    719                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
    720            }
    721        }
    722        if (currentPenalties < bestPenalties)
    723            return true;
    724        if (bestPenalties < currentPenalties)
    725            return false;
    726
    727        // 2. best priority & alternativity including free times
    728        if (ft) {
    729            alt = 0;
    730            for (int idx = 0; idx < current.length; idx++) {
    731                Request request = getStudent().getRequests().get(idx);
    732                if (idx < maxIdx) {
    733                    if (best[idx] != null) {
    734                        if (current[idx] == null)
    735                            return false; // higher priority request assigned
    736                        if (best[idx].getTruePriority() < current[idx].getTruePriority())
    737                            return false; // less alternative request assigned
    738                        if (best[idx].getTruePriority() > current[idx].getTruePriority())
    739                            return true; // less alternative request assigned
    740                        if (request.isAlternative())
    741                            alt--;
    742                    } else {
    743                        if (current[idx] != null)
    744                            return true; // higher priority request assigned
    745                        if (request instanceof CourseRequest && !request.isAlternative())
    746                            alt++;
    747                    }
    748                } else {
    749                    if (best[idx] != null) {
    750                        if (best[idx].getTruePriority() > 0)
    751                            return true; // alternativity can be improved
    752                    } else {
    753                        if (!request.isAlternative() || alt > 0)
    754                            return true; // priority can be improved
    755                    }
    756                }
    757            }
    758        }
    759
    760        // 3. maximize selection
    761        int bestSelected = 0, currentSelected = 0;
    762        for (int idx = 0; idx < current.length; idx++) {
    763            if (best[idx] != null && best[idx].isCourseRequest()) {
    764                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
    765                if (preferred != null && !preferred.isEmpty()) {
    766                    for (Section section : best[idx].getSections())
    767                        if (preferred.contains(section)) {
    768                            if (idx < maxIdx)
    769                                bestSelected++;
    770                        } else if (idx >= maxIdx)
    771                            bestSelected--;
    772                }
    773            }
    774            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
    775                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
    776                if (preferred != null && !preferred.isEmpty()) {
    777                    for (Section section : current[idx].getSections())
    778                        if (preferred.contains(section))
    779                            currentSelected++;
    780                }
    781            }
    782        }
    783        if (currentSelected > bestSelected)
    784            return true;
    785        if (bestSelected > currentSelected)
    786            return false;
    787
    788        // 3.5 maximize preferences
    789        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
    790        double bestSelectedSections = 0, currentSelectedSections = 0;
    791        for (int idx = 0; idx < current.length; idx++) {
    792            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    793                bestSelectedSections += best[idx].percentSelectedSameSection();
    794                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
    795                if (idx >= maxIdx) {
    796                    bestSelectedSections -= 1.0;
    797                    bestSelectedConfigs -= 1.0;
    798                }
    799            }
    800            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    801                currentSelectedSections += current[idx].percentSelectedSameSection();
    802                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
    803            }
    804        }
    805        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
    806        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
    807
    808        // 3.9 maximize selection with penalization for not followed reservations
    809        if (res) {
    810            alt = 0;
    811            for (int idx = 0; idx < current.length; idx++) {
    812                Request request = getStudent().getRequests().get(idx);
    813                if (idx < maxIdx) {
    814                    if (best[idx] != null) {
    815                        if (current[idx] == null)
    816                            return false; // higher priority request assigned
    817                        if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority())
    818                            return false; // less alternative request assigned
    819                        if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority())
    820                            return true; // less alternative request assigned
    821                        if (request.isAlternative())
    822                            alt--;
    823                    } else {
    824                        if (current[idx] != null)
    825                            return true; // higher priority request assigned
    826                        if (request instanceof CourseRequest && !request.isAlternative())
    827                            alt++;
    828                    }
    829                } else {
    830                    if (best[idx] != null) {
    831                        if (best[idx].getTruePriority() > 0)
    832                            return true; // alternativity can be improved
    833                    } else {
    834                        if (!request.isAlternative() || alt > 0)
    835                            return true; // priority can be improved
    836                    }
    837                }
    838            }
    839        }
    840
    841        // 3.95 avoid past sections
    842        int bestPast = 0, currentPast = 0;
    843        for (int idx = 0; idx < current.length; idx++) {
    844            if (best[idx] != null && best[idx].getAssignments() != null) {
    845                for (Section section : best[idx].getSections()) {
    846                    if (section.isPast())
    847                        bestPast++;
    848                }
    849            }
    850            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null) {
    851                for (Section section : current[idx].getSections()) {
    852                    if (section.isPast())
    853                        currentPast++;
    854                }
    855            }
    856        }
    857        if (currentPast < bestPast)
    858            return true;
    859        if (bestPast < currentPast)
    860            return false;
    861
    862        // 4-5. student quality
    863        if (getModel().getStudentQuality() != null) {
    864            double bestQuality = 0, currentQuality = 0;
    865            for (StudentQuality.Type type: StudentQuality.Type.values()) {
    866                for (int idx = 0; idx < current.length; idx++) {
    867                    if (best[idx] != null) {
    868                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
    869                        for (int x = 0; x < idx; x++) {
    870                            if (best[x] != null)
    871                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
    872                        }
    873                    }
    874                    if (current[idx] != null && idx < maxIdx) {
    875                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
    876                        for (int x = 0; x < idx; x++) {
    877                            if (current[x] != null)
    878                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
    879                        }
    880                    }
    881                }
    882            }
    883            if (currentQuality < bestQuality)
    884                return true;
    885            if (bestQuality < currentQuality)
    886                return false;
    887        } else {
    888            // 4. avoid time overlaps
    889            if (getModel().getTimeOverlaps() != null) {
    890                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
    891                for (int idx = 0; idx < current.length; idx++) {
    892                    if (best[idx] != null) {
    893                        for (int x = 0; x < idx; x++) {
    894                            if (best[x] != null)
    895                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
    896                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    897                                bestTimeOverlaps += getModel().getTimeOverlaps()
    898                                        .nrConflicts(
    899                                                ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
    900                                                best[idx]);
    901                        }
    902                    }
    903                    if (current[idx] != null && idx < maxIdx) {
    904                        for (int x = 0; x < idx; x++) {
    905                            if (current[x] != null)
    906                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
    907                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
    908                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
    909                                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
    910                                        current[idx]);
    911                        }
    912                    }
    913                }
    914                for (int idx = 0; idx < current.length; idx++) {
    915                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    916                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
    917                    }
    918                    if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
    919                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
    920                    }
    921                }
    922                if (currentTimeOverlaps < bestTimeOverlaps)
    923                    return true;
    924                if (bestTimeOverlaps < currentTimeOverlaps)
    925                    return false;
    926            }
    927
    928            // 5. avoid distance conflicts
    929            if (getModel().getDistanceConflict() != null) {
    930                int bestDistanceConf = 0, currentDistanceConf = 0;
    931                for (int idx = 0; idx < current.length; idx++) {
    932                    if (best[idx] != null) {
    933                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
    934                        for (int x = 0; x < idx; x++) {
    935                            if (best[x] != null)
    936                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
    937                        }
    938                    }
    939                    if (current[idx] != null && idx < maxIdx) {
    940                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
    941                        for (int x = 0; x < idx; x++) {
    942                            if (current[x] != null)
    943                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
    944                                        current[idx]);
    945                        }
    946                    }
    947                }
    948                if (currentDistanceConf < bestDistanceConf)
    949                    return true;
    950                if (bestDistanceConf < currentDistanceConf)
    951                    return false;
    952            }
    953        }
    954
    955        // 6. avoid no-time and online sections (no-time first, online second)
    956        int bestNoTime = 0, currentNoTime = 0;
    957        int bestOnline = 0, currentOnline = 0;
    958        for (int idx = 0; idx < current.length; idx++) {
    959            if (best[idx] != null) {
    960                for (Section section : best[idx].getSections()) {
    961                    if (!section.hasTime())
    962                        bestNoTime++;
    963                    if (section.isOnline())
    964                        bestOnline++;
    965                }
    966            }
    967            if (current[idx] != null && idx < maxIdx) {
    968                for (Section section : current[idx].getSections()) {
    969                    if (!section.hasTime())
    970                        currentNoTime++;
    971                    if (section.isOnline())
    972                        currentOnline++;
    973                }
    974            }
    975        }
    976        if (currentNoTime < bestNoTime)
    977            return true;
    978        if (bestNoTime < currentNoTime)
    979            return false;
    980        if (currentOnline < bestOnline)
    981            return true;
    982        if (bestOnline < currentOnline)
    983            return false;
    984
    985        // 7. balance sections
    986        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
    987        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
    988        for (int idx = 0; idx < current.length; idx++) {
    989            if (best[idx] != null) {
    990                for (Section section : best[idx].getSections()) {
    991                    Subpart subpart = section.getSubpart();
    992                    // skip unlimited and single section subparts
    993                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    994                        continue;
    995                    // average size
    996                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    997                    // section is below average
    998                    if (section.getLimit() < averageSize)
    999                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    1000                    bestAltSectionsWithLimit++;
    1001                }
    1002            }
    1003            if (current[idx] != null && idx < maxIdx) {
    1004                for (Section section : current[idx].getSections()) {
    1005                    Subpart subpart = section.getSubpart();
    1006                    // skip unlimited and single section subparts
    1007                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    1008                        continue;
    1009                    // average size
    1010                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    1011                    // section is below average
    1012                    if (section.getLimit() < averageSize)
    1013                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
    1014                    currentAltSectionsWithLimit++;
    1015                }
    1016            }
    1017        }
    1018        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
    1019                : 0.0);
    1020        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
    1021                / currentAltSectionsWithLimit : 0.0);
    1022        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
    1023            return true;
    1024        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
    1025            return false;
    1026
    1027        // 8. average penalty sections
    1028        double bestPenalty = 0.0, currentPenalty = 0.0;
    1029        for (int idx = 0; idx < current.length; idx++) {
    1030            if (best[idx] != null) {
    1031                for (Section section : best[idx].getSections())
    1032                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
    1033                if (idx >= maxIdx && best[idx].isCourseRequest())
    1034                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
    1035            }
    1036            if (current[idx] != null && idx < maxIdx) {
    1037                for (Section section : current[idx].getSections())
    1038                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
    1039            }
    1040        }
    1041        if (currentPenalty < bestPenalty)
    1042            return true;
    1043        if (bestPenalty < currentPenalty)
    1044            return false;
    1045
    1046        return true;
    1047    }
    1048
    1049    @Override
    1050    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
    1051        if (enrollemnts == null)
    1052            return 0.0;
    1053        double value = 0.0;
    1054        for (int idx = 0; idx < enrollemnts.length; idx++) {
    1055            if (enrollemnts[idx] != null)
    1056                if (getModel().getStudentQuality() != null) {
    1057                    value += getWeight(assignment, enrollemnts[idx], getStudentQualityConflicts(enrollemnts, idx));
    1058                } else {
    1059                    value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), getTimeOverlappingConflicts(enrollemnts, idx));
    1060                }
    1061        }
    1062        return value;
    1063    }
    1064
    1065    @Override
    1066    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
    1067        // 1. alternativity
    1068        if (e1.getTruePriority() < e2.getTruePriority())
    1069            return -1;
    1070        if (e1.getTruePriority() > e2.getTruePriority())
    1071            return 1;
    1072
    1073        // 1.5 not available sections
    1074        int na1 = 0, na2 = 0;
    1075        for (Section section: e1.getSections())
    1076            if (section.getLimit() == 0) na1++;
    1077        for (Section section: e2.getSections())
    1078            if (section.getLimit() == 0) na2++;
    1079        if (na1 < na2) return -1;
    1080        if (na1 > na2) return 1;
    1081
    1082        // 2. maximize number of penalties
    1083        double p1 = 0, p2 = 0;
    1084        for (Section section : e1.getSections())
    1085            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
    1086        for (Section section : e2.getSections())
    1087            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
    1088        if (p1 < p2)
    1089            return -1;
    1090        if (p2 < p1)
    1091            return 1;
    1092
    1093        // 3. maximize selection
    1094        if (e1.isCourseRequest()) {
    1095            Set<Section> preferred = getPreferredSections(e1.getRequest());
    1096            if (preferred != null && !preferred.isEmpty()) {
    1097                int s1 = 0, s2 = 0;
    1098                for (Section section : e1.getSections())
    1099                    if (preferred.contains(section))
    1100                        s1++;
    1101                for (Section section : e2.getSections())
    1102                    if (preferred.contains(section))
    1103                        s2++;
    1104                if (s2 > s1)
    1105                    return -1;
    1106                if (s1 > s2)
    1107                    return 1;
    1108            }
    1109        }
    1110
    1111        // 3.5 maximize preferences
    1112        if (e1.isCourseRequest()) {
    1113            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
    1114            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
    1115            if (s1 > s2) return -1;
    1116            if (s2 > s1) return 1;
    1117        }
    1118
    1119        // 3.9 maximize selection with penalization for not followed reservations
    1120        if (e1.getAdjustedPriority() < e2.getAdjustedPriority())
    1121            return -1;
    1122        if (e1.getAdjustedPriority() > e2.getAdjustedPriority())
    1123            return 1;
    1124
    1125        // 3.95 avoid past sections
    1126        int w1 = 0, w2 = 0;
    1127        for (Section section : e1.getSections()) {
    1128            if (section.isPast())
    1129                w1++;
    1130        }
    1131        for (Section section : e2.getSections()) {
    1132            if (section.isPast())
    1133                w2++;
    1134        }
    1135        if (w1 < w2)
    1136            return -1;
    1137        if (w2 < w1)
    1138            return 1;
    1139
    1140        // 4. avoid time overlaps
    1141        if (getTimesToAvoid() == null) {
    1142            if (getModel().getStudentQuality() != null) {
    1143                int o1 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e1) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e1);
    1144                int o2 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e2) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e2);
    1145                if (o1 < o2)
    1146                    return -1;
    1147                if (o2 < o1)
    1148                    return 1;
    1149            } else if (getModel().getTimeOverlaps() != null) {
    1150                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1);
    1151                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2);
    1152                if (o1 < o2)
    1153                    return -1;
    1154                if (o2 < o1)
    1155                    return 1;
    1156            }
    1157        } else {
    1158            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
    1159                double o1 = 0.0, o2 = 0.0;
    1160                for (Section s : e1.getSections()) {
    1161                    if (s.getTime() != null)
    1162                        for (TimeToAvoid avoid : getTimesToAvoid()) {
    1163                            if (avoid.priority() > e1.getRequest().getPriority())
    1164                                o1 += avoid.overlap(s.getTime());
    1165                        }
    1166                }
    1167                for (Section s : e2.getSections()) {
    1168                    if (s.getTime() != null)
    1169                        for (TimeToAvoid avoid : getTimesToAvoid()) {
    1170                            if (avoid.priority() > e2.getRequest().getPriority())
    1171                                o2 += avoid.overlap(s.getTime());
    1172                        }
    1173                }
    1174                if (o1 < o2)
    1175                    return -1;
    1176                if (o2 < o1)
    1177                    return 1;
    1178            }
    1179        }
    1180
    1181        // 5. avoid distance conflicts
    1182        if (getModel().getDistanceConflict() != null) {
    1183            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
    1184            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
    1185            if (c1 < c2)
    1186                return -1;
    1187            if (c2 < c1)
    1188                return 1;
    1189        }
    1190
    1191        // 6. avoid no-time and online sections (no-time first, online second)
    1192        int n1 = 0, n2 = 0;
    1193        int o1 = 0, o2 = 0;
    1194        for (Section section : e1.getSections()) {
    1195            if (!section.hasTime())
    1196                n1++;
    1197            if (section.isOnline())
    1198                o1++;
    1199        }
    1200        for (Section section : e2.getSections()) {
    1201            if (!section.hasTime())
    1202                n2++;
    1203            if (section.isOnline())
    1204                o2++;
    1205        }
    1206        if (n1 < n2)
    1207            return -1;
    1208        if (n2 < n1)
    1209            return 1;
    1210        if (o1 < o2)
    1211            return -1;
    1212        if (o2 < o1)
    1213            return 1;
    1214
    1215        // 7. balance sections
    1216        double u1 = 0.0, u2 = 0.0;
    1217        int a1 = 0, a2 = 0;
    1218        for (Section section : e1.getSections()) {
    1219            Subpart subpart = section.getSubpart();
    1220            // skip unlimited and single section subparts
    1221            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    1222                continue;
    1223            // average size
    1224            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    1225            // section is below average
    1226            if (section.getLimit() < averageSize)
    1227                u1 += (averageSize - section.getLimit()) / averageSize;
    1228            a1++;
    1229        }
    1230        for (Section section : e2.getSections()) {
    1231            Subpart subpart = section.getSubpart();
    1232            // skip unlimited and single section subparts
    1233            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    1234                continue;
    1235            // average size
    1236            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    1237            // section is below average
    1238            if (section.getLimit() < averageSize)
    1239                u2 += (averageSize - section.getLimit()) / averageSize;
    1240            a2++;
    1241        }
    1242        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
    1243        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
    1244        if (f1 < f2)
    1245            return -1;
    1246        if (f2 < f1)
    1247            return 1;
    1248
    1249        // 8. average penalty sections
    1250        double x1 = 0.0, x2 = 0.0;
    1251        for (Section section : e1.getSections())
    1252            x1 += section.getPenalty() / e1.getSections().size();
    1253        for (Section section : e2.getSections())
    1254            x2 += section.getPenalty() / e2.getSections().size();
    1255        if (x1 < x2)
    1256            return -1;
    1257        if (x2 < x1)
    1258            return 1;
    1259
    1260        return 0;
    1261    }
    1262
    1263    /**
    1264     * Time to be avoided.
    1265     */
    1266    public static class TimeToAvoid {
    1267        private TimeLocation iTime;
    1268        private double iPenalty;
    1269        private int iPriority;
    1270
    1271        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
    1272            iTime = time;
    1273            iPenalty = penalty;
    1274            iPriority = priority;
    1275        }
    1276
    1277        public int priority() {
    1278            return iPriority;
    1279        }
    1280
    1281        public double overlap(TimeLocation time) {
    1282            if (time.hasIntersection(iTime)) {
    1283                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedHours(iTime))
    1284                        / (iTime.getNrMeetings() * iTime.getLength());
    1285            } else {
    1286                return 0.0;
    1287            }
    1288        }
    1289
    1290        @Override
    1291        public String toString() {
    1292            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
    1293        }
    1294    }
    1295}