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}