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 Tomas Muller<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].getPriority() < current[idx].getPriority())
068                    return 1; // less alternative request assigned
069            } else {
070                if (current[idx] != null && current[idx].getAssignments() != null)
071                    return -1; // higher priority request assigned
072            }
073        }
074
075        // 1. minimize number of penalties
076        double bestPenalties = 0, currentPenalties = 0;
077        for (int idx = 0; idx < current.length; idx++) {
078            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
079                for (Section section : best[idx].getSections())
080                    bestPenalties += iModel.getOverExpected(assignment, section, best[idx].getRequest());
081                for (Section section : current[idx].getSections())
082                    currentPenalties += iModel.getOverExpected(assignment, section, current[idx].getRequest());
083            }
084        }
085        if (currentPenalties < bestPenalties)
086            return -1;
087        if (bestPenalties < currentPenalties)
088            return 1;
089
090        return 0;
091    }
092
093    @Override
094    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
095            Enrollment[] best) {
096        // 0. best priority & alternativity ignoring free time requests
097        int alt = 0;
098        for (int idx = 0; idx < current.length; idx++) {
099            if (isFreeTime(idx))
100                continue;
101            Request request = getRequest(idx);
102            if (idx < maxIdx) {
103                if (best[idx] != null) {
104                    if (current[idx] == null)
105                        return false; // higher priority request assigned
106                    if (best[idx].getPriority() < current[idx].getPriority())
107                        return false; // less alternative request assigned
108                    if (request.isAlternative())
109                        alt--;
110                } else {
111                    if (current[idx] != null)
112                        return true; // higher priority request assigned
113                    if (!request.isAlternative())
114                        alt++;
115                }
116            } else {
117                if (best[idx] != null) {
118                    if (best[idx].getPriority() > 0)
119                        return true; // alternativity can be improved
120                } else {
121                    if (!request.isAlternative() || alt > 0)
122                        return true; // priority can be improved
123                }
124            }
125        }
126
127        // 1. maximize number of penalties
128        int bestPenalties = 0, currentPenalties = 0;
129        for (int idx = 0; idx < current.length; idx++) {
130            if (best[idx] != null) {
131                for (Section section : best[idx].getSections())
132                    bestPenalties += iModel.getOverExpected(assignment, section, best[idx].getRequest());
133            }
134            if (current[idx] != null && idx < maxIdx) {
135                for (Section section : current[idx].getSections())
136                    currentPenalties += iModel.getOverExpected(assignment, section, current[idx].getRequest());
137            }
138        }
139        if (currentPenalties < bestPenalties)
140            return true;
141        if (bestPenalties < currentPenalties)
142            return false;
143
144        return false;
145    }
146
147    @Override
148    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollments) {
149        return 0.0;
150    }
151
152    @Override
153    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
154        // 1. alternativity
155        if (e1.getPriority() < e2.getPriority())
156            return -1;
157        if (e1.getPriority() > e2.getPriority())
158            return 1;
159
160        // 2. maximize number of penalties
161        double p1 = 0, p2 = 0;
162        for (Section section : e1.getSections())
163            p1 += iModel.getOverExpected(assignment, section, e1.getRequest());
164        for (Section section : e2.getSections())
165            p2 += iModel.getOverExpected(assignment, section, e2.getRequest());
166        if (p1 < p2)
167            return -1;
168        if (p2 < p1)
169            return 1;
170
171        return 0;
172    }
173}