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 Tomáš Müller<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 if (iBranchBound != null) 122 iBranchBound.init(solver, "Online..."); 123 } 124 125 /** Use student preference penalties 126 * @return true if student preference penalties are to be used 127 **/ 128 public boolean isUseStudentPrefPenalties() { 129 return iUseStudentPrefPenalties; 130 } 131 132 /** Use online penalties 133 * @return true if online penalties are to be used 134 **/ 135 public boolean isUsePenalties() { 136 return iUsePenalties; 137 } 138 139 /** 140 * Set online sectioning penalties to all sections of all courses of the 141 * given student 142 */ 143 private static void setPenalties(Assignment<Request, Enrollment> assignment, Student student) { 144 for (Request request : student.getRequests()) { 145 if (!(request instanceof CourseRequest)) 146 continue; 147 CourseRequest courseRequest = (CourseRequest) request; 148 for (Course course : courseRequest.getCourses()) { 149 for (Config config : course.getOffering().getConfigs()) { 150 for (Subpart subpart : config.getSubparts()) { 151 for (Section section : subpart.getSections()) { 152 section.setPenalty(section.getOnlineSectioningPenalty(assignment)); 153 } 154 } 155 } 156 } 157 courseRequest.clearCache(); 158 } 159 } 160 161 /** Update online sectioning info after the given student is sectioned 162 * @param assignment current assignment 163 * @param student student in question 164 **/ 165 public void updateSpace(Assignment<Request, Enrollment> assignment, Student student) { 166 for (Request request : student.getRequests()) { 167 if (!(request instanceof CourseRequest)) 168 continue; 169 CourseRequest courseRequest = (CourseRequest) request; 170 Enrollment enrollment = assignment.getValue(courseRequest); 171 if (enrollment == null) 172 return; // not enrolled --> no update 173 for (Section section : enrollment.getSections()) { 174 section.setSpaceHeld(section.getSpaceHeld() - courseRequest.getWeight()); 175 // sLog.debug(" -- space held for "+section+" decreased by 1 (to "+section.getSpaceHeld()+")"); 176 } 177 List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>(); 178 for (Enrollment enrl : courseRequest.values(assignment)) { 179 boolean overlaps = false; 180 for (Request otherRequest : courseRequest.getStudent().getRequests()) { 181 if (otherRequest.equals(courseRequest) || !(otherRequest instanceof CourseRequest)) 182 continue; 183 Enrollment otherErollment = assignment.getValue(otherRequest); 184 if (otherErollment == null) 185 continue; 186 if (enrl.isOverlapping(otherErollment)) { 187 overlaps = true; 188 break; 189 } 190 } 191 if (!overlaps) 192 feasibleEnrollments.add(enrl); 193 } 194 double decrement = courseRequest.getWeight() / feasibleEnrollments.size(); 195 for (Enrollment feasibleEnrollment : feasibleEnrollments) { 196 for (Section section : feasibleEnrollment.getSections()) { 197 section.setSpaceExpected(section.getSpaceExpected() - decrement); 198 // sLog.debug(" -- space expected for "+section+" decreased by "+decrement+" (to "+section.getSpaceExpected()+")"); 199 } 200 } 201 } 202 } 203 204 /** 205 * Branch & bound selection for a student 206 */ 207 @Override 208 public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) { 209 if (iUsePenalties) 210 setPenalties(assignment, student); 211 Selection selection = null; 212 if (iBranchBound != null) 213 selection = iBranchBound.getSelection(assignment, student); 214 if (iUseStudentPrefPenalties) 215 selection = new EpsilonSelection(student, assignment, selection); 216 return selection; 217 } 218 219 /** 220 * Branch & bound selection for a student 221 */ 222 public class EpsilonSelection extends BranchBoundSelection.Selection { 223 private StudentPreferencePenalties iPenalties = null; 224 private Selection iSelection = null; 225 226 /** 227 * Constructor 228 * 229 * @param student 230 * selected student 231 * @param assignment current assignment 232 * @param selection selection 233 */ 234 public EpsilonSelection(Student student, Assignment<Request, Enrollment> assignment, Selection selection) { 235 super(student, assignment); 236 iPenalties = new StudentPreferencePenalties(iDistributionType); 237 iSelection = selection; 238 } 239 240 /** 241 * Execute branch & bound, return the best found schedule for the 242 * selected student. 243 */ 244 @Override 245 public BranchBoundNeighbour select() { 246 BranchBoundNeighbour onlineSelection = null; 247 if (iSelection != null) { 248 onlineSelection = iSelection.select(); 249 if (sDebug) 250 sLog.debug("Online: " + onlineSelection); 251 } 252 BranchBoundNeighbour neighbour = super.select(); 253 if (neighbour != null) 254 return neighbour; 255 if (onlineSelection != null) 256 return onlineSelection; 257 return null; 258 } 259 260 /** Assignment penalty */ 261 @Override 262 protected double getAssignmentPenalty(int i) { 263 return iPenalties.getPenalty(iAssignment[i]) + iDistConfWeight * getDistanceConflicts(i).size(); 264 } 265 266 public boolean isAllowed(int idx, Enrollment enrollment) { 267 if (iSelection == null || iSelection.getBestAssignment() == null 268 || iSelection.getBestAssignment()[idx] == null) 269 return true; 270 double bestPenalty = iSelection.getBestAssignment()[idx].getPenalty(); 271 double limit = (iEpsilon < 0 ? Math.max(0, bestPenalty) : (bestPenalty < 0 ? 1 - iEpsilon : 1 + iEpsilon) 272 * bestPenalty); 273 if (enrollment.getPenalty() > limit) { 274 if (sDebug) 275 sLog.debug(" -- enrollment " + enrollment + " was filtered out " + "(penalty=" 276 + enrollment.getPenalty() + ", best=" + bestPenalty + ", limit=" + limit + ")"); 277 return false; 278 } 279 return true; 280 } 281 282 /** First conflicting enrollment */ 283 @Override 284 public Enrollment firstConflict(int idx, Enrollment enrollment) { 285 Enrollment conflict = super.firstConflict(idx, enrollment); 286 if (conflict != null) 287 return conflict; 288 return (isAllowed(idx, enrollment) ? null : enrollment); 289 } 290 291 /** Student preference penalties 292 * @return student preference penalties 293 **/ 294 public StudentPreferencePenalties getPenalties() { 295 return iPenalties; 296 } 297 } 298}