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