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