    001package org.cpsolver.studentsct.online.selection;
    002
    003import org.cpsolver.ifs.assignment.Assignment;
    004import org.cpsolver.studentsct.model.Enrollment;
    005import org.cpsolver.studentsct.model.FreeTimeRequest;
    006import org.cpsolver.studentsct.model.Request;
    007import org.cpsolver.studentsct.model.Section;
    008import org.cpsolver.studentsct.model.Student;
    009import org.cpsolver.studentsct.online.OnlineSectioningModel;
    010import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionCriterion;
    011
    012/**
    013 * A simple weighting multi-criteria selection criterion only optimizing on the
    014 * over-expected penalty. This criterion is used to find a bound on the
    015 * over-expected penalty to ensure no suggestion given to the student.
    016 *
    017 * @version StudentSct 1.3 (Student Sectioning)<br>
    018 *          Copyright (C) 2014 Tomáš Müller<br>
    019 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    020 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    021 * <br>
    022 *          This library is free software; you can redistribute it and/or modify
    023 *          it under the terms of the GNU Lesser General Public License as
    024 *          published by the Free Software Foundation; either version 3 of the
    025 *          License, or (at your option) any later version. <br>
    026 * <br>
    027 *          This library is distributed in the hope that it will be useful, but
    028 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    029 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    030 *          Lesser General Public License for more details. <br>
    031 * <br>
    032 *          You should have received a copy of the GNU Lesser General Public
    033 *          License along with this library; if not see <a
    034 *          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
    035 *
    036 */
    037public class BestPenaltyCriterion implements SelectionCriterion {
    038    private Student iStudent;
    039    private OnlineSectioningModel iModel;
    040
    041    public BestPenaltyCriterion(Student student, OnlineSectioningModel model) {
    042        iStudent = student;
    043        iModel = model;
    044    }
    045
    046    private Request getRequest(int index) {
    047        return (index < 0 || index >= iStudent.getRequests().size() ? null : iStudent.getRequests().get(index));
    048    }
    049
    050    private boolean isFreeTime(int index) {
    051        Request r = getRequest(index);
    052        return r != null && r instanceof FreeTimeRequest;
    053    }
    054
    055    @Override
    056    public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) {
    057        if (best == null)
    058            return -1;
    059
    060        // 0. best priority & alternativity ignoring free time requests
    061        for (int idx = 0; idx < current.length; idx++) {
    062            if (isFreeTime(idx))
    063                continue;
    064            if (best[idx] != null && best[idx].getAssignments() != null) {
    065                if (current[idx] == null || current[idx].getSections() == null)
    066                    return 1; // higher priority request assigned
    067                if (best[idx].getTruePriority() < current[idx].getTruePriority())
    068                    return 1; // less alternative request assigned
    069                if (best[idx].getTruePriority() > current[idx].getTruePriority())
    070                    return -1; // more alternative request assigned
    071            } else {
    072                if (current[idx] != null && current[idx].getAssignments() != null)
    073                    return -1; // higher priority request assigned
    074            }
    075        }
    076
    077        // 1. minimize number of penalties
    078        double bestPenalties = 0, currentPenalties = 0;
    079        for (int idx = 0; idx < current.length; idx++) {
    080            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
    081                for (Section section : best[idx].getSections())
    082                    bestPenalties += iModel.getOverExpected(assignment, best, idx, section, best[idx].getRequest());
    083                for (Section section : current[idx].getSections())
    084                    currentPenalties += iModel.getOverExpected(assignment, current, idx, section, current[idx].getRequest());
    085            }
    086        }
    087        if (currentPenalties < bestPenalties)
    088            return -1;
    089        if (bestPenalties < currentPenalties)
    090            return 1;
    091
    092        return 0;
    093    }
    094
    095    @Override
    096    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
    097            Enrollment[] best) {
    098        // 0. best priority & alternativity ignoring free time requests
    099        int alt = 0;
    100        for (int idx = 0; idx < current.length; idx++) {
    101            if (isFreeTime(idx))
    102                continue;
    103            Request request = getRequest(idx);
    104            if (idx < maxIdx) {
    105                if (best[idx] != null) {
    106                    if (current[idx] == null)
    107                        return false; // higher priority request assigned
    108                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
    109                        return false; // less alternative request assigned
    110                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
    111                        return true; // more alternative request assigned
    112                    if (request.isAlternative())
    113                        alt--;
    114                } else {
    115                    if (current[idx] != null)
    116                        return true; // higher priority request assigned
    117                    if (!request.isAlternative())
    118                        alt++;
    119                }
    120            } else {
    121                if (best[idx] != null) {
    122                    if (best[idx].getTruePriority() > 0)
    123                        return true; // alternativity can be improved
    124                } else {
    125                    if (!request.isAlternative() || alt > 0)
    126                        return true; // priority can be improved
    127                }
    128            }
    129        }
    130
    131        // 1. maximize number of penalties
    132        double bestPenalties = 0, currentPenalties = 0;
    133        for (int idx = 0; idx < current.length; idx++) {
    134            if (best[idx] != null) {
    135                for (Section section : best[idx].getSections())
    136                    bestPenalties += iModel.getOverExpected(assignment, best, idx, section, best[idx].getRequest());
    137            }
    138            if (current[idx] != null && idx < maxIdx) {
    139                for (Section section : current[idx].getSections())
    140                    currentPenalties += iModel.getOverExpected(assignment, current, idx, section, current[idx].getRequest());
    141            }
    142        }
    143        if (currentPenalties < bestPenalties)
    144            return true;
    145        if (bestPenalties < currentPenalties)
    146            return false;
    147
    148        return false;
    149    }
    150
    151    @Override
    152    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollments) {
    153        return 0.0;
    154    }
    155
    156    @Override
    157    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
    158        // 1. alternativity
    159        if (e1.getTruePriority() < e2.getTruePriority())
    160            return -1;
    161        if (e1.getTruePriority() > e2.getTruePriority())
    162            return 1;
    163
    164        // 2. maximize number of penalties
    165        double p1 = 0, p2 = 0;
    166        for (Section section : e1.getSections())
    167            p1 += iModel.getOverExpected(assignment, section, e1.getRequest());
    168        for (Section section : e2.getSections())
    169            p2 += iModel.getOverExpected(assignment, section, e2.getRequest());
    170        if (p1 < p2)
    171            return -1;
    172        if (p2 < p1)
    173            return 1;
    174
    175        return 0;
    176    }
    177}