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