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.LinkedList; 008import java.util.List; 009import java.util.Map; 010import java.util.Queue; 011 012import org.cpsolver.ifs.assignment.Assignment; 013import org.cpsolver.ifs.heuristics.NeighbourSelection; 014import org.cpsolver.ifs.model.InfoProvider; 015import org.cpsolver.ifs.model.Neighbour; 016import org.cpsolver.ifs.solution.Solution; 017import org.cpsolver.ifs.solver.Solver; 018import org.cpsolver.ifs.util.DataProperties; 019import org.cpsolver.ifs.util.Progress; 020import org.cpsolver.studentsct.heuristics.RandomizedBacktrackNeighbourSelection; 021import org.cpsolver.studentsct.model.CourseRequest; 022import org.cpsolver.studentsct.model.Enrollment; 023import org.cpsolver.studentsct.model.FreeTimeRequest; 024import org.cpsolver.studentsct.model.Request; 025 026 027/** 028 * Use backtrack neighbour selection. For all unassigned variables (in a random 029 * order), {@link RandomizedBacktrackNeighbourSelection} is being used. 030 * 031 * <br> 032 * <br> 033 * 034 * @version StudentSct 1.3 (Student Sectioning)<br> 035 * Copyright (C) 2007 - 2014 Tomas Muller<br> 036 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 037 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 038 * <br> 039 * This library is free software; you can redistribute it and/or modify 040 * it under the terms of the GNU Lesser General Public License as 041 * published by the Free Software Foundation; either version 3 of the 042 * License, or (at your option) any later version. <br> 043 * <br> 044 * This library is distributed in the hope that it will be useful, but 045 * WITHOUT ANY WARRANTY; without even the implied warranty of 046 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 047 * Lesser General Public License for more details. <br> 048 * <br> 049 * You should have received a copy of the GNU Lesser General Public 050 * License along with this library; if not see 051 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 052 */ 053 054public class BacktrackSelection implements NeighbourSelection<Request, Enrollment>, InfoProvider<Request, Enrollment> { 055 private static DecimalFormat sDF = new DecimalFormat("0.00"); 056 protected RandomizedBacktrackNeighbourSelection iRBtNSel = null; 057 protected Queue<Request> iRequests = null; 058 protected boolean iIncludeAssignedRequests = false; 059 060 protected long iNbrIterations = 0; 061 protected long iTotalTime = 0; 062 protected long iNbrTimeoutReached = 0; 063 protected long iNbrNoSolution = 0; 064 065 public BacktrackSelection(DataProperties properties) { 066 iIncludeAssignedRequests = properties.getPropertyBoolean("Neighbour.IncludeAssignedRequests", iIncludeAssignedRequests); 067 } 068 069 public void init(Solver<Request, Enrollment> solver, String name) { 070 List<Request> variables = new ArrayList<Request>(iIncludeAssignedRequests ? solver.currentSolution().getModel().variables() : solver.currentSolution().getModel().unassignedVariables(solver.currentSolution().getAssignment())); 071 Collections.shuffle(variables); 072 iRequests = new LinkedList<Request>(variables); 073 if (iRBtNSel == null) { 074 try { 075 iRBtNSel = new RandomizedBacktrackNeighbourSelection(solver.getProperties()); 076 iRBtNSel.init(solver); 077 } catch (Exception e) { 078 throw new RuntimeException(e.getMessage(), e); 079 } 080 } 081 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size()); 082 } 083 084 @Override 085 public void init(Solver<Request, Enrollment> solver) { 086 init(solver, "Backtracking..."); 087 088 iNbrIterations = 0; 089 iNbrTimeoutReached = 0; 090 iNbrNoSolution = 0; 091 iTotalTime = 0; 092 } 093 094 protected synchronized Request nextRequest() { 095 return iRequests.poll(); 096 } 097 098 @Override 099 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 100 Request request = null; 101 while ((request = nextRequest()) != null) { 102 Progress.getInstance(solution.getModel()).incProgress(); 103 Enrollment e = request.getAssignment(solution.getAssignment()); 104 if (e != null && request instanceof FreeTimeRequest) continue; 105 if (e != null && e.getPriority() == 0 && ((CourseRequest)request).getSelectedChoices().isEmpty()) continue; 106 Neighbour<Request, Enrollment> n = iRBtNSel.selectNeighbour(solution, request); 107 if (iRBtNSel.getContext() != null) { 108 iNbrIterations ++; 109 iTotalTime += iRBtNSel.getContext().getTime(); 110 if (iRBtNSel.getContext().isTimeoutReached()) iNbrTimeoutReached ++; 111 if (n == null) iNbrNoSolution ++; 112 } 113 if (n != null && n.value(solution.getAssignment()) <= 0.0) 114 return n; 115 } 116 return null; 117 } 118 119 @Override 120 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) { 121 if (iNbrIterations > 0) 122 info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" + 123 iNbrIterations + " iterations, " + 124 (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") + 125 sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iRBtNSel.getTimeout() / 1000.0) + " seconds reached)"); 126 } 127 128 @Override 129 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) { 130 } 131}