001package org.cpsolver.studentsct.heuristics.selection; 002 003import java.util.ArrayList; 004import java.util.List; 005 006 007import org.apache.log4j.Logger; 008import org.cpsolver.ifs.assignment.Assignment; 009import org.cpsolver.ifs.solver.Solver; 010import org.cpsolver.ifs.util.DataProperties; 011import org.cpsolver.studentsct.StudentPreferencePenalties; 012import org.cpsolver.studentsct.model.Config; 013import org.cpsolver.studentsct.model.Course; 014import org.cpsolver.studentsct.model.CourseRequest; 015import org.cpsolver.studentsct.model.Enrollment; 016import org.cpsolver.studentsct.model.Request; 017import org.cpsolver.studentsct.model.Section; 018import org.cpsolver.studentsct.model.Student; 019import org.cpsolver.studentsct.model.Subpart; 020 021/** 022 * Section given student using branch & bound algorithm with no unassignments 023 * allowed. 024 * 025 * <br> 026 * <br> 027 * Parameters: <br> 028 * <table border='1' summary='Related Solver Parameters'> 029 * <tr> 030 * <th>Parameter</th> 031 * <th>Type</th> 032 * <th>Comment</th> 033 * </tr> 034 * <tr> 035 * <td>Sectioning.UseStudentPreferencePenalties</td> 036 * <td>{@link Boolean}</td> 037 * <td>If true, {@link StudentPreferencePenalties} are used</td> 038 * </tr> 039 * <tr> 040 * <td>Sectioning.Distribution</td> 041 * <td>{@link Integer}</td> 042 * <td>When student preference penalties are used, defines which distribution is 043 * to be used (one of {@link StudentPreferencePenalties#sDistTypePreference}, 044 * {@link StudentPreferencePenalties#sDistTypePreferenceQuadratic}, 045 * {@link StudentPreferencePenalties#sDistTypePreferenceReverse}, 046 * {@link StudentPreferencePenalties#sDistTypeUniform})</td> 047 * </tr> 048 * <tr> 049 * <td>Sectioning.UseOnlinePenalties</td> 050 * <td>{@link Boolean}</td> 051 * <td>If true, online sectioning penalties computed based on held/expected 052 * space are used.</td> 053 * </tr> 054 * <tr> 055 * <td>Sectioning.Epsilon</td> 056 * <td>{@link Double}</td> 057 * <td>When both online penalties and student preference penalties are used: a 058 * solution based on online penalties is computed first, this solution (and the 059 * given epsilon) is then used to setup bounds on online penalties for the 060 * solution that minimizes student preference penalties. Limit on online penalty 061 * is computed as (1+Section.Epsilon) {@link BranchBoundSelection.Selection#getPenalty()}, i.e., only 062 * sections with penalty equal or below this limit can be used -- among these 063 * the solution that minimizes student preference penalties is computed.</td> 064 * </tr> 065 * </table> 066 * <br> 067 * <br> 068 * 069 * @version StudentSct 1.3 (Student Sectioning)<br> 070 * Copyright (C) 2007 - 2014 Tomas Muller<br> 071 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 072 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 073 * <br> 074 * This library is free software; you can redistribute it and/or modify 075 * it under the terms of the GNU Lesser General Public License as 076 * published by the Free Software Foundation; either version 3 of the 077 * License, or (at your option) any later version. <br> 078 * <br> 079 * This library is distributed in the hope that it will be useful, but 080 * WITHOUT ANY WARRANTY; without even the implied warranty of 081 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 082 * Lesser General Public License for more details. <br> 083 * <br> 084 * You should have received a copy of the GNU Lesser General Public 085 * License along with this library; if not see 086 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 087 */ 088 089public class OnlineSelection extends BranchBoundSelection { 090 private static Logger sLog = Logger.getLogger(OnlineSelection.class); 091 private int iDistributionType = -1; 092 private double iEpsilon = 0.05; 093 private boolean iUsePenalties = true; 094 private boolean iUseStudentPrefPenalties = false; 095 private BranchBoundSelection iBranchBound = null; 096 097 /** 098 * Constructor 099 * 100 * @param properties 101 * configuration 102 */ 103 public OnlineSelection(DataProperties properties) { 104 super(properties); 105 iUseStudentPrefPenalties = properties.getPropertyBoolean("Sectioning.UseStudentPreferencePenalties", 106 iUseStudentPrefPenalties); 107 iDistributionType = properties.getPropertyInt("Sectioning.Distribution", 108 StudentPreferencePenalties.sDistTypePreference); 109 iEpsilon = properties.getPropertyDouble("Sectioning.Epsilon", iEpsilon); 110 iUsePenalties = properties.getPropertyBoolean("Sectioning.UseOnlinePenalties", iUsePenalties); 111 if (iUseStudentPrefPenalties && !properties.containsPropery("Sectioning.UseOnlinePenalties")) 112 iUsePenalties = false; 113 if (iUsePenalties || !iUseStudentPrefPenalties) 114 iBranchBound = new BranchBoundSelection(properties); 115 iMinimizePenalty = true; 116 } 117 118 @Override 119 public void init(Solver<Request, Enrollment> solver) { 120 init(solver, "Online..."); 121 } 122 123 /** Use student preference penalties 124 * @return true if student preference penalties are to be used 125 **/ 126 public boolean isUseStudentPrefPenalties() { 127 return iUseStudentPrefPenalties; 128 } 129 130 /** Use online penalties 131 * @return true if online penalties are to be used 132 **/ 133 public boolean isUsePenalties() { 134 return iUsePenalties; 135 } 136 137 /** 138 * Set online sectioning penalties to all sections of all courses of the 139 * given student 140 */ 141 private static void setPenalties(Assignment<Request, Enrollment> assignment, Student student) { 142 for (Request request : student.getRequests()) { 143 if (!(request instanceof CourseRequest)) 144 continue; 145 CourseRequest courseRequest = (CourseRequest) request; 146 for (Course course : courseRequest.getCourses()) { 147 for (Config config : course.getOffering().getConfigs()) { 148 for (Subpart subpart : config.getSubparts()) { 149 for (Section section : subpart.getSections()) { 150 section.setPenalty(section.getOnlineSectioningPenalty(assignment)); 151 } 152 } 153 } 154 } 155 courseRequest.clearCache(); 156 } 157 } 158 159 /** Update online sectioning info after the given student is sectioned 160 * @param assignment current assignment 161 * @param student student in question 162 **/ 163 public void updateSpace(Assignment<Request, Enrollment> assignment, Student student) { 164 for (Request request : student.getRequests()) { 165 if (!(request instanceof CourseRequest)) 166 continue; 167 CourseRequest courseRequest = (CourseRequest) request; 168 Enrollment enrollment = assignment.getValue(courseRequest); 169 if (enrollment == null) 170 return; // not enrolled --> no update 171 for (Section section : enrollment.getSections()) { 172 section.setSpaceHeld(section.getSpaceHeld() - courseRequest.getWeight()); 173 // sLog.debug(" -- space held for "+section+" decreased by 1 (to "+section.getSpaceHeld()+")"); 174 } 175 List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>(); 176 for (Enrollment enrl : courseRequest.values(assignment)) { 177 boolean overlaps = false; 178 for (Request otherRequest : courseRequest.getStudent().getRequests()) { 179 if (otherRequest.equals(courseRequest) || !(otherRequest instanceof CourseRequest)) 180 continue; 181 Enrollment otherErollment = assignment.getValue(otherRequest); 182 if (otherErollment == null) 183 continue; 184 if (enrl.isOverlapping(otherErollment)) { 185 overlaps = true; 186 break; 187 } 188 } 189 if (!overlaps) 190 feasibleEnrollments.add(enrl); 191 } 192 double decrement = courseRequest.getWeight() / feasibleEnrollments.size(); 193 for (Enrollment feasibleEnrollment : feasibleEnrollments) { 194 for (Section section : feasibleEnrollment.getSections()) { 195 section.setSpaceExpected(section.getSpaceExpected() - decrement); 196 // sLog.debug(" -- space expected for "+section+" decreased by "+decrement+" (to "+section.getSpaceExpected()+")"); 197 } 198 } 199 } 200 } 201 202 /** 203 * Branch & bound selection for a student 204 */ 205 @Override 206 public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) { 207 if (iUsePenalties) 208 setPenalties(assignment, student); 209 Selection selection = null; 210 if (iBranchBound != null) 211 selection = iBranchBound.getSelection(assignment, student); 212 if (iUseStudentPrefPenalties) 213 selection = new EpsilonSelection(student, assignment, selection); 214 return selection; 215 } 216 217 /** 218 * Branch & bound selection for a student 219 */ 220 public class EpsilonSelection extends BranchBoundSelection.Selection { 221 private StudentPreferencePenalties iPenalties = null; 222 private Selection iSelection = null; 223 224 /** 225 * Constructor 226 * 227 * @param student 228 * selected student 229 * @param assignment current assignment 230 * @param selection selection 231 */ 232 public EpsilonSelection(Student student, Assignment<Request, Enrollment> assignment, Selection selection) { 233 super(student, assignment); 234 iPenalties = new StudentPreferencePenalties(iDistributionType); 235 iSelection = selection; 236 } 237 238 /** 239 * Execute branch & bound, return the best found schedule for the 240 * selected student. 241 */ 242 @Override 243 public BranchBoundNeighbour select() { 244 BranchBoundNeighbour onlineSelection = null; 245 if (iSelection != null) { 246 onlineSelection = iSelection.select(); 247 if (sDebug) 248 sLog.debug("Online: " + onlineSelection); 249 } 250 BranchBoundNeighbour neighbour = super.select(); 251 if (neighbour != null) 252 return neighbour; 253 if (onlineSelection != null) 254 return onlineSelection; 255 return null; 256 } 257 258 /** Assignment penalty */ 259 @Override 260 protected double getAssignmentPenalty(int i) { 261 return iPenalties.getPenalty(iAssignment[i]) + iDistConfWeight * getDistanceConflicts(i).size(); 262 } 263 264 public boolean isAllowed(int idx, Enrollment enrollment) { 265 if (iSelection == null || iSelection.getBestAssignment() == null 266 || iSelection.getBestAssignment()[idx] == null) 267 return true; 268 double bestPenalty = iSelection.getBestAssignment()[idx].getPenalty(); 269 double limit = (iEpsilon < 0 ? Math.max(0, bestPenalty) : (bestPenalty < 0 ? 1 - iEpsilon : 1 + iEpsilon) 270 * bestPenalty); 271 if (enrollment.getPenalty() > limit) { 272 if (sDebug) 273 sLog.debug(" -- enrollment " + enrollment + " was filtered out " + "(penalty=" 274 + enrollment.getPenalty() + ", best=" + bestPenalty + ", limit=" + limit + ")"); 275 return false; 276 } 277 return true; 278 } 279 280 /** First conflicting enrollment */ 281 @Override 282 public Enrollment firstConflict(int idx, Enrollment enrollment) { 283 Enrollment conflict = super.firstConflict(idx, enrollment); 284 if (conflict != null) 285 return conflict; 286 return (isAllowed(idx, enrollment) ? null : enrollment); 287 } 288 289 /** Student preference penalties 290 * @return student preference penalties 291 **/ 292 public StudentPreferencePenalties getPenalties() { 293 return iPenalties; 294 } 295 } 296}