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 051 public BacktrackSelection(DataProperties properties) { 052 } 053 054 public void init(Solver<Request, Enrollment> solver, String name) { 055 List<Request> unassigned = new ArrayList<Request>(solver.currentSolution().getModel().unassignedVariables(solver.currentSolution().getAssignment())); 056 Collections.shuffle(unassigned); 057 iRequests = new LinkedList<Request>(unassigned); 058 if (iRBtNSel == null) { 059 try { 060 iRBtNSel = new RandomizedBacktrackNeighbourSelection(solver.getProperties()); 061 iRBtNSel.init(solver); 062 } catch (Exception e) { 063 throw new RuntimeException(e.getMessage(), e); 064 } 065 } 066 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, unassigned.size()); 067 } 068 069 @Override 070 public void init(Solver<Request, Enrollment> solver) { 071 init(solver, "Backtracking..."); 072 } 073 074 protected synchronized Request nextRequest() { 075 return iRequests.poll(); 076 } 077 078 @Override 079 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 080 Request request = null; 081 while ((request = nextRequest()) != null) { 082 Progress.getInstance(solution.getModel()).incProgress(); 083 Neighbour<Request, Enrollment> n = iRBtNSel.selectNeighbour(solution, request); 084 if (n != null && n.value(solution.getAssignment()) <= 0.0) 085 return n; 086 } 087 return null; 088 } 089 090}