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 for (Course course: offering.getCourses()) { 078 for (RequestGroup group: course.getRequestGroups()) { 079 double spread = group.getAverageSpread(solver.currentSolution().getAssignment()); 080 if (spread >= 1.0) continue; 081 groups.add(group, 1.0 - spread); 082 } 083 } 084 } 085 // If there are some, pick one randomly (using roulette wheel selection) 086 if (groups.hasMoreElements()) { 087 RequestGroup group = groups.nextElement(); 088 RouletteWheelSelection<Subpart> subparts = new RouletteWheelSelection<Subpart>(); 089 for (CourseRequest cr: group.getRequests()) { 090 Enrollment e = assignment.getValue(cr); 091 if (e != null) 092 for (Section section: e.getSections()) 093 if (group.getSectionSpread(assignment, section) < 1.0) 094 subparts.addExisting(section.getSubpart(), 1.0); 095 } 096 if (subparts.hasMoreElements()) { 097 // Pick a subpart that has sections with a section spread < 1.0 098 Subpart subpart = subparts.nextElement(); 099 RouletteWheelSelection<Section> sections = new RouletteWheelSelection<Section>(); 100 section: for (Section section: subpart.getSections()) { 101 // Only take sections that all requests can use 102 for (CourseRequest cr: group.getRequests()) { 103 boolean match = false; 104 for (Enrollment e: cr.values(assignment)) 105 if (e.getSections().contains(section)) { match = true; break; } 106 if (!match) continue section; 107 } 108 // Take sections with conflicts with lower probability 109 int nrConflicts = 0; 110 if (!section.isAllowOverlap()) 111 requests: for (CourseRequest cr: group.getRequests()) { 112 for (Request r: cr.getStudent().getRequests()) { 113 if (r.equals(cr)) continue; 114 Enrollment e = assignment.getValue(r); 115 if (e != null && !e.isAllowOverlap() && section.isOverlapping(e.getSections())) { 116 nrConflicts++; continue requests; 117 } 118 } 119 } 120 sections.add(section, 1 + group.getRequests().size() - nrConflicts); 121 } 122 Set<Section> filter = new HashSet<Section>(); double space = 0.0; 123 // Pick enough sections 124 while (sections.hasMoreElements()) { 125 Section section = sections.nextElement(); 126 if (filter.add(section)) { 127 if (section.getLimit() < 0) break; 128 space += section.getLimit(); 129 } 130 if (space >= group.getTotalWeight()) break; 131 } 132 // Add all requests that should be moved into the queue 133 for (CourseRequest cr: group.getRequests()) { 134 Shuffle shuffle = new Shuffle(group, cr, filter); 135 Enrollment e = assignment.getValue(cr); 136 if (e != null && shuffle.matchFilter(e)) continue; 137 iQueue.add(shuffle); 138 } 139 } else { 140 // No subpart -> no section filter 141 for (CourseRequest cr: group.getRequests()) 142 iQueue.add(new Shuffle(group, cr, null)); 143 } 144 } 145 // Shuffle the queue 146 Collections.shuffle((LinkedList<Shuffle>)iQueue); 147 // Initialize the backtrack selection, if needed 148 if (iBacktrack == null) { 149 try { 150 iBacktrack = new ShuffleBacktrackNeighbourSelection(solver.getProperties()); 151 iBacktrack.init(solver); 152 } catch (Exception e) { 153 throw new RuntimeException(e.getMessage(), e); 154 } 155 } 156 // Change progress 157 Progress.getInstance(solver.currentSolution().getModel()).setPhase("Shuffling students along request groups...", iQueue.size()); 158 } 159 160 @Override 161 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 162 Shuffle shuffle = null; 163 while ((shuffle = iQueue.poll()) != null) { 164 Progress.getInstance(solution.getModel()).incProgress(); 165 // Take an item from the queue, try backtrack first 166 Neighbour<Request, Enrollment> n = iBacktrack.selectNeighbour(solution, shuffle); 167 if (n != null) return n; 168 // If fails, just assign the request randomly and hope for the best 169 List<Enrollment> adepts = new ArrayList<Enrollment>(); 170 for (Enrollment e: shuffle.getRequest().values(solution.getAssignment())) { 171 if (shuffle.matchFilter(e)) adepts.add(e); 172 } 173 if (!adepts.isEmpty()) { 174 return new SimpleNeighbour<Request, Enrollment>(shuffle.getRequest(), ToolBox.random(adepts)); 175 } 176 } 177 return null; 178 } 179 180 /** 181 * One item to be shuffled 182 */ 183 private static class Shuffle { 184 RequestGroup iGroup; 185 CourseRequest iRequest; 186 Set<Section> iFilter; 187 188 /** 189 * Constructor 190 * @param group selected request group 191 * @param request selected request of a request group 192 * @param filter section filter (if used, only enrollments that contain one of the given sections can be used) 193 */ 194 Shuffle(RequestGroup group, CourseRequest request, Set<Section> filter) { 195 iGroup = group; 196 iRequest = request; 197 iFilter = filter; 198 } 199 200 /** 201 * Selected request group 202 * @return a request group 203 */ 204 public CourseRequest getRequest() { return iRequest; } 205 206 /** 207 * Is there a section filter set? 208 * @return true, if only enrollments with matching sections can be used 209 */ 210 public boolean hasFilter() { return iFilter != null && !iFilter.isEmpty(); } 211 212 /** 213 * Is the given request matching this object? 214 * @param variable a request 215 * @return true if the given variable is a course request for a matching course 216 */ 217 public boolean matchRequest(Request variable) { 218 return variable instanceof CourseRequest && ((CourseRequest)variable).getCourses().contains(iGroup.getCourse()); 219 } 220 221 /** 222 * Is the given enrollment matching the section filter 223 * @param e an enrollment 224 * @return true if the enrollment contains at least one section of the filter 225 */ 226 public boolean matchFilter(Enrollment e) { 227 if (iFilter == null || iFilter.isEmpty()) return true; 228 for (Section s: e.getSections()) 229 if (iFilter.contains(s)) return true; 230 return false; 231 } 232 } 233 234 /** 235 * A special version of the {@link BacktrackNeighbourSelection} that filters the enrollments with the 236 * provided section filter. 237 * 238 */ 239 public static class ShuffleBacktrackNeighbourSelection extends BacktrackNeighbourSelection<Request, Enrollment> { 240 241 /** 242 * Constructor 243 * @param properties configuration 244 * @throws Exception thrown when initialization fails 245 */ 246 ShuffleBacktrackNeighbourSelection(DataProperties properties) throws Exception { 247 super(properties); 248 setTimeout(properties.getPropertyInt("Shuffle.BackTrackTimeout", getTimeout())); 249 setDepth(properties.getPropertyInt("Shuffle.BackTrackDepth", getDepth())); 250 setMaxIters(properties.getPropertyInt("Shuffle.BackTrackMaxIters", getMaxIters())); 251 } 252 253 /** 254 * List of values of the given variable that will be considered (filtered using {@link ShuffleStudentsSelection.Shuffle#matchFilter(Enrollment)} if applicable). 255 * @param context assignment context 256 * @param variable given variable 257 * @return values of the given variable that will be considered 258 */ 259 @Override 260 protected Iterator<Enrollment> values(BacktrackNeighbourSelectionContext context, Request variable) { 261 Shuffle shuffle = ((ShuffleBacktrackNeighbourSelectionContext)context).getShuffle(); 262 if (shuffle.matchRequest(variable) && shuffle.hasFilter()) { 263 List<Enrollment> values = new ArrayList<Enrollment>(); 264 for (Iterator<Enrollment> i = super.values(context, variable); i.hasNext(); ) { 265 Enrollment e = i.next(); 266 if (shuffle.matchFilter(e)) values.add(e); 267 } 268 return values.iterator(); 269 } else { 270 return super.values(context, variable); 271 } 272 } 273 274 protected Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution, Shuffle shuffle) { 275 BacktrackNeighbourSelectionContext context = new ShuffleBacktrackNeighbourSelectionContext(solution, shuffle); 276 selectNeighbour(solution, shuffle.getRequest(), context); 277 return context.getBackTrackNeighbour(); 278 } 279 280 private class ShuffleBacktrackNeighbourSelectionContext extends BacktrackNeighbourSelectionContext { 281 private Shuffle iShuffle = null; 282 283 private ShuffleBacktrackNeighbourSelectionContext(Solution<Request, Enrollment> solution, Shuffle shuffle) { 284 super(solution); 285 iShuffle = shuffle; 286 } 287 288 private Shuffle getShuffle() { return iShuffle; } 289 } 290 } 291 292}