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}