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