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