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        // 3.5 maximize preferences
270        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
271        double bestSelectedSections = 0, currentSelectedSections = 0;
272        for (int idx = 0; idx < current.length; idx++) {
273            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
274                bestSelectedSections += best[idx].percentSelectedSameSection();
275                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
276            }
277            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
278                currentSelectedSections += current[idx].percentSelectedSameSection();
279                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
280            }
281        }
282        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1;
283        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1;
284
285        // 4. avoid time overlaps
286        if (getModel().getTimeOverlaps() != null) {
287            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
288            for (int idx = 0; idx < current.length; idx++) {
289                if (best[idx] != null && best[idx].getAssignments() != null) {
290                    for (int x = 0; x < idx; x++) {
291                        if (best[x] != null && best[x].getAssignments() != null)
292                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
293                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
294                            bestTimeOverlaps += getModel().getTimeOverlaps()
295                                    .nrConflicts(
296                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
297                                            best[idx]);
298                    }
299                    for (int x = 0; x < idx; x++) {
300                        if (current[x] != null && current[x].getAssignments() != null)
301                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
302                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
303                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
304                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
305                                    current[idx]);
306                    }
307                }
308            }
309            if (currentTimeOverlaps < bestTimeOverlaps)
310                return -1;
311            if (bestTimeOverlaps < currentTimeOverlaps)
312                return 1;
313        }
314
315        // 5. avoid distance conflicts
316        if (getModel().getDistanceConflict() != null) {
317            int bestDistanceConf = 0, currentDistanceConf = 0;
318            for (int idx = 0; idx < current.length; idx++) {
319                if (best[idx] != null && best[idx].getAssignments() != null) {
320                    for (int x = 0; x < idx; x++) {
321                        if (best[x] != null && best[x].getAssignments() != null)
322                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
323                    }
324                    for (int x = 0; x < idx; x++) {
325                        if (current[x] != null && current[x].getAssignments() != null)
326                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
327                                    current[idx]);
328                    }
329                }
330            }
331            if (currentDistanceConf < bestDistanceConf)
332                return -1;
333            if (bestDistanceConf < currentDistanceConf)
334                return 1;
335        }
336
337        // 6. avoid no-time sections
338        int bestNoTime = 0, currentNoTime = 0;
339        for (int idx = 0; idx < current.length; idx++) {
340            if (best[idx] != null && best[idx].getAssignments() != null) {
341                for (Section section : best[idx].getSections())
342                    if (section.getTime() == null)
343                        bestNoTime++;
344                for (Section section : current[idx].getSections())
345                    if (section.getTime() == null)
346                        currentNoTime++;
347            }
348        }
349        if (currentNoTime < bestNoTime)
350            return -1;
351        if (bestNoTime < currentNoTime)
352            return 1;
353
354        // 7. balance sections
355        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
356        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
357        for (int idx = 0; idx < current.length; idx++) {
358            if (best[idx] != null && best[idx].getAssignments() != null) {
359                for (Section section : best[idx].getSections()) {
360                    Subpart subpart = section.getSubpart();
361                    // skip unlimited and single section subparts
362                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
363                        continue;
364                    // average size
365                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
366                    // section is below average
367                    if (section.getLimit() < averageSize)
368                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
369                    bestAltSectionsWithLimit++;
370                }
371                for (Section section : current[idx].getSections()) {
372                    Subpart subpart = section.getSubpart();
373                    // skip unlimited and single section subparts
374                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
375                        continue;
376                    // average size
377                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
378                    // section is below average
379                    if (section.getLimit() < averageSize)
380                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
381                    currentAltSectionsWithLimit++;
382                }
383            }
384        }
385        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
386                : 0.0);
387        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
388                / currentAltSectionsWithLimit : 0.0);
389        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
390            return -1;
391        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
392            return 1;
393
394        // 8. average penalty sections
395        double bestPenalty = 0.0, currentPenalty = 0.0;
396        for (int idx = 0; idx < current.length; idx++) {
397            if (best[idx] != null && best[idx].getAssignments() != null) {
398                for (Section section : best[idx].getSections())
399                    bestPenalty += section.getPenalty();
400                for (Section section : current[idx].getSections())
401                    currentPenalty += section.getPenalty();
402            }
403        }
404        if (currentPenalty < bestPenalty)
405            return -1;
406        if (bestPenalty < currentPenalty)
407            return 1;
408
409        return 0;
410    }
411
412    @Override
413    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
414            Enrollment[] best) {
415        // 0. best priority & alternativity ignoring free time requests
416        int alt = 0;
417        boolean ft = false;
418        for (int idx = 0; idx < current.length; idx++) {
419            if (isFreeTime(idx)) {
420                ft = true;
421                continue;
422            }
423            Request request = getRequest(idx);
424            if (idx < maxIdx) {
425                if (best[idx] != null) {
426                    if (current[idx] == null)
427                        return false; // higher priority request assigned
428                    if (best[idx].getPriority() < current[idx].getPriority())
429                        return false; // less alternative request assigned
430                    if (request.isAlternative())
431                        alt--;
432                } else {
433                    if (current[idx] != null)
434                        return true; // higher priority request assigned
435                    if (!request.isAlternative())
436                        alt++;
437                }
438            } else {
439                if (best[idx] != null) {
440                    if (best[idx].getPriority() > 0)
441                        return true; // alternativity can be improved
442                } else {
443                    if (!request.isAlternative() || alt > 0)
444                        return true; // priority can be improved
445                }
446            }
447        }
448
449        // 0.5. avoid course time overlaps
450        if (getModel().getTimeOverlaps() != null) {
451            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
452            for (int idx = 0; idx < current.length; idx++) {
453                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
454                    for (int x = 0; x < idx; x++) {
455                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
456                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
457                    }
458                }
459                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
460                    for (int x = 0; x < idx; x++) {
461                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
462                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
463                    }
464                }
465            }
466            if (currentTimeOverlaps < bestTimeOverlaps)
467                return true;
468            if (bestTimeOverlaps < currentTimeOverlaps)
469                return false;
470        }
471
472        // 1. maximize number of penalties
473        double bestPenalties = 0, currentPenalties = 0;
474        for (int idx = 0; idx < current.length; idx++) {
475            if (best[idx] != null) {
476                for (Section section : best[idx].getSections())
477                    bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest());
478            }
479            if (current[idx] != null && idx < maxIdx) {
480                for (Section section : current[idx].getSections())
481                    currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest());
482            }
483        }
484        if (currentPenalties < bestPenalties)
485            return true;
486        if (bestPenalties < currentPenalties)
487            return false;
488
489        // 2. best priority & alternativity including free times
490        if (ft) {
491            alt = 0;
492            for (int idx = 0; idx < current.length; idx++) {
493                Request request = getStudent().getRequests().get(idx);
494                if (idx < maxIdx) {
495                    if (best[idx] != null) {
496                        if (current[idx] == null)
497                            return false; // higher priority request assigned
498                        if (best[idx].getPriority() < current[idx].getPriority())
499                            return false; // less alternative request assigned
500                        if (request.isAlternative())
501                            alt--;
502                    } else {
503                        if (current[idx] != null)
504                            return true; // higher priority request assigned
505                        if (request instanceof CourseRequest && !request.isAlternative())
506                            alt++;
507                    }
508                } else {
509                    if (best[idx] != null) {
510                        if (best[idx].getPriority() > 0)
511                            return true; // alternativity can be improved
512                    } else {
513                        if (!request.isAlternative() || alt > 0)
514                            return true; // priority can be improved
515                    }
516                }
517            }
518        }
519
520        // 3. maximize selection
521        int bestSelected = 0, currentSelected = 0;
522        for (int idx = 0; idx < current.length; idx++) {
523            if (best[idx] != null && best[idx].isCourseRequest()) {
524                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
525                if (preferred != null && !preferred.isEmpty()) {
526                    for (Section section : best[idx].getSections())
527                        if (preferred.contains(section)) {
528                            if (idx < maxIdx)
529                                bestSelected++;
530                        } else if (idx >= maxIdx)
531                            bestSelected--;
532                }
533            }
534            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
535                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
536                if (preferred != null && !preferred.isEmpty()) {
537                    for (Section section : current[idx].getSections())
538                        if (preferred.contains(section))
539                            currentSelected++;
540                }
541            }
542        }
543        if (currentSelected > bestSelected)
544            return true;
545        if (bestSelected > currentSelected)
546            return false;
547
548        // 3.5 maximize preferences
549        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
550        double bestSelectedSections = 0, currentSelectedSections = 0;
551        for (int idx = 0; idx < current.length; idx++) {
552            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
553                bestSelectedSections += best[idx].percentSelectedSameSection();
554                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
555                if (idx >= maxIdx) {
556                    bestSelectedSections -= 1.0;
557                    bestSelectedConfigs -= 1.0;
558                }
559            }
560            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
561                currentSelectedSections += current[idx].percentSelectedSameSection();
562                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
563            }
564        }
565        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
566        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
567        
568        // 4. avoid time overlaps
569        if (getModel().getTimeOverlaps() != null) {
570            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
571            for (int idx = 0; idx < current.length; idx++) {
572                if (best[idx] != null) {
573                    for (int x = 0; x < idx; x++) {
574                        if (best[x] != null)
575                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
576                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
577                            bestTimeOverlaps += getModel().getTimeOverlaps()
578                                    .nrConflicts(
579                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
580                                            best[idx]);
581                    }
582                }
583                if (current[idx] != null && idx < maxIdx) {
584                    for (int x = 0; x < idx; x++) {
585                        if (current[x] != null)
586                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
587                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
588                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
589                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
590                                    current[idx]);
591                    }
592                }
593            }
594            if (currentTimeOverlaps < bestTimeOverlaps)
595                return true;
596            if (bestTimeOverlaps < currentTimeOverlaps)
597                return false;
598        }
599
600        // 5. avoid distance conflicts
601        if (getModel().getDistanceConflict() != null) {
602            int bestDistanceConf = 0, currentDistanceConf = 0;
603            for (int idx = 0; idx < current.length; idx++) {
604                if (best[idx] != null) {
605                    for (int x = 0; x < idx; x++) {
606                        if (best[x] != null)
607                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
608                    }
609                }
610                if (current[idx] != null && idx < maxIdx) {
611                    for (int x = 0; x < idx; x++) {
612                        if (current[x] != null)
613                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
614                                    current[idx]);
615                    }
616                }
617            }
618            if (currentDistanceConf < bestDistanceConf)
619                return true;
620            if (bestDistanceConf < currentDistanceConf)
621                return false;
622        }
623
624        // 6. avoid no-time sections
625        int bestNoTime = 0, currentNoTime = 0;
626        for (int idx = 0; idx < current.length; idx++) {
627            if (best[idx] != null) {
628                for (Section section : best[idx].getSections())
629                    if (section.getTime() == null)
630                        bestNoTime++;
631            }
632            if (current[idx] != null && idx < maxIdx) {
633                for (Section section : current[idx].getSections())
634                    if (section.getTime() == null)
635                        currentNoTime++;
636            }
637        }
638        if (currentNoTime < bestNoTime)
639            return true;
640        if (bestNoTime < currentNoTime)
641            return false;
642
643        // 7. balance sections
644        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
645        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
646        for (int idx = 0; idx < current.length; idx++) {
647            if (best[idx] != null) {
648                for (Section section : best[idx].getSections()) {
649                    Subpart subpart = section.getSubpart();
650                    // skip unlimited and single section subparts
651                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
652                        continue;
653                    // average size
654                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
655                    // section is below average
656                    if (section.getLimit() < averageSize)
657                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
658                    bestAltSectionsWithLimit++;
659                }
660            }
661            if (current[idx] != null && idx < maxIdx) {
662                for (Section section : current[idx].getSections()) {
663                    Subpart subpart = section.getSubpart();
664                    // skip unlimited and single section subparts
665                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
666                        continue;
667                    // average size
668                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
669                    // section is below average
670                    if (section.getLimit() < averageSize)
671                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
672                    currentAltSectionsWithLimit++;
673                }
674            }
675        }
676        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
677                : 0.0);
678        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
679                / currentAltSectionsWithLimit : 0.0);
680        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
681            return true;
682        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
683            return false;
684
685        // 8. average penalty sections
686        double bestPenalty = 0.0, currentPenalty = 0.0;
687        for (int idx = 0; idx < current.length; idx++) {
688            if (best[idx] != null) {
689                for (Section section : best[idx].getSections())
690                    bestPenalty += section.getPenalty();
691                if (idx >= maxIdx && best[idx].isCourseRequest())
692                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
693            }
694            if (current[idx] != null && idx < maxIdx) {
695                for (Section section : current[idx].getSections())
696                    currentPenalty += section.getPenalty();
697            }
698        }
699        if (currentPenalty < bestPenalty)
700            return true;
701        if (bestPenalty < currentPenalty)
702            return false;
703
704        return true;
705    }
706
707    @Override
708    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
709        if (enrollemnts == null)
710            return 0.0;
711        double value = 0.0;
712        for (int idx = 0; idx < enrollemnts.length; idx++) {
713            if (enrollemnts[idx] != null)
714                value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx),
715                        getTimeOverlappingConflicts(enrollemnts, idx));
716        }
717        return value;
718    }
719
720    @Override
721    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
722        // 1. alternativity
723        if (e1.getPriority() < e2.getPriority())
724            return -1;
725        if (e1.getPriority() > e2.getPriority())
726            return 1;
727
728        // 2. maximize number of penalties
729        double p1 = 0, p2 = 0;
730        for (Section section : e1.getSections())
731            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
732        for (Section section : e2.getSections())
733            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
734        if (p1 < p2)
735            return -1;
736        if (p2 < p1)
737            return 1;
738
739        // 3. maximize selection
740        if (e1.isCourseRequest()) {
741            Set<Section> preferred = getPreferredSections(e1.getRequest());
742            if (preferred != null && !preferred.isEmpty()) {
743                int s1 = 0, s2 = 0;
744                for (Section section : e1.getSections())
745                    if (preferred.contains(section))
746                        s1++;
747                for (Section section : e2.getSections())
748                    if (preferred.contains(section))
749                        s2++;
750                if (s2 > s1)
751                    return -1;
752                if (s1 > s2)
753                    return 1;
754            }
755        }
756        
757        // 3.5 maximize preferences
758        if (e1.isCourseRequest()) {
759            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
760            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
761            if (s1 > s2) return -1;
762            if (s2 < s1) return 1;
763        }
764
765        // 4. avoid time overlaps
766        if (getTimesToAvoid() == null) {
767            if (getModel().getTimeOverlaps() != null) {
768                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1);
769                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2);
770                if (o1 < o2)
771                    return -1;
772                if (o2 < o1)
773                    return 1;
774            }
775        } else {
776            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
777                double o1 = 0.0, o2 = 0.0;
778                for (Section s : e1.getSections()) {
779                    if (s.getTime() != null)
780                        for (TimeToAvoid avoid : getTimesToAvoid()) {
781                            if (avoid.priority() > e1.getPriority())
782                                o1 += avoid.overlap(s.getTime());
783                        }
784                }
785                for (Section s : e2.getSections()) {
786                    if (s.getTime() != null)
787                        for (TimeToAvoid avoid : getTimesToAvoid()) {
788                            if (avoid.priority() > e2.getPriority())
789                                o2 += avoid.overlap(s.getTime());
790                        }
791                }
792                if (o1 < o2)
793                    return -1;
794                if (o2 < o1)
795                    return 1;
796            }
797        }
798
799        // 5. avoid distance conflicts
800        if (getModel().getDistanceConflict() != null) {
801            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
802            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
803            if (c1 < c2)
804                return -1;
805            if (c2 < c1)
806                return 1;
807        }
808
809        // 6. avoid no-time sections
810        int n1 = 0, n2 = 0;
811        for (Section section : e1.getSections())
812            if (section.getTime() == null)
813                n1++;
814        for (Section section : e2.getSections())
815            if (section.getTime() == null)
816                n2++;
817        if (n1 < n2)
818            return -1;
819        if (n2 < n1)
820            return 1;
821
822        // 7. balance sections
823        double u1 = 0.0, u2 = 0.0;
824        int a1 = 0, a2 = 0;
825        for (Section section : e1.getSections()) {
826            Subpart subpart = section.getSubpart();
827            // skip unlimited and single section subparts
828            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
829                continue;
830            // average size
831            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
832            // section is below average
833            if (section.getLimit() < averageSize)
834                u1 += (averageSize - section.getLimit()) / averageSize;
835            a1++;
836        }
837        for (Section section : e2.getSections()) {
838            Subpart subpart = section.getSubpart();
839            // skip unlimited and single section subparts
840            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
841                continue;
842            // average size
843            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
844            // section is below average
845            if (section.getLimit() < averageSize)
846                u2 += (averageSize - section.getLimit()) / averageSize;
847            a2++;
848        }
849        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
850        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
851        if (f1 < f2)
852            return -1;
853        if (f2 < f1)
854            return 1;
855
856        // 8. average penalty sections
857        double x1 = 0.0, x2 = 0.0;
858        for (Section section : e1.getSections())
859            x1 += section.getPenalty();
860        for (Section section : e2.getSections())
861            x2 += section.getPenalty();
862        if (x1 < x2)
863            return -1;
864        if (x2 < x1)
865            return 1;
866
867        return 0;
868    }
869
870    /**
871     * Time to be avoided.
872     */
873    protected static class TimeToAvoid {
874        private TimeLocation iTime;
875        private double iPenalty;
876        private int iPriority;
877
878        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
879            iTime = time;
880            iPenalty = penalty;
881            iPriority = priority;
882        }
883
884        public int priority() {
885            return iPriority;
886        }
887
888        public double overlap(TimeLocation time) {
889            if (time.hasIntersection(iTime)) {
890                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedDays(iTime))
891                        / (iTime.getNrMeetings() * iTime.getLength());
892            } else {
893                return 0.0;
894            }
895        }
896
897        @Override
898        public String toString() {
899            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
900        }
901    }
902}