001package org.cpsolver.studentsct.heuristics.selection; 002 003import java.util.ArrayList; 004import java.util.Collections; 005import java.util.HashSet; 006import java.util.Iterator; 007import java.util.LinkedList; 008import java.util.List; 009import java.util.Queue; 010import java.util.Set; 011 012import org.cpsolver.ifs.assignment.Assignment; 013import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection; 014import org.cpsolver.ifs.heuristics.NeighbourSelection; 015import org.cpsolver.ifs.heuristics.RouletteWheelSelection; 016import org.cpsolver.ifs.model.Neighbour; 017import org.cpsolver.ifs.model.SimpleNeighbour; 018import org.cpsolver.ifs.solution.Solution; 019import org.cpsolver.ifs.solver.Solver; 020import org.cpsolver.ifs.util.DataProperties; 021import org.cpsolver.ifs.util.Progress; 022import org.cpsolver.ifs.util.ToolBox; 023import org.cpsolver.studentsct.StudentSectioningModel; 024import org.cpsolver.studentsct.model.Course; 025import org.cpsolver.studentsct.model.CourseRequest; 026import org.cpsolver.studentsct.model.Enrollment; 027import org.cpsolver.studentsct.model.Offering; 028import org.cpsolver.studentsct.model.Request; 029import org.cpsolver.studentsct.model.RequestGroup; 030import org.cpsolver.studentsct.model.Section; 031import org.cpsolver.studentsct.model.Subpart; 032 033/** 034 * Shuffle students along request groups. This selection tries to improve the 035 * ability to keep students of the same request group together by moving students 036 * of a request group that are spread over multiple sections into a single section 037 * or into a fewer number of sections. 038 * 039 * @version StudentSct 1.3 (Student Sectioning)<br> 040 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 041 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 042 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 043 * <br> 044 * This library is free software; you can redistribute it and/or modify 045 * it under the terms of the GNU Lesser General Public License as 046 * published by the Free Software Foundation; either version 3 of the 047 * License, or (at your option) any later version. <br> 048 * <br> 049 * This library is distributed in the hope that it will be useful, but 050 * WITHOUT ANY WARRANTY; without even the implied warranty of 051 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 052 * Lesser General Public License for more details. <br> 053 * <br> 054 * You should have received a copy of the GNU Lesser General Public 055 * License along with this library; if not see 056 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 057 */ 058public class ShuffleStudentsSelection implements NeighbourSelection<Request, Enrollment> { 059 private Queue<Shuffle> iQueue = null; 060 private ShuffleBacktrackNeighbourSelection iBacktrack; 061 062 /** 063 * Constructor 064 * @param properties the selection has no properties at the moment 065 */ 066 public ShuffleStudentsSelection(DataProperties properties) { 067 } 068 069 @Override 070 public void init(Solver<Request, Enrollment> solver) { 071 StudentSectioningModel model = (StudentSectioningModel)solver.currentSolution().getModel(); 072 iQueue = new LinkedList<Shuffle>(); 073 Assignment<Request, Enrollment> assignment = solver.currentSolution().getAssignment(); 074 // Check all request groups that have a spread < 1.0 075 RouletteWheelSelection<RequestGroup> groups = new RouletteWheelSelection<RequestGroup>(); 076 for (Offering offering: model.getOfferings()) { 077 if (offering.isDummy()) continue; 078 for (Course course: offering.getCourses()) { 079 for (RequestGroup group: course.getRequestGroups()) { 080 double spread = group.getAverageSpread(solver.currentSolution().getAssignment()); 081 if (spread >= 1.0) continue; 082 groups.add(group, 1.0 - spread); 083 } 084 } 085 } 086 // If there are some, pick one randomly (using roulette wheel selection) 087 if (groups.hasMoreElements()) { 088 RequestGroup group = groups.nextElement(); 089 RouletteWheelSelection<Subpart> subparts = new RouletteWheelSelection<Subpart>(); 090 for (CourseRequest cr: group.getRequests()) { 091 Enrollment e = assignment.getValue(cr); 092 if (e != null) 093 for (Section section: e.getSections()) 094 if (group.getSectionSpread(assignment, section) < 1.0) 095 subparts.addExisting(section.getSubpart(), 1.0); 096 } 097 if (subparts.hasMoreElements()) { 098 // Pick a subpart that has sections with a section spread < 1.0 099 Subpart subpart = subparts.nextElement(); 100 RouletteWheelSelection<Section> sections = new RouletteWheelSelection<Section>(); 101 section: for (Section section: subpart.getSections()) { 102 // Only take sections that all requests can use 103 for (CourseRequest cr: group.getRequests()) { 104 boolean match = false; 105 for (Enrollment e: cr.values(assignment)) 106 if (e.getSections().contains(section)) { match = true; break; } 107 if (!match) continue section; 108 } 109 // Take sections with conflicts with lower probability 110 int nrConflicts = 0; 111 if (!section.isAllowOverlap()) 112 requests: for (CourseRequest cr: group.getRequests()) { 113 for (Request r: cr.getStudent().getRequests()) { 114 if (r.equals(cr)) continue; 115 Enrollment e = assignment.getValue(r); 116 if (e != null && !e.isAllowOverlap() && section.isOverlapping(e.getSections())) { 117 nrConflicts++; continue requests; 118 } 119 } 120 } 121 sections.add(section, 1 + group.getRequests().size() - nrConflicts); 122 } 123 Set<Section> filter = new HashSet<Section>(); double space = 0.0; 124 // Pick enough sections 125 while (sections.hasMoreElements()) { 126 Section section = sections.nextElement(); 127 if (filter.add(section)) { 128 if (section.getLimit() < 0) break; 129 space += section.getLimit(); 130 } 131 if (space >= group.getTotalWeight()) break; 132 } 133 // Add all requests that should be moved into the queue 134 for (CourseRequest cr: group.getRequests()) { 135 Shuffle shuffle = new Shuffle(group, cr, filter); 136 Enrollment e = assignment.getValue(cr); 137 if (e != null && shuffle.matchFilter(e)) continue; 138 iQueue.add(shuffle); 139 } 140 } else { 141 // No subpart -> no section filter 142 for (CourseRequest cr: group.getRequests()) 143 iQueue.add(new Shuffle(group, cr, null)); 144 } 145 } 146 // Shuffle the queue 147 Collections.shuffle((LinkedList<Shuffle>)iQueue); 148 // Initialize the backtrack selection, if needed 149 if (iBacktrack == null) { 150 try { 151 iBacktrack = new ShuffleBacktrackNeighbourSelection(solver.getProperties()); 152 iBacktrack.init(solver); 153 } catch (Exception e) { 154 throw new RuntimeException(e.getMessage(), e); 155 } 156 } 157 // Change progress 158 Progress.getInstance(solver.currentSolution().getModel()).setPhase("Shuffling students along request groups...", iQueue.size()); 159 } 160 161 @Override 162 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 163 Shuffle shuffle = null; 164 while ((shuffle = iQueue.poll()) != null) { 165 Progress.getInstance(solution.getModel()).incProgress(); 166 // Take an item from the queue, try backtrack first 167 Neighbour<Request, Enrollment> n = iBacktrack.selectNeighbour(solution, shuffle); 168 if (n != null) return n; 169 // If fails, just assign the request randomly and hope for the best 170 List<Enrollment> adepts = new ArrayList<Enrollment>(); 171 for (Enrollment e: shuffle.getRequest().values(solution.getAssignment())) { 172 if (shuffle.matchFilter(e)) adepts.add(e); 173 } 174 if (!adepts.isEmpty()) { 175 return new SimpleNeighbour<Request, Enrollment>(shuffle.getRequest(), ToolBox.random(adepts)); 176 } 177 } 178 return null; 179 } 180 181 /** 182 * One item to be shuffled 183 */ 184 private static class Shuffle { 185 RequestGroup iGroup; 186 CourseRequest iRequest; 187 Set<Section> iFilter; 188 189 /** 190 * Constructor 191 * @param group selected request group 192 * @param request selected request of a request group 193 * @param filter section filter (if used, only enrollments that contain one of the given sections can be used) 194 */ 195 Shuffle(RequestGroup group, CourseRequest request, Set<Section> filter) { 196 iGroup = group; 197 iRequest = request; 198 iFilter = filter; 199 } 200 201 /** 202 * Selected request group 203 * @return a request group 204 */ 205 public CourseRequest getRequest() { return iRequest; } 206 207 /** 208 * Is there a section filter set? 209 * @return true, if only enrollments with matching sections can be used 210 */ 211 public boolean hasFilter() { return iFilter != null && !iFilter.isEmpty(); } 212 213 /** 214 * Is the given request matching this object? 215 * @param variable a request 216 * @return true if the given variable is a course request for a matching course 217 */ 218 public boolean matchRequest(Request variable) { 219 return variable instanceof CourseRequest && ((CourseRequest)variable).getCourses().contains(iGroup.getCourse()); 220 } 221 222 /** 223 * Is the given enrollment matching the section filter 224 * @param e an enrollment 225 * @return true if the enrollment contains at least one section of the filter 226 */ 227 public boolean matchFilter(Enrollment e) { 228 if (iFilter == null || iFilter.isEmpty()) return true; 229 for (Section s: e.getSections()) 230 if (iFilter.contains(s)) return true; 231 return false; 232 } 233 } 234 235 /** 236 * A special version of the {@link BacktrackNeighbourSelection} that filters the enrollments with the 237 * provided section filter. 238 * 239 */ 240 public static class ShuffleBacktrackNeighbourSelection extends BacktrackNeighbourSelection<Request, Enrollment> { 241 242 /** 243 * Constructor 244 * @param properties configuration 245 * @throws Exception thrown when initialization fails 246 */ 247 ShuffleBacktrackNeighbourSelection(DataProperties properties) throws Exception { 248 super(properties); 249 setTimeout(properties.getPropertyInt("Shuffle.BackTrackTimeout", getTimeout())); 250 setDepth(properties.getPropertyInt("Shuffle.BackTrackDepth", getDepth())); 251 setMaxIters(properties.getPropertyInt("Shuffle.BackTrackMaxIters", getMaxIters())); 252 } 253 254 /** 255 * List of values of the given variable that will be considered (filtered using {@link ShuffleStudentsSelection.Shuffle#matchFilter(Enrollment)} if applicable). 256 * @param context assignment context 257 * @param variable given variable 258 * @return values of the given variable that will be considered 259 */ 260 @Override 261 protected Iterator<Enrollment> values(BacktrackNeighbourSelectionContext context, Request variable) { 262 Shuffle shuffle = ((ShuffleBacktrackNeighbourSelectionContext)context).getShuffle(); 263 if (shuffle.matchRequest(variable) && shuffle.hasFilter()) { 264 List<Enrollment> values = new ArrayList<Enrollment>(); 265 for (Iterator<Enrollment> i = super.values(context, variable); i.hasNext(); ) { 266 Enrollment e = i.next(); 267 if (shuffle.matchFilter(e)) values.add(e); 268 } 269 return values.iterator(); 270 } else { 271 return super.values(context, variable); 272 } 273 } 274 275 protected Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution, Shuffle shuffle) { 276 BacktrackNeighbourSelectionContext context = new ShuffleBacktrackNeighbourSelectionContext(solution, shuffle); 277 selectNeighbour(solution, shuffle.getRequest(), context); 278 return context.getBackTrackNeighbour(); 279 } 280 281 private class ShuffleBacktrackNeighbourSelectionContext extends BacktrackNeighbourSelectionContext { 282 private Shuffle iShuffle = null; 283 284 private ShuffleBacktrackNeighbourSelectionContext(Solution<Request, Enrollment> solution, Shuffle shuffle) { 285 super(solution); 286 iShuffle = shuffle; 287 } 288 289 private Shuffle getShuffle() { return iShuffle; } 290 } 291 } 292 293}