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}