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