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