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}