org.cpsolver.studentsct.heuristics

Class RandomizedBacktrackNeighbourSelection

java.lang.Object

org.cpsolver.ifs.heuristics.StandardNeighbourSelection<V,T>

org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection<Request,Enrollment>

org.cpsolver.studentsct.heuristics.RandomizedBacktrackNeighbourSelection

All Implemented Interfaces:

NeighbourSelection<Request,Enrollment>

public class RandomizedBacktrackNeighbourSelection
extends BacktrackNeighbourSelection<Request,Enrollment>

Randomized backtracking-based neighbour selection. This class extends RandomizedBacktrackNeighbourSelection, however, only a randomly selected subset of enrollments of each request is considered ( CourseRequest.computeRandomEnrollments(Assignment, int) with the given limit is used).

Parameters:

Related Solver Parameters

Parameter	Type	Comment
Neighbour.MaxValues	Integer	Limit on the number of enrollments to be visited of each CourseRequest.

Version:

StudentSct 1.3 (Student Sectioning)
Copyright (C) 2007 - 2014 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.

Author:

Tomáš Müller

Nested Class Summary

Nested classes/interfaces inherited from class org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection

BacktrackNeighbourSelection.BackTrackNeighbour, BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext

Field Summary

Fields inherited from class org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection

iContext

Fields inherited from class org.cpsolver.ifs.heuristics.StandardNeighbourSelection

iSolver, sLogger

Constructor Summary

Constructors

Constructor and Description
RandomizedBacktrackNeighbourSelection(DataProperties properties) Constructor

Method Summary

Modifier and Type	Method and Description
boolean	canUnassign(Enrollment enrollment, Enrollment conflict, Assignment<Request,Enrollment> assignment) Check if the given conflicting enrollment can be unassigned
protected boolean	checkBound(List<Request> variables2resolve, int idx, int depth, Enrollment value, Set<Enrollment> conflicts) Check bound
protected Iterator<Enrollment>	values(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context, Request variable) List of values of a variable.

Methods inherited from class org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection

backtrack, canContinue, canContinueEvaluation, getContext, getDepth, getMaxIters, getTimeout, init, selectNeighbour, selectNeighbour, selectNeighbour, setDepth, setMaxIters, setTimeout

Methods inherited from class org.cpsolver.ifs.heuristics.StandardNeighbourSelection

getValueSelection, getVariableSelection, selectValue, selectVariable, setValueSelection, setVariableSelection

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RandomizedBacktrackNeighbourSelection

public RandomizedBacktrackNeighbourSelection(DataProperties properties)
                                      throws Exception

Constructor

Parameters:

properties - configuration

Throws:

Exception - thrown when the initialization fails

Method Detail

values

protected Iterator<Enrollment> values(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context,
                                      Request variable)

List of values of a variable. CourseRequest.computeRandomEnrollments(Assignment, int) with the provided limit is used for a CourseRequest.

Overrides:

values in class BacktrackNeighbourSelection<Request,Enrollment>

Parameters:

context - assignment context

variable - given variable

Returns:

values of the given variable that will be considered

canUnassign

public boolean canUnassign(Enrollment enrollment,
                           Enrollment conflict,
                           Assignment<Request,Enrollment> assignment)

Check if the given conflicting enrollment can be unassigned

Parameters:

conflict - given enrollment

Returns:

if running MPP, do not unassign initial enrollments

checkBound

protected boolean checkBound(List<Request> variables2resolve,
                             int idx,
                             int depth,
                             Enrollment value,
                             Set<Enrollment> conflicts)

Description copied from class: BacktrackNeighbourSelection

Check bound

Overrides:

checkBound in class BacktrackNeighbourSelection<Request,Enrollment>

Parameters:

variables2resolve - unassigned variables that are in conflict with the current solution

idx - position in variables2resolve

depth - current depth

value - value to check

conflicts - conflicting values

Returns:

bound (best possible improvement)