001package org.cpsolver.studentsct.heuristics.selection; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.Collections; 007import java.util.Comparator; 008import java.util.ConcurrentModificationException; 009import java.util.HashMap; 010import java.util.LinkedList; 011import java.util.List; 012import java.util.ListIterator; 013import java.util.Map; 014 015import org.cpsolver.ifs.assignment.Assignment; 016import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection; 017import org.cpsolver.ifs.heuristics.NeighbourSelection; 018import org.cpsolver.ifs.model.InfoProvider; 019import org.cpsolver.ifs.model.Neighbour; 020import org.cpsolver.ifs.solution.Solution; 021import org.cpsolver.ifs.solver.Solver; 022import org.cpsolver.ifs.solver.SolverListener; 023import org.cpsolver.ifs.util.DataProperties; 024import org.cpsolver.ifs.util.Progress; 025import org.cpsolver.studentsct.filter.StudentFilter; 026import org.cpsolver.studentsct.heuristics.RandomizedBacktrackNeighbourSelection; 027import org.cpsolver.studentsct.model.CourseRequest; 028import org.cpsolver.studentsct.model.Enrollment; 029import org.cpsolver.studentsct.model.FreeTimeRequest; 030import org.cpsolver.studentsct.model.Request; 031import org.cpsolver.studentsct.model.Request.RequestPriority; 032import org.cpsolver.studentsct.model.Student.StudentPriority; 033 034 035/** 036 * Use backtrack neighbour selection. For all unassigned variables (in a random 037 * order), {@link RandomizedBacktrackNeighbourSelection} is being used. 038 * 039 * <br> 040 * <br> 041 * 042 * @author Tomáš Müller 043 * @version StudentSct 1.3 (Student Sectioning)<br> 044 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 045 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 046 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 047 * <br> 048 * This library is free software; you can redistribute it and/or modify 049 * it under the terms of the GNU Lesser General Public License as 050 * published by the Free Software Foundation; either version 3 of the 051 * License, or (at your option) any later version. <br> 052 * <br> 053 * This library is distributed in the hope that it will be useful, but 054 * WITHOUT ANY WARRANTY; without even the implied warranty of 055 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 056 * Lesser General Public License for more details. <br> 057 * <br> 058 * You should have received a copy of the GNU Lesser General Public 059 * License along with this library; if not see 060 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 061 */ 062 063public class BacktrackSelection implements NeighbourSelection<Request, Enrollment>, InfoProvider<Request, Enrollment>, SolverListener<Request, Enrollment> { 064 private static DecimalFormat sDF = new DecimalFormat("0.00"); 065 protected RandomizedBacktrackNeighbourSelection iRBtNSel = null; 066 protected LinkedList<Request> iRequests = null; 067 protected boolean iIncludeAssignedRequests = false; 068 069 protected long iNbrIterations = 0; 070 protected long iMaxIterations = 0; 071 protected long iTotalTime = 0; 072 protected long iNbrTimeoutReached = 0; 073 protected long iNbrNoSolution = 0; 074 protected StudentFilter iFilter = null; 075 protected RequestComparator iRequestComparator = null; 076 protected Map<Request, Integer> iFailedCounter = new HashMap<Request, Integer>(); 077 protected long iNbrRequests = 0; 078 079 public BacktrackSelection(DataProperties properties) { 080 iIncludeAssignedRequests = properties.getPropertyBoolean("Neighbour.IncludeAssignedRequests", iIncludeAssignedRequests); 081 iRequestComparator = new RequestComparator(properties); 082 } 083 084 public void init(Solver<Request, Enrollment> solver, String name) { 085 List<Request> variables = new ArrayList<Request>(iIncludeAssignedRequests ? solver.currentSolution().getModel().variables() : solver.currentSolution().getModel().unassignedVariables(solver.currentSolution().getAssignment())); 086 Collections.shuffle(variables); 087 Collections.sort(variables, iRequestComparator); 088 iRequests = new LinkedList<Request>(variables); 089 iFailedCounter.clear(); 090 if (iRBtNSel == null) { 091 try { 092 iRBtNSel = new RandomizedBacktrackNeighbourSelection(solver.getProperties()); 093 iRBtNSel.init(solver); 094 } catch (Exception e) { 095 throw new RuntimeException(e.getMessage(), e); 096 } 097 } 098 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size()); 099 } 100 101 @Override 102 public void init(Solver<Request, Enrollment> solver) { 103 init(solver, "Backtracking" + (iFilter == null ? "" : " (" + iFilter.getName().toLowerCase() + " students)") + "..."); 104 105 iNbrIterations = 0; 106 iNbrTimeoutReached = 0; 107 iNbrNoSolution = 0; 108 iTotalTime = 0; 109 iMaxIterations = Math.max(10, 2 * iRequests.size()); 110 iNbrRequests = iRequests.size(); 111 } 112 113 protected synchronized Request nextRequest() { 114 while (true) { 115 Request request = iRequests.poll(); 116 if (request == null) return null; 117 if (iFilter == null || iFilter.accept(request.getStudent())) return request; 118 } 119 } 120 121 public synchronized void addRequest(Request request) { 122 if (iRequests != null && request != null && !request.getStudent().isDummy()) { 123 Integer failed = iFailedCounter.getOrDefault(request, 0); 124 iFailedCounter.put(request, 1 + failed); 125 if (failed >= 5) return; 126 if (request.getStudent().getPriority().ordinal() < StudentPriority.Normal.ordinal() || request.getRequestPriority().ordinal() < RequestPriority.Normal.ordinal()) { 127 for (ListIterator<Request> i = iRequests.listIterator(); i.hasNext();) { 128 Request r = i.next(); 129 if (iRequestComparator.compare(r, request) > 0) { 130 i.previous(); // go one back 131 i.add(request); 132 return; 133 } 134 } 135 } 136 iRequests.add(request); 137 } 138 } 139 140 @Override 141 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 142 Request request = null; 143 if (iNbrIterations > iMaxIterations) return null; 144 while ((request = nextRequest()) != null) { 145 Progress.getInstance(solution.getModel()).setProgress(iNbrRequests - iRequests.size()); 146 Enrollment e = request.getAssignment(solution.getAssignment()); 147 if (e != null && request instanceof FreeTimeRequest) continue; 148 if (e != null && e.getPriority() == 0 && ((CourseRequest)request).getSelectedChoices().isEmpty()) continue; 149 for (int i = 0; i < 5; i++) { 150 try { 151 Neighbour<Request, Enrollment> n = iRBtNSel.selectNeighbour(solution, request); 152 if (iRBtNSel.getContext() != null) { 153 iNbrIterations ++; 154 iTotalTime += iRBtNSel.getContext().getTime(); 155 if (iRBtNSel.getContext().isTimeoutReached()) iNbrTimeoutReached ++; 156 if (n == null) iNbrNoSolution ++; 157 } 158 if (n != null && n.value(solution.getAssignment()) <= 0.0) 159 return n; 160 break; 161 } catch (ConcurrentModificationException ex) {} 162 } 163 } 164 return null; 165 } 166 167 @Override 168 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) { 169 if (iNbrIterations > 0) 170 info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" + 171 iNbrIterations + " iterations, " + 172 (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") + 173 sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iRBtNSel.getTimeout() / 1000.0) + " seconds reached" + 174 (iNbrIterations > iMaxIterations ? ", stopped after " + iNbrIterations + " iterations" : "") + 175 ")"); 176 } 177 178 @Override 179 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) { 180 } 181 182 /** 183 * Only consider students meeting the given filter. 184 */ 185 public StudentFilter getFilter() { return iFilter; } 186 187 /** 188 * Only consider students meeting the given filter. 189 */ 190 public BacktrackSelection withFilter(StudentFilter filter) { iFilter = filter; return this; } 191 192 @Override 193 public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) { 194 return false; 195 } 196 @Override 197 public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) { 198 return false; 199 } 200 @Override 201 public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 202 return false; 203 } 204 @Override 205 public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 206 if (neighbour instanceof BacktrackNeighbourSelection.BackTrackNeighbour) 207 addRequest(((BacktrackNeighbourSelection<Request, Enrollment>.BackTrackNeighbour)neighbour).getAssignments().get(0).getRequest()); 208 } 209 210 public static class RequestComparator implements Comparator<Request> { 211 protected boolean iPreferPriorityStudents = true; 212 protected RequestComparator(DataProperties properties) { 213 iPreferPriorityStudents = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true); 214 } 215 216 @Override 217 public int compare(Request r1, Request r2) { 218 if (iPreferPriorityStudents) { 219 if (r1.getStudent().getPriority() != r2.getStudent().getPriority()) 220 return r1.getStudent().getPriority().compareTo(r2.getStudent().getPriority()); 221 if (r1.getRequestPriority() != r2.getRequestPriority()) 222 return r1.getRequestPriority().compareTo(r2.getRequestPriority()); 223 } else { 224 if (r1.getRequestPriority() != r2.getRequestPriority()) 225 return r1.getRequestPriority().compareTo(r2.getRequestPriority()); 226 if (r1.getRequestPriority() != r2.getRequestPriority()) 227 return r1.getStudent().getPriority().compareTo(r2.getStudent().getPriority()); 228 } 229 if (r1.isAlternative() != r2.isAlternative()) 230 return r2.isAlternative() ? -1 : 1; 231 if (r1.getPriority() != r2.getPriority()) 232 return r1.getPriority() < r2.getPriority() ? -1 : 1; 233 return 0; 234 } 235 } 236}