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.TimeOverlapsCounter;
013import org.cpsolver.studentsct.model.CourseRequest;
014import org.cpsolver.studentsct.model.Enrollment;
015import org.cpsolver.studentsct.model.FreeTimeRequest;
016import org.cpsolver.studentsct.model.Request;
017import org.cpsolver.studentsct.model.Section;
018import org.cpsolver.studentsct.model.Student;
019import org.cpsolver.studentsct.model.Subpart;
020import org.cpsolver.studentsct.model.Unavailability;
021import org.cpsolver.studentsct.online.OnlineSectioningModel;
022import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionCriterion;
023import org.cpsolver.studentsct.weights.StudentWeights;
024
025/**
026* Multi-criteria selection criterion. This provides a lexicographical order of solutions using the
027* following criteria:
028* <ul>
029* <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)
030* <li>avoid or minimize course time overlaps
031* <li>minimise use of over-expected classes (this prevents students of getting into classes that we know will be needed later in the process)
032* <li>best priority & alternativity including free time requests (this is to prevent students of gaming the system by adding free time requests)
033* <li>maximise selection (preferred sections)
034* <li>avoid or minimise time overlaps (for classes that are allowed to overlap and for free time requests)
035* <li>avoid or minimise distance conflicts
036* <li>avoid classes that have no time assignment (arranged hours)
037* <li>balance sections
038* <li>minimise class penalties (expressing how much a class is over-expected)
039* </ul>
040* 
041* @version StudentSct 1.3 (Student Sectioning)<br>
042*          Copyright (C) 2014 Tomas Muller<br>
043*          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
044*          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
045* <br>
046*          This library is free software; you can redistribute it and/or modify
047*          it under the terms of the GNU Lesser General Public License as
048*          published by the Free Software Foundation; either version 3 of the
049*          License, or (at your option) any later version. <br>
050* <br>
051*          This library is distributed in the hope that it will be useful, but
052*          WITHOUT ANY WARRANTY; without even the implied warranty of
053*          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
054*          Lesser General Public License for more details. <br>
055* <br>
056*          You should have received a copy of the GNU Lesser General Public
057*          License along with this library; if not see <a
058*          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
059* 
060*/
061public class OnlineSectioningCriterion implements SelectionCriterion {
062    private Hashtable<CourseRequest, Set<Section>> iPreferredSections = null;
063    private List<TimeToAvoid> iTimesToAvoid = null;
064    private OnlineSectioningModel iModel;
065    private Student iStudent;
066
067    /**
068     * Constructor
069     * @param student current student
070     * @param model online student sectioning model
071     * @param assignment current assignment
072     * @param preferredSections preferred sections
073     */
074    public OnlineSectioningCriterion(Student student, OnlineSectioningModel model,
075            Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) {
076        iStudent = student;
077        iModel = model;
078        iPreferredSections = preferredSections;
079        if (model.getProperties().getPropertyBoolean("OnlineStudentSectioning.TimesToAvoidHeuristics", true)) {
080            iTimesToAvoid = new ArrayList<TimeToAvoid>();
081            for (Request r : iStudent.getRequests()) {
082                if (r instanceof CourseRequest) {
083                    List<Enrollment> enrollments = ((CourseRequest) r).getAvaiableEnrollmentsSkipSameTime(assignment);
084                    if (enrollments.size() <= 5) {
085                        int penalty = (7 - enrollments.size()) * (r.isAlternative() ? 1 : 7 - enrollments.size());
086                        for (Enrollment enrollment : enrollments)
087                            for (Section section : enrollment.getSections())
088                                if (section.getTime() != null)
089                                    iTimesToAvoid.add(new TimeToAvoid(section.getTime(), penalty, r.getPriority()));
090                    }
091                } else if (r instanceof FreeTimeRequest) {
092                    iTimesToAvoid.add(new TimeToAvoid(((FreeTimeRequest) r).getTime(), 1, Integer.MAX_VALUE));
093                }
094            }
095            for (Unavailability unavailability: iStudent.getUnavailabilities())
096                if (unavailability.getTime() != null)
097                    iTimesToAvoid.add(new TimeToAvoid(unavailability.getTime(), 1, Integer.MAX_VALUE));
098        }
099    }
100
101    protected OnlineSectioningModel getModel() {
102        return iModel;
103    }
104
105    protected Student getStudent() {
106        return iStudent;
107    }
108
109    protected Set<Section> getPreferredSections(Request request) {
110        return iPreferredSections.get(request);
111    }
112
113    protected List<TimeToAvoid> getTimesToAvoid() {
114        return iTimesToAvoid;
115    }
116
117    /**
118     * Distance conflicts of idx-th assignment of the current schedule
119     */
120    public Set<DistanceConflict.Conflict> getDistanceConflicts(Enrollment[] assignment, int idx) {
121        if (getModel().getDistanceConflict() == null || assignment[idx] == null)
122            return null;
123        Set<DistanceConflict.Conflict> dist = getModel().getDistanceConflict().conflicts(assignment[idx]);
124        for (int x = 0; x < idx; x++)
125            if (assignment[x] != null)
126                dist.addAll(getModel().getDistanceConflict().conflicts(assignment[x], assignment[idx]));
127        return dist;
128    }
129
130    /**
131     * Time overlapping conflicts of idx-th assignment of the current schedule
132     */
133    public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(Enrollment[] assignment, int idx) {
134        if (getModel().getTimeOverlaps() == null || assignment[idx] == null)
135            return null;
136        Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>();
137        for (int x = 0; x < idx; x++)
138            if (assignment[x] != null) {
139                overlaps.addAll(getModel().getTimeOverlaps().conflicts(assignment[x], assignment[idx]));
140            } else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
141                overlaps.addAll(getModel().getTimeOverlaps().conflicts(
142                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), assignment[idx]));
143        overlaps.addAll(getModel().getTimeOverlaps().notAvailableTimeConflicts(assignment[idx]));
144        return overlaps;
145    }
146
147    /**
148     * Weight of an assignment. Unlike
149     * {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this
150     * side of distance conflicts and time overlaps.
151     **/
152    protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment,
153            Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
154        double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment);
155        if (distanceConflicts != null)
156            for (DistanceConflict.Conflict c : distanceConflicts) {
157                Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
158                if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
159                    weight += getModel().getStudentWeights().getDistanceConflictWeight(assignment, c);
160            }
161        if (timeOverlappingConflicts != null)
162            for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) {
163                weight += getModel().getStudentWeights().getTimeOverlapConflictWeight(assignment, enrollment, c);
164            }
165        return enrollment.getRequest().getWeight() * weight;
166    }
167
168    public Request getRequest(int index) {
169        return (index < 0 || index >= getStudent().getRequests().size() ? null : getStudent().getRequests().get(index));
170    }
171
172    public boolean isFreeTime(int index) {
173        Request r = getRequest(index);
174        return r != null && r instanceof FreeTimeRequest;
175    }
176    
177    @Override
178    public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) {
179        if (best == null)
180            return -1;
181
182        // 0. best priority & alternativity ignoring free time requests
183        boolean ft = false;
184        for (int idx = 0; idx < current.length; idx++) {
185            if (isFreeTime(idx)) {
186                ft = true;
187                continue;
188            }
189            if (best[idx] != null && best[idx].getAssignments() != null) {
190                if (current[idx] == null || current[idx].getSections() == null)
191                    return 1; // higher priority request assigned
192                if (best[idx].getPriority() < current[idx].getPriority())
193                    return 1; // less alternative request assigned
194            } else {
195                if (current[idx] != null && current[idx].getAssignments() != null)
196                    return -1; // higher priority request assigned
197            }
198        }
199        
200        // 0.1. allowed, but not available sections
201        int bestNotAvailable = 0, currentNotAvailable = 0;
202        for (int idx = 0; idx < current.length; idx++) {
203            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
204                for (Section section: best[idx].getSections()) {
205                    if (section.getLimit() == 0)
206                        bestNotAvailable ++;
207                }
208            }
209            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
210                for (Section section: current[idx].getSections()) {
211                    if (section.getLimit() == 0)
212                        currentNotAvailable ++;
213                }
214            }
215        }
216        if (bestNotAvailable > currentNotAvailable) return -1;
217        if (bestNotAvailable < currentNotAvailable) return 1;
218
219        // 0.5. avoid course time overlaps & unavailabilities
220        if (getModel().getTimeOverlaps() != null) {
221            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
222            for (int idx = 0; idx < current.length; idx++) {
223                if (best[idx] != null && best[idx].getAssignments() != null
224                                && best[idx].getRequest() instanceof CourseRequest) {
225                    for (int x = 0; x < idx; x++) {
226                        if (best[x] != null && best[x].getAssignments() != null
227                                        && best[x].getRequest() instanceof CourseRequest)
228                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
229                    }
230                    for (int x = 0; x < idx; x++) {
231                        if (current[x] != null && current[x].getAssignments() != null
232                                        && current[x].getRequest() instanceof CourseRequest)
233                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
234                    }
235                }
236            }
237            for (int idx = 0; idx < current.length; idx++) {
238                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
239                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
240                }
241                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
242                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
243                }
244            }
245            if (currentTimeOverlaps < bestTimeOverlaps)
246                return -1;
247            if (bestTimeOverlaps < currentTimeOverlaps)
248                return 1;
249        }
250
251        // 1. minimize number of penalties
252        double bestPenalties = 0, currentPenalties = 0;
253        for (int idx = 0; idx < current.length; idx++) {
254            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
255                for (Section section : best[idx].getSections())
256                    bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest());
257                for (Section section : current[idx].getSections())
258                    currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest());
259            }
260        }
261        if (currentPenalties < bestPenalties)
262            return -1;
263        if (bestPenalties < currentPenalties)
264            return 1;
265
266        // 2. best priority & alternativity including free time requests
267        if (ft) {
268            for (int idx = 0; idx < current.length; idx++) {
269                if (best[idx] != null && best[idx].getAssignments() != null) {
270                    if (current[idx] == null || current[idx].getSections() == null)
271                        return 1; // higher priority request assigned
272                    if (best[idx].getPriority() < current[idx].getPriority())
273                        return 1; // less alternative request assigned
274                } else {
275                    if (current[idx] != null && current[idx].getAssignments() != null)
276                        return -1; // higher priority request assigned
277                }
278            }
279        }
280
281        // 3. maximize selection
282        int bestSelected = 0, currentSelected = 0;
283        for (int idx = 0; idx < current.length; idx++) {
284            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
285                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
286                if (preferred != null && !preferred.isEmpty()) {
287                    for (Section section : best[idx].getSections())
288                        if (preferred.contains(section))
289                            bestSelected++;
290                    for (Section section : current[idx].getSections())
291                        if (preferred.contains(section))
292                            currentSelected++;
293                }
294            }
295        }
296        if (currentSelected > bestSelected)
297            return -1;
298        if (bestSelected > currentSelected)
299            return 1;
300        
301        // 3.5 maximize preferences
302        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
303        double bestSelectedSections = 0, currentSelectedSections = 0;
304        for (int idx = 0; idx < current.length; idx++) {
305            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
306                bestSelectedSections += best[idx].percentSelectedSameSection();
307                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
308            }
309            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
310                currentSelectedSections += current[idx].percentSelectedSameSection();
311                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
312            }
313        }
314        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1;
315        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1;
316
317        // 4. avoid time overlaps
318        if (getModel().getTimeOverlaps() != null) {
319            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
320            for (int idx = 0; idx < current.length; idx++) {
321                if (best[idx] != null && best[idx].getAssignments() != null) {
322                    for (int x = 0; x < idx; x++) {
323                        if (best[x] != null && best[x].getAssignments() != null)
324                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
325                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
326                            bestTimeOverlaps += getModel().getTimeOverlaps()
327                                    .nrConflicts(
328                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
329                                            best[idx]);
330                    }
331                    for (int x = 0; x < idx; x++) {
332                        if (current[x] != null && current[x].getAssignments() != null)
333                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
334                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
335                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
336                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
337                                    current[idx]);
338                    }
339                }
340            }
341            for (int idx = 0; idx < current.length; idx++) {
342                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
343                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
344                }
345                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
346                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
347                }
348            }
349            if (currentTimeOverlaps < bestTimeOverlaps)
350                return -1;
351            if (bestTimeOverlaps < currentTimeOverlaps)
352                return 1;
353        }
354
355        // 5. avoid distance conflicts
356        if (getModel().getDistanceConflict() != null) {
357            int bestDistanceConf = 0, currentDistanceConf = 0;
358            for (int idx = 0; idx < current.length; idx++) {
359                if (best[idx] != null && best[idx].getAssignments() != null) {
360                    bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
361                    for (int x = 0; x < idx; x++) {
362                        if (best[x] != null && best[x].getAssignments() != null)
363                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
364                    }
365                }
366                if (current[idx] != null && current[idx].getAssignments() != null) {
367                    currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
368                    for (int x = 0; x < idx; x++) {
369                        if (current[x] != null && current[x].getAssignments() != null)
370                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]);
371                    }
372                }
373            }
374            if (currentDistanceConf < bestDistanceConf)
375                return -1;
376            if (bestDistanceConf < currentDistanceConf)
377                return 1;
378        }
379
380        // 6. avoid no-time sections
381        int bestNoTime = 0, currentNoTime = 0;
382        for (int idx = 0; idx < current.length; idx++) {
383            if (best[idx] != null && best[idx].getAssignments() != null) {
384                for (Section section : best[idx].getSections())
385                    if (section.getTime() == null)
386                        bestNoTime++;
387                for (Section section : current[idx].getSections())
388                    if (section.getTime() == null)
389                        currentNoTime++;
390            }
391        }
392        if (currentNoTime < bestNoTime)
393            return -1;
394        if (bestNoTime < currentNoTime)
395            return 1;
396
397        // 7. balance sections
398        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
399        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 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                    Subpart subpart = section.getSubpart();
404                    // skip unlimited and single section subparts
405                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
406                        continue;
407                    // average size
408                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
409                    // section is below average
410                    if (section.getLimit() < averageSize)
411                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
412                    bestAltSectionsWithLimit++;
413                }
414                for (Section section : current[idx].getSections()) {
415                    Subpart subpart = section.getSubpart();
416                    // skip unlimited and single section subparts
417                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
418                        continue;
419                    // average size
420                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
421                    // section is below average
422                    if (section.getLimit() < averageSize)
423                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
424                    currentAltSectionsWithLimit++;
425                }
426            }
427        }
428        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
429                : 0.0);
430        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
431                / currentAltSectionsWithLimit : 0.0);
432        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
433            return -1;
434        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
435            return 1;
436
437        // 8. average penalty sections
438        double bestPenalty = 0.0, currentPenalty = 0.0;
439        for (int idx = 0; idx < current.length; idx++) {
440            if (best[idx] != null && best[idx].getAssignments() != null) {
441                for (Section section : best[idx].getSections())
442                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
443                for (Section section : current[idx].getSections())
444                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
445            }
446        }
447        if (currentPenalty < bestPenalty)
448            return -1;
449        if (bestPenalty < currentPenalty)
450            return 1;
451
452        return 0;
453    }
454
455    @Override
456    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
457            Enrollment[] best) {
458        // 0. best priority & alternativity ignoring free time requests
459        int alt = 0;
460        boolean ft = false;
461        for (int idx = 0; idx < current.length; idx++) {
462            if (isFreeTime(idx)) {
463                ft = true;
464                continue;
465            }
466            Request request = getRequest(idx);
467            if (idx < maxIdx) {
468                if (best[idx] != null) {
469                    if (current[idx] == null)
470                        return false; // higher priority request assigned
471                    if (best[idx].getPriority() < current[idx].getPriority())
472                        return false; // less alternative request assigned
473                    if (request.isAlternative())
474                        alt--;
475                } else {
476                    if (current[idx] != null)
477                        return true; // higher priority request assigned
478                    if (!request.isAlternative())
479                        alt++;
480                }
481            } else {
482                if (best[idx] != null) {
483                    if (best[idx].getPriority() > 0)
484                        return true; // alternativity can be improved
485                } else {
486                    if (!request.isAlternative() || alt > 0)
487                        return true; // priority can be improved
488                }
489            }
490        }
491        
492        // 0.1. allowed, but not available sections
493        int notAvailable = 0;
494        for (int idx = 0; idx < current.length; idx++) {
495            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
496                for (Section section: best[idx].getSections()) {
497                    if (section.getLimit() == 0)
498                        notAvailable ++;
499                }
500            }
501            if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
502                for (Section section: current[idx].getSections()) {
503                    if (section.getLimit() == 0)
504                        notAvailable --;
505                }
506            }
507        }
508        if (notAvailable > 0) {
509            return true;
510        }
511
512        // 0.5. avoid course time overlaps & unavailability overlaps
513        if (getModel().getTimeOverlaps() != null) {
514            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
515            for (int idx = 0; idx < current.length; idx++) {
516                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
517                    for (int x = 0; x < idx; x++) {
518                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
519                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
520                    }
521                }
522                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
523                    for (int x = 0; x < idx; x++) {
524                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
525                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
526                    }
527                }
528            }
529            for (int idx = 0; idx < current.length; idx++) {
530                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
531                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
532                }
533                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
534                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
535                }
536            }
537            if (currentTimeOverlaps < bestTimeOverlaps)
538                return true;
539            if (bestTimeOverlaps < currentTimeOverlaps)
540                return false;
541        }
542
543        // 1. maximize number of penalties
544        double bestPenalties = 0, currentPenalties = 0;
545        for (int idx = 0; idx < current.length; idx++) {
546            if (best[idx] != null) {
547                for (Section section : best[idx].getSections())
548                    bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest());
549            }
550            if (current[idx] != null && idx < maxIdx) {
551                for (Section section : current[idx].getSections())
552                    currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest());
553            }
554        }
555        if (currentPenalties < bestPenalties)
556            return true;
557        if (bestPenalties < currentPenalties)
558            return false;
559
560        // 2. best priority & alternativity including free times
561        if (ft) {
562            alt = 0;
563            for (int idx = 0; idx < current.length; idx++) {
564                Request request = getStudent().getRequests().get(idx);
565                if (idx < maxIdx) {
566                    if (best[idx] != null) {
567                        if (current[idx] == null)
568                            return false; // higher priority request assigned
569                        if (best[idx].getPriority() < current[idx].getPriority())
570                            return false; // less alternative request assigned
571                        if (request.isAlternative())
572                            alt--;
573                    } else {
574                        if (current[idx] != null)
575                            return true; // higher priority request assigned
576                        if (request instanceof CourseRequest && !request.isAlternative())
577                            alt++;
578                    }
579                } else {
580                    if (best[idx] != null) {
581                        if (best[idx].getPriority() > 0)
582                            return true; // alternativity can be improved
583                    } else {
584                        if (!request.isAlternative() || alt > 0)
585                            return true; // priority can be improved
586                    }
587                }
588            }
589        }
590
591        // 3. maximize selection
592        int bestSelected = 0, currentSelected = 0;
593        for (int idx = 0; idx < current.length; idx++) {
594            if (best[idx] != null && best[idx].isCourseRequest()) {
595                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
596                if (preferred != null && !preferred.isEmpty()) {
597                    for (Section section : best[idx].getSections())
598                        if (preferred.contains(section)) {
599                            if (idx < maxIdx)
600                                bestSelected++;
601                        } else if (idx >= maxIdx)
602                            bestSelected--;
603                }
604            }
605            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
606                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
607                if (preferred != null && !preferred.isEmpty()) {
608                    for (Section section : current[idx].getSections())
609                        if (preferred.contains(section))
610                            currentSelected++;
611                }
612            }
613        }
614        if (currentSelected > bestSelected)
615            return true;
616        if (bestSelected > currentSelected)
617            return false;
618
619        // 3.5 maximize preferences
620        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
621        double bestSelectedSections = 0, currentSelectedSections = 0;
622        for (int idx = 0; idx < current.length; idx++) {
623            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
624                bestSelectedSections += best[idx].percentSelectedSameSection();
625                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
626                if (idx >= maxIdx) {
627                    bestSelectedSections -= 1.0;
628                    bestSelectedConfigs -= 1.0;
629                }
630            }
631            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
632                currentSelectedSections += current[idx].percentSelectedSameSection();
633                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
634            }
635        }
636        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
637        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
638        
639        // 4. avoid time overlaps
640        if (getModel().getTimeOverlaps() != null) {
641            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
642            for (int idx = 0; idx < current.length; idx++) {
643                if (best[idx] != null) {
644                    for (int x = 0; x < idx; x++) {
645                        if (best[x] != null)
646                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
647                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
648                            bestTimeOverlaps += getModel().getTimeOverlaps()
649                                    .nrConflicts(
650                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
651                                            best[idx]);
652                    }
653                }
654                if (current[idx] != null && idx < maxIdx) {
655                    for (int x = 0; x < idx; x++) {
656                        if (current[x] != null)
657                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
658                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
659                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
660                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
661                                    current[idx]);
662                    }
663                }
664            }
665            for (int idx = 0; idx < current.length; idx++) {
666                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
667                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
668                }
669                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
670                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
671                }
672            }
673            if (currentTimeOverlaps < bestTimeOverlaps)
674                return true;
675            if (bestTimeOverlaps < currentTimeOverlaps)
676                return false;
677        }
678
679        // 5. avoid distance conflicts
680        if (getModel().getDistanceConflict() != null) {
681            int bestDistanceConf = 0, currentDistanceConf = 0;
682            for (int idx = 0; idx < current.length; idx++) {
683                if (best[idx] != null) {
684                    bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
685                    for (int x = 0; x < idx; x++) {
686                        if (best[x] != null)
687                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
688                    }
689                }
690                if (current[idx] != null && idx < maxIdx) {
691                    currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
692                    for (int x = 0; x < idx; x++) {
693                        if (current[x] != null)
694                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
695                                    current[idx]);
696                    }
697                }
698            }
699            if (currentDistanceConf < bestDistanceConf)
700                return true;
701            if (bestDistanceConf < currentDistanceConf)
702                return false;
703        }
704
705        // 6. avoid no-time sections
706        int bestNoTime = 0, currentNoTime = 0;
707        for (int idx = 0; idx < current.length; idx++) {
708            if (best[idx] != null) {
709                for (Section section : best[idx].getSections())
710                    if (section.getTime() == null)
711                        bestNoTime++;
712            }
713            if (current[idx] != null && idx < maxIdx) {
714                for (Section section : current[idx].getSections())
715                    if (section.getTime() == null)
716                        currentNoTime++;
717            }
718        }
719        if (currentNoTime < bestNoTime)
720            return true;
721        if (bestNoTime < currentNoTime)
722            return false;
723
724        // 7. balance sections
725        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
726        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
727        for (int idx = 0; idx < current.length; idx++) {
728            if (best[idx] != null) {
729                for (Section section : best[idx].getSections()) {
730                    Subpart subpart = section.getSubpart();
731                    // skip unlimited and single section subparts
732                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
733                        continue;
734                    // average size
735                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
736                    // section is below average
737                    if (section.getLimit() < averageSize)
738                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
739                    bestAltSectionsWithLimit++;
740                }
741            }
742            if (current[idx] != null && idx < maxIdx) {
743                for (Section section : current[idx].getSections()) {
744                    Subpart subpart = section.getSubpart();
745                    // skip unlimited and single section subparts
746                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
747                        continue;
748                    // average size
749                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
750                    // section is below average
751                    if (section.getLimit() < averageSize)
752                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
753                    currentAltSectionsWithLimit++;
754                }
755            }
756        }
757        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
758                : 0.0);
759        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
760                / currentAltSectionsWithLimit : 0.0);
761        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
762            return true;
763        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
764            return false;
765
766        // 8. average penalty sections
767        double bestPenalty = 0.0, currentPenalty = 0.0;
768        for (int idx = 0; idx < current.length; idx++) {
769            if (best[idx] != null) {
770                for (Section section : best[idx].getSections())
771                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
772                if (idx >= maxIdx && best[idx].isCourseRequest())
773                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
774            }
775            if (current[idx] != null && idx < maxIdx) {
776                for (Section section : current[idx].getSections())
777                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
778            }
779        }
780        if (currentPenalty < bestPenalty)
781            return true;
782        if (bestPenalty < currentPenalty)
783            return false;
784
785        return true;
786    }
787
788    @Override
789    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
790        if (enrollemnts == null)
791            return 0.0;
792        double value = 0.0;
793        for (int idx = 0; idx < enrollemnts.length; idx++) {
794            if (enrollemnts[idx] != null)
795                value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx),
796                        getTimeOverlappingConflicts(enrollemnts, idx));
797        }
798        return value;
799    }
800
801    @Override
802    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
803        // 1. alternativity
804        if (e1.getPriority() < e2.getPriority())
805            return -1;
806        if (e1.getPriority() > e2.getPriority())
807            return 1;
808        
809        // 1.5 not available sections
810        int na1 = 0, na2 = 0;
811        for (Section section: e1.getSections())
812            if (section.getLimit() == 0) na1++;
813        for (Section section: e2.getSections())
814            if (section.getLimit() == 0) na2++;
815        if (na1 < na2) return -1;
816        if (na1 > na2) return 1;
817        
818        // 2. maximize number of penalties
819        double p1 = 0, p2 = 0;
820        for (Section section : e1.getSections())
821            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
822        for (Section section : e2.getSections())
823            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
824        if (p1 < p2)
825            return -1;
826        if (p2 < p1)
827            return 1;
828
829        // 3. maximize selection
830        if (e1.isCourseRequest()) {
831            Set<Section> preferred = getPreferredSections(e1.getRequest());
832            if (preferred != null && !preferred.isEmpty()) {
833                int s1 = 0, s2 = 0;
834                for (Section section : e1.getSections())
835                    if (preferred.contains(section))
836                        s1++;
837                for (Section section : e2.getSections())
838                    if (preferred.contains(section))
839                        s2++;
840                if (s2 > s1)
841                    return -1;
842                if (s1 > s2)
843                    return 1;
844            }
845        }
846        
847        // 3.5 maximize preferences
848        if (e1.isCourseRequest()) {
849            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
850            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
851            if (s1 > s2) return -1;
852            if (s2 > s1) return 1;
853        }
854
855        // 4. avoid time overlaps
856        if (getTimesToAvoid() == null) {
857            if (getModel().getTimeOverlaps() != null) {
858                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1);
859                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2);
860                if (o1 < o2)
861                    return -1;
862                if (o2 < o1)
863                    return 1;
864            }
865        } else {
866            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
867                double o1 = 0.0, o2 = 0.0;
868                for (Section s : e1.getSections()) {
869                    if (s.getTime() != null)
870                        for (TimeToAvoid avoid : getTimesToAvoid()) {
871                            if (avoid.priority() > e1.getPriority())
872                                o1 += avoid.overlap(s.getTime());
873                        }
874                }
875                for (Section s : e2.getSections()) {
876                    if (s.getTime() != null)
877                        for (TimeToAvoid avoid : getTimesToAvoid()) {
878                            if (avoid.priority() > e2.getPriority())
879                                o2 += avoid.overlap(s.getTime());
880                        }
881                }
882                if (o1 < o2)
883                    return -1;
884                if (o2 < o1)
885                    return 1;
886            }
887        }
888
889        // 5. avoid distance conflicts
890        if (getModel().getDistanceConflict() != null) {
891            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
892            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
893            if (c1 < c2)
894                return -1;
895            if (c2 < c1)
896                return 1;
897        }
898
899        // 6. avoid no-time sections
900        int n1 = 0, n2 = 0;
901        for (Section section : e1.getSections())
902            if (section.getTime() == null)
903                n1++;
904        for (Section section : e2.getSections())
905            if (section.getTime() == null)
906                n2++;
907        if (n1 < n2)
908            return -1;
909        if (n2 < n1)
910            return 1;
911
912        // 7. balance sections
913        double u1 = 0.0, u2 = 0.0;
914        int a1 = 0, a2 = 0;
915        for (Section section : e1.getSections()) {
916            Subpart subpart = section.getSubpart();
917            // skip unlimited and single section subparts
918            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
919                continue;
920            // average size
921            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
922            // section is below average
923            if (section.getLimit() < averageSize)
924                u1 += (averageSize - section.getLimit()) / averageSize;
925            a1++;
926        }
927        for (Section section : e2.getSections()) {
928            Subpart subpart = section.getSubpart();
929            // skip unlimited and single section subparts
930            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
931                continue;
932            // average size
933            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
934            // section is below average
935            if (section.getLimit() < averageSize)
936                u2 += (averageSize - section.getLimit()) / averageSize;
937            a2++;
938        }
939        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
940        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
941        if (f1 < f2)
942            return -1;
943        if (f2 < f1)
944            return 1;
945
946        // 8. average penalty sections
947        double x1 = 0.0, x2 = 0.0;
948        for (Section section : e1.getSections())
949            x1 += section.getPenalty() / e1.getSections().size();
950        for (Section section : e2.getSections())
951            x2 += section.getPenalty() / e2.getSections().size();
952        if (x1 < x2)
953            return -1;
954        if (x2 < x1)
955            return 1;
956
957        return 0;
958    }
959
960    /**
961     * Time to be avoided.
962     */
963    protected static class TimeToAvoid {
964        private TimeLocation iTime;
965        private double iPenalty;
966        private int iPriority;
967
968        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
969            iTime = time;
970            iPenalty = penalty;
971            iPriority = priority;
972        }
973
974        public int priority() {
975            return iPriority;
976        }
977
978        public double overlap(TimeLocation time) {
979            if (time.hasIntersection(iTime)) {
980                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedDays(iTime))
981                        / (iTime.getNrMeetings() * iTime.getLength());
982            } else {
983                return 0.0;
984            }
985        }
986
987        @Override
988        public String toString() {
989            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
990        }
991    }
992}