001package org.cpsolver.studentsct.online.selection;
002
003import java.util.Hashtable;
004import java.util.Set;
005
006import org.cpsolver.ifs.assignment.Assignment;
007import org.cpsolver.studentsct.model.CourseRequest;
008import org.cpsolver.studentsct.model.Enrollment;
009import org.cpsolver.studentsct.model.FreeTimeRequest;
010import org.cpsolver.studentsct.model.Request;
011import org.cpsolver.studentsct.model.Section;
012import org.cpsolver.studentsct.model.Student;
013import org.cpsolver.studentsct.model.Subpart;
014import org.cpsolver.studentsct.online.OnlineSectioningModel;
015
016/**
017* Equal weighting multi-criteria selection criterion. Much like the {@link OnlineSectioningCriterion}, but
018* course request priorities are ignored. Most complete solution is preferred instead.
019* 
020* @version StudentSct 1.3 (Student Sectioning)<br>
021*          Copyright (C) 2014 Tomas Muller<br>
022*          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
023*          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
024* <br>
025*          This library is free software; you can redistribute it and/or modify
026*          it under the terms of the GNU Lesser General Public License as
027*          published by the Free Software Foundation; either version 3 of the
028*          License, or (at your option) any later version. <br>
029* <br>
030*          This library is distributed in the hope that it will be useful, but
031*          WITHOUT ANY WARRANTY; without even the implied warranty of
032*          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
033*          Lesser General Public License for more details. <br>
034* <br>
035*          You should have received a copy of the GNU Lesser General Public
036*          License along with this library; if not see <a
037*          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
038* 
039*/
040public class EqualWeightCriterion extends OnlineSectioningCriterion {
041
042    public EqualWeightCriterion(Student student, OnlineSectioningModel model,
043            Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) {
044        super(student, model, assignment, preferredSections);
045    }
046
047    @Override
048    public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) {
049        if (best == null)
050            return -1;
051
052        // 0. best number of assigned course requests (including alternativity &
053        // priority)
054        int currentAssignedCourseReq = 0, bestAssignedCourseReq = 0;
055        int currentAssignedRequests = 0, bestAssignedRequests = 0;
056        int currentAssignedPriority = 0, bestAssignedPriority = 0;
057        int currentAssignedAlternativity = 0, bestAssignedAlternativity = 0;
058        for (int idx = 0; idx < current.length; idx++) {
059            if (current[idx] != null && current[idx].getAssignments() != null) {
060                currentAssignedRequests++;
061                if (current[idx].isCourseRequest())
062                    currentAssignedCourseReq++;
063                currentAssignedPriority += current[idx].getPriority() * current[idx].getPriority();
064                currentAssignedAlternativity += (current[idx].getRequest().isAlternative() ? 1 : 0);
065            }
066            if (best[idx] != null && best[idx].getAssignments() != null) {
067                bestAssignedRequests++;
068                if (best[idx].isCourseRequest())
069                    bestAssignedCourseReq++;
070                bestAssignedPriority += best[idx].getPriority() * best[idx].getPriority();
071                bestAssignedAlternativity += (best[idx].getRequest().isAlternative() ? 1 : 0);
072            }
073        }
074        if (currentAssignedCourseReq > bestAssignedCourseReq)
075            return -1;
076        if (bestAssignedCourseReq > currentAssignedCourseReq)
077            return 1;
078        if (currentAssignedPriority < bestAssignedPriority)
079            return -1;
080        if (bestAssignedPriority < currentAssignedPriority)
081            return 1;
082        if (currentAssignedAlternativity < bestAssignedAlternativity)
083            return -1;
084        if (bestAssignedAlternativity < currentAssignedAlternativity)
085            return 1;
086
087        // 0.5. avoid course overlaps
088        if (getModel().getTimeOverlaps() != null) {
089            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
090            for (int idx = 0; idx < current.length; idx++) {
091                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest) {
092                    for (int x = 0; x < idx; x++) {
093                        if (best[x] != null && best[x].getAssignments() != null
094                                        && best[x].getRequest() instanceof CourseRequest)
095                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
096                    }
097                }
098                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest) {
099                    for (int x = 0; x < idx; x++) {
100                        if (current[x] != null && current[x].getAssignments() != null
101                                && current[x].getRequest() instanceof CourseRequest)
102                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
103                    }
104                }
105            }
106            if (currentTimeOverlaps < bestTimeOverlaps)
107                return -1;
108            if (bestTimeOverlaps < currentTimeOverlaps)
109                return 1;
110        }
111
112        // 1. minimize number of penalties
113        double bestPenalties = 0, currentPenalties = 0;
114        for (int idx = 0; idx < current.length; idx++) {
115            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
116                for (Section section : best[idx].getSections())
117                    bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest());
118            }
119            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
120                for (Section section : current[idx].getSections())
121                    currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest());
122            }
123        }
124        if (currentPenalties < bestPenalties)
125            return -1;
126        if (bestPenalties < currentPenalties)
127            return 1;
128
129        // 2. best number of assigned requests (including free time requests)
130        if (currentAssignedRequests > bestAssignedRequests)
131            return -1;
132        if (bestAssignedRequests > currentAssignedRequests)
133            return 1;
134
135        // 3. maximize selection
136        int bestSelected = 0, currentSelected = 0;
137        for (int idx = 0; idx < current.length; idx++) {
138            Set<Section> preferred = getPreferredSections(getRequest(idx));
139            if (preferred != null && !preferred.isEmpty()) {
140                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
141                    for (Section section : best[idx].getSections())
142                        if (preferred.contains(section))
143                            bestSelected++;
144                }
145                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
146                    for (Section section : current[idx].getSections())
147                        if (preferred.contains(section))
148                            currentSelected++;
149                }
150            }
151        }
152        if (currentSelected > bestSelected)
153            return -1;
154        if (bestSelected > currentSelected)
155            return 1;
156
157        // 4. avoid time overlaps
158        if (getModel().getTimeOverlaps() != null) {
159            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
160            for (int idx = 0; idx < current.length; idx++) {
161                if (best[idx] != null && best[idx].getAssignments() != null) {
162                    for (int x = 0; x < idx; x++) {
163                        if (best[x] != null && best[x].getAssignments() != null)
164                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
165                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
166                            bestTimeOverlaps += getModel().getTimeOverlaps()
167                                    .nrConflicts(
168                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
169                                            best[idx]);
170                    }
171                }
172                if (current[idx] != null && current[idx].getAssignments() != null) {
173                    for (int x = 0; x < idx; x++) {
174                        if (current[x] != null && current[x].getAssignments() != null)
175                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
176                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
177                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
178                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
179                                    current[idx]);
180                    }
181                }
182            }
183            if (currentTimeOverlaps < bestTimeOverlaps)
184                return -1;
185            if (bestTimeOverlaps < currentTimeOverlaps)
186                return 1;
187        }
188
189        // 5. avoid distance conflicts
190        if (getModel().getDistanceConflict() != null) {
191            int bestDistanceConf = 0, currentDistanceConf = 0;
192            for (int idx = 0; idx < current.length; idx++) {
193                if (best[idx] != null && best[idx].getAssignments() != null) {
194                    for (int x = 0; x < idx; x++) {
195                        if (best[x] != null && best[x].getAssignments() != null)
196                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
197                    }
198                }
199                if (current[idx] != null && current[idx].getAssignments() != null) {
200                    for (int x = 0; x < idx; x++) {
201                        if (current[x] != null && current[x].getAssignments() != null)
202                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
203                                    current[idx]);
204                    }
205                }
206            }
207            if (currentDistanceConf < bestDistanceConf)
208                return -1;
209            if (bestDistanceConf < currentDistanceConf)
210                return 1;
211        }
212
213        // 6. avoid no-time sections
214        int bestNoTime = 0, currentNoTime = 0;
215        for (int idx = 0; idx < current.length; idx++) {
216            if (best[idx] != null && best[idx].getAssignments() != null) {
217                for (Section section : best[idx].getSections())
218                    if (section.getTime() == null)
219                        bestNoTime++;
220            }
221            if (current[idx] != null && current[idx].getAssignments() != null) {
222                for (Section section : current[idx].getSections())
223                    if (section.getTime() == null)
224                        currentNoTime++;
225            }
226        }
227        if (currentNoTime < bestNoTime)
228            return -1;
229        if (bestNoTime < currentNoTime)
230            return 1;
231
232        // 7. balance sections
233        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
234        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
235        for (int idx = 0; idx < current.length; idx++) {
236            if (best[idx] != null && best[idx].getAssignments() != null) {
237                for (Section section : best[idx].getSections()) {
238                    Subpart subpart = section.getSubpart();
239                    // skip unlimited and single section subparts
240                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
241                        continue;
242                    // average size
243                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
244                    // section is below average
245                    if (section.getLimit() < averageSize)
246                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
247                    bestAltSectionsWithLimit++;
248                }
249            }
250            if (current[idx] != null && current[idx].getAssignments() != null) {
251                for (Section section : current[idx].getSections()) {
252                    Subpart subpart = section.getSubpart();
253                    // skip unlimited and single section subparts
254                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
255                        continue;
256                    // average size
257                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
258                    // section is below average
259                    if (section.getLimit() < averageSize)
260                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
261                    currentAltSectionsWithLimit++;
262                }
263            }
264        }
265        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
266                : 0.0);
267        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
268                / currentAltSectionsWithLimit : 0.0);
269        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
270            return -1;
271        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
272            return 1;
273
274        // 8. average penalty sections
275        double bestPenalty = 0.0, currentPenalty = 0.0;
276        for (int idx = 0; idx < current.length; idx++) {
277            if (best[idx] != null && best[idx].getAssignments() != null) {
278                for (Section section : best[idx].getSections())
279                    bestPenalty += section.getPenalty();
280            }
281            if (current[idx] != null && current[idx].getAssignments() != null) {
282                for (Section section : current[idx].getSections())
283                    currentPenalty += section.getPenalty();
284            }
285        }
286        if (currentPenalty < bestPenalty)
287            return -1;
288        if (bestPenalty < currentPenalty)
289            return 1;
290
291        return 0;
292    }
293
294    @Override
295    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
296            Enrollment[] best) {
297        // 0. best number of assigned course requests (including alternativity &
298        // priority)
299        int currentAssignedCourseReq = 0, bestAssignedCourseReq = 0;
300        int currentAssignedRequests = 0, bestAssignedRequests = 0;
301        int currentAssignedPriority = 0, bestAssignedPriority = 0;
302        int currentAssignedAlternativity = 0, bestAssignedAlternativity = 0;
303        int alt = 0;
304        for (int idx = 0; idx < current.length; idx++) {
305            if (idx < maxIdx) {
306                if (current[idx] != null && current[idx].getAssignments() != null) {
307                    currentAssignedRequests++;
308                    if (current[idx].isCourseRequest())
309                        currentAssignedCourseReq++;
310                    currentAssignedPriority += current[idx].getPriority() * current[idx].getPriority();
311                    currentAssignedAlternativity += (current[idx].getRequest().isAlternative() ? 1 : 0);
312                } else if (!isFreeTime(idx) && !getRequest(idx).isAlternative()) {
313                    alt++;
314                }
315            } else {
316                if (!getRequest(idx).isAlternative()) {
317                    currentAssignedRequests++;
318                    if (!isFreeTime(idx))
319                        currentAssignedCourseReq++;
320                } else if (alt > 0) {
321                    currentAssignedRequests++;
322                    currentAssignedCourseReq++;
323                    alt--;
324                    currentAssignedAlternativity++;
325                }
326            }
327            if (best[idx] != null && best[idx].getAssignments() != null) {
328                bestAssignedRequests++;
329                if (best[idx].isCourseRequest())
330                    bestAssignedCourseReq++;
331                bestAssignedPriority += best[idx].getPriority() * best[idx].getPriority();
332                bestAssignedAlternativity += (best[idx].getRequest().isAlternative() ? 1 : 0);
333            }
334        }
335        if (currentAssignedCourseReq > bestAssignedCourseReq)
336            return true;
337        if (bestAssignedCourseReq > currentAssignedCourseReq)
338            return false;
339        if (currentAssignedPriority < bestAssignedPriority)
340            return true;
341        if (bestAssignedPriority < currentAssignedPriority)
342            return false;
343        if (currentAssignedAlternativity < bestAssignedAlternativity)
344            return true;
345        if (bestAssignedAlternativity < currentAssignedAlternativity)
346            return false;
347
348        // 0.5. avoid course time overlaps
349        if (getModel().getTimeOverlaps() != null) {
350            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
351            for (int idx = 0; idx < current.length; idx++) {
352                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
353                    for (int x = 0; x < idx; x++) {
354                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
355                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
356                    }
357                }
358                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
359                    for (int x = 0; x < idx; x++) {
360                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
361                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
362                    }
363                }
364            }
365            if (currentTimeOverlaps < bestTimeOverlaps)
366                return true;
367            if (bestTimeOverlaps < currentTimeOverlaps)
368                return false;
369        }
370
371        // 1. maximize number of penalties
372        double bestPenalties = 0, currentPenalties = 0;
373        for (int idx = 0; idx < current.length; idx++) {
374            if (best[idx] != null) {
375                for (Section section : best[idx].getSections())
376                    bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest());
377            }
378            if (current[idx] != null && idx < maxIdx) {
379                for (Section section : current[idx].getSections())
380                    currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest());
381            }
382        }
383        if (currentPenalties < bestPenalties)
384            return true;
385        if (bestPenalties < currentPenalties)
386            return false;
387
388        // 2. best number of assigned requests (including free time requests)
389        if (currentAssignedRequests > bestAssignedRequests)
390            return true;
391        if (bestAssignedRequests > currentAssignedRequests)
392            return false;
393
394        // 3. maximize selection
395        int bestSelected = 0, currentSelected = 0;
396        for (int idx = 0; idx < current.length; idx++) {
397            if (best[idx] != null && best[idx].isCourseRequest()) {
398                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
399                if (preferred != null && !preferred.isEmpty()) {
400                    for (Section section : best[idx].getSections())
401                        if (preferred.contains(section)) {
402                            if (idx < maxIdx)
403                                bestSelected++;
404                        } else if (idx >= maxIdx)
405                            bestSelected--;
406                }
407            }
408            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
409                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
410                if (preferred != null && !preferred.isEmpty()) {
411                    for (Section section : current[idx].getSections())
412                        if (preferred.contains(section))
413                            currentSelected++;
414                }
415            }
416        }
417        if (currentSelected > bestSelected)
418            return true;
419        if (bestSelected > currentSelected)
420            return false;
421
422        // 4. avoid time overlaps
423        if (getModel().getTimeOverlaps() != null) {
424            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
425            for (int idx = 0; idx < current.length; idx++) {
426                if (best[idx] != null) {
427                    for (int x = 0; x < idx; x++) {
428                        if (best[x] != null)
429                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
430                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
431                            bestTimeOverlaps += getModel().getTimeOverlaps()
432                                    .nrConflicts(
433                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
434                                            best[idx]);
435                    }
436                }
437                if (current[idx] != null && idx < maxIdx) {
438                    for (int x = 0; x < idx; x++) {
439                        if (current[x] != null)
440                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
441                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
442                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
443                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
444                                    current[idx]);
445                    }
446                }
447            }
448            if (currentTimeOverlaps < bestTimeOverlaps)
449                return true;
450            if (bestTimeOverlaps < currentTimeOverlaps)
451                return false;
452        }
453
454        // 5. avoid distance conflicts
455        if (getModel().getDistanceConflict() != null) {
456            int bestDistanceConf = 0, currentDistanceConf = 0;
457            for (int idx = 0; idx < current.length; idx++) {
458                if (best[idx] != null) {
459                    for (int x = 0; x < idx; x++) {
460                        if (best[x] != null)
461                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
462                    }
463                }
464                if (current[idx] != null && idx < maxIdx) {
465                    for (int x = 0; x < idx; x++) {
466                        if (current[x] != null)
467                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
468                                    current[idx]);
469                    }
470                }
471            }
472            if (currentDistanceConf < bestDistanceConf)
473                return true;
474            if (bestDistanceConf < currentDistanceConf)
475                return false;
476        }
477
478        // 6. avoid no-time sections
479        int bestNoTime = 0, currentNoTime = 0;
480        for (int idx = 0; idx < current.length; idx++) {
481            if (best[idx] != null) {
482                for (Section section : best[idx].getSections())
483                    if (section.getTime() == null)
484                        bestNoTime++;
485            }
486            if (current[idx] != null && idx < maxIdx) {
487                for (Section section : current[idx].getSections())
488                    if (section.getTime() == null)
489                        currentNoTime++;
490            }
491        }
492        if (currentNoTime < bestNoTime)
493            return true;
494        if (bestNoTime < currentNoTime)
495            return false;
496
497        // 7. balance sections
498        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
499        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
500        for (int idx = 0; idx < current.length; idx++) {
501            if (best[idx] != null) {
502                for (Section section : best[idx].getSections()) {
503                    Subpart subpart = section.getSubpart();
504                    // skip unlimited and single section subparts
505                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
506                        continue;
507                    // average size
508                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
509                    // section is below average
510                    if (section.getLimit() < averageSize)
511                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
512                    bestAltSectionsWithLimit++;
513                }
514            }
515            if (current[idx] != null && idx < maxIdx) {
516                for (Section section : current[idx].getSections()) {
517                    Subpart subpart = section.getSubpart();
518                    // skip unlimited and single section subparts
519                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
520                        continue;
521                    // average size
522                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
523                    // section is below average
524                    if (section.getLimit() < averageSize)
525                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
526                    currentAltSectionsWithLimit++;
527                }
528            }
529        }
530        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
531                : 0.0);
532        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
533                / currentAltSectionsWithLimit : 0.0);
534        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
535            return true;
536        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
537            return false;
538
539        // 8. average penalty sections
540        double bestPenalty = 0.0, currentPenalty = 0.0;
541        for (int idx = 0; idx < current.length; idx++) {
542            if (best[idx] != null) {
543                for (Section section : best[idx].getSections())
544                    bestPenalty += section.getPenalty();
545                if (idx >= maxIdx && best[idx].isCourseRequest())
546                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
547            }
548            if (current[idx] != null && idx < maxIdx) {
549                for (Section section : current[idx].getSections())
550                    currentPenalty += section.getPenalty();
551            }
552        }
553        if (currentPenalty < bestPenalty)
554            return true;
555        if (bestPenalty < currentPenalty)
556            return false;
557
558        return true;
559    }
560}