001package org.cpsolver.studentsct.heuristics.selection; 002 003import java.util.ArrayList; 004import java.util.Collections; 005import java.util.LinkedList; 006import java.util.List; 007import java.util.Queue; 008 009import org.cpsolver.ifs.heuristics.NeighbourSelection; 010import org.cpsolver.ifs.model.Neighbour; 011import org.cpsolver.ifs.solution.Solution; 012import org.cpsolver.ifs.solver.Solver; 013import org.cpsolver.ifs.util.DataProperties; 014import org.cpsolver.ifs.util.Progress; 015import org.cpsolver.studentsct.heuristics.RandomizedBacktrackNeighbourSelection; 016import org.cpsolver.studentsct.model.CourseRequest; 017import org.cpsolver.studentsct.model.Enrollment; 018import org.cpsolver.studentsct.model.FreeTimeRequest; 019import org.cpsolver.studentsct.model.Request; 020 021 022/** 023 * Use backtrack neighbour selection. For all unassigned variables (in a random 024 * order), {@link RandomizedBacktrackNeighbourSelection} is being used. 025 * 026 * <br> 027 * <br> 028 * 029 * @version StudentSct 1.3 (Student Sectioning)<br> 030 * Copyright (C) 2007 - 2014 Tomas Muller<br> 031 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 032 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 033 * <br> 034 * This library is free software; you can redistribute it and/or modify 035 * it under the terms of the GNU Lesser General Public License as 036 * published by the Free Software Foundation; either version 3 of the 037 * License, or (at your option) any later version. <br> 038 * <br> 039 * This library is distributed in the hope that it will be useful, but 040 * WITHOUT ANY WARRANTY; without even the implied warranty of 041 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 042 * Lesser General Public License for more details. <br> 043 * <br> 044 * You should have received a copy of the GNU Lesser General Public 045 * License along with this library; if not see 046 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 047 */ 048 049public class BacktrackSelection implements NeighbourSelection<Request, Enrollment> { 050 private RandomizedBacktrackNeighbourSelection iRBtNSel = null; 051 protected Queue<Request> iRequests = null; 052 protected boolean iIncludeAssignedRequests = false; 053 054 public BacktrackSelection(DataProperties properties) { 055 iIncludeAssignedRequests = properties.getPropertyBoolean("Neighbour.IncludeAssignedRequests", iIncludeAssignedRequests); 056 } 057 058 public void init(Solver<Request, Enrollment> solver, String name) { 059 List<Request> variables = new ArrayList<Request>(iIncludeAssignedRequests ? solver.currentSolution().getModel().variables() : solver.currentSolution().getModel().unassignedVariables(solver.currentSolution().getAssignment())); 060 Collections.shuffle(variables); 061 iRequests = new LinkedList<Request>(variables); 062 if (iRBtNSel == null) { 063 try { 064 iRBtNSel = new RandomizedBacktrackNeighbourSelection(solver.getProperties()); 065 iRBtNSel.init(solver); 066 } catch (Exception e) { 067 throw new RuntimeException(e.getMessage(), e); 068 } 069 } 070 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size()); 071 } 072 073 @Override 074 public void init(Solver<Request, Enrollment> solver) { 075 init(solver, "Backtracking..."); 076 } 077 078 protected synchronized Request nextRequest() { 079 return iRequests.poll(); 080 } 081 082 @Override 083 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 084 Request request = null; 085 while ((request = nextRequest()) != null) { 086 Progress.getInstance(solution.getModel()).incProgress(); 087 Enrollment e = request.getAssignment(solution.getAssignment()); 088 if (e != null && request instanceof FreeTimeRequest) continue; 089 if (e != null && e.getPriority() == 0 && ((CourseRequest)request).getSelectedChoices().isEmpty()) continue; 090 Neighbour<Request, Enrollment> n = iRBtNSel.selectNeighbour(solution, request); 091 if (n != null && n.value(solution.getAssignment()) <= 0.0) 092 return n; 093 } 094 return null; 095 } 096 097}