org.cpsolver.studentsct.heuristics.selection

Class BacktrackSelection

java.lang.Object

org.cpsolver.studentsct.heuristics.selection.BacktrackSelection

All Implemented Interfaces:

NeighbourSelection<Request,Enrollment>, InfoProvider<Request,Enrollment>, SolverListener<Request,Enrollment>

Direct Known Subclasses:

CriticalBacktrackSelection

public class BacktrackSelection
extends Object
implements NeighbourSelection<Request,Enrollment>, InfoProvider<Request,Enrollment>, SolverListener<Request,Enrollment>

Use backtrack neighbour selection. For all unassigned variables (in a random order), RandomizedBacktrackNeighbourSelection is being used.

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

Modifier and Type	Class and Description
static class	BacktrackSelection.RequestComparator

Field Summary

Fields

Modifier and Type	Field and Description
protected StudentFilter	iFilter
protected boolean	iIncludeAssignedRequests
protected long	iMaxIterations
protected long	iNbrIterations
protected long	iNbrNoSolution
protected long	iNbrTimeoutReached
protected RandomizedBacktrackNeighbourSelection	iRBtNSel
protected BacktrackSelection.RequestComparator	iRequestComparator
protected LinkedList<Request>	iRequests
protected long	iTotalTime

Constructor Summary

Constructors

Constructor and Description
BacktrackSelection(DataProperties properties)

Method Summary

Modifier and Type	Method and Description
void	addRequest(Request request)
StudentFilter	getFilter() Only consider students meeting the given filter.
void	getInfo(Assignment<Request,Enrollment> assignment, Map<String,String> info) Adds some information into the table with information about the solution
void	getInfo(Assignment<Request,Enrollment> assignment, Map<String,String> info, Collection<Request> variables) Adds some information into the table with information about the solution, only consider variables from the given set
void	init(Solver<Request,Enrollment> solver) Criterion initialization
void	init(Solver<Request,Enrollment> solver, String name)
void	neighbourFailed(Assignment<Request,Enrollment> assignment, long iteration, Neighbour<Request,Enrollment> neighbour) Called when ParallelSolver failed to assign the given neighbour
boolean	neighbourSelected(Assignment<Request,Enrollment> assignment, long iteration, Neighbour<Request,Enrollment> neighbour) A neighbour was selected
protected Request	nextRequest()
Neighbour<Request,Enrollment>	selectNeighbour(Solution<Request,Enrollment> solution) select a neighbour of a given solution
boolean	valueSelected(Assignment<Request,Enrollment> assignment, long iteration, Request variable, Enrollment value) A value was selected
boolean	variableSelected(Assignment<Request,Enrollment> assignment, long iteration, Request variable) A variable was selected
BacktrackSelection	withFilter(StudentFilter filter) Only consider students meeting the given filter.

Methods inherited from class java.lang.Object

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

Field Detail

iRBtNSel

protected RandomizedBacktrackNeighbourSelection iRBtNSel

iRequests

protected LinkedList<Request> iRequests

iIncludeAssignedRequests

protected boolean iIncludeAssignedRequests

iNbrIterations

protected long iNbrIterations

iMaxIterations

protected long iMaxIterations

iTotalTime

protected long iTotalTime

iNbrTimeoutReached

protected long iNbrTimeoutReached

iNbrNoSolution

protected long iNbrNoSolution

iFilter

protected StudentFilter iFilter

iRequestComparator

protected BacktrackSelection.RequestComparator iRequestComparator

Constructor Detail

BacktrackSelection

public BacktrackSelection(DataProperties properties)

Method Detail

init

public void init(Solver<Request,Enrollment> solver,
                 String name)

init

public void init(Solver<Request,Enrollment> solver)

Description copied from interface: NeighbourSelection

Criterion initialization

Specified by:

init in interface NeighbourSelection<Request,Enrollment>

Parameters:

solver - current solver

nextRequest

protected Request nextRequest()

addRequest

public void addRequest(Request request)

selectNeighbour

public Neighbour<Request,Enrollment> selectNeighbour(Solution<Request,Enrollment> solution)

Description copied from interface: NeighbourSelection

select a neighbour of a given solution

Specified by:

selectNeighbour in interface NeighbourSelection<Request,Enrollment>

Parameters:

solution - given solution

Returns:

a neighbour assignment

getInfo

public void getInfo(Assignment<Request,Enrollment> assignment,
                    Map<String,String> info)

Description copied from interface: InfoProvider

Adds some information into the table with information about the solution

Specified by:

getInfo in interface InfoProvider<Request,Enrollment>

Parameters:

assignment - current assignment

info - info table

getInfo

public void getInfo(Assignment<Request,Enrollment> assignment,
                    Map<String,String> info,
                    Collection<Request> variables)

Description copied from interface: InfoProvider

Adds some information into the table with information about the solution, only consider variables from the given set

Specified by:

getInfo in interface InfoProvider<Request,Enrollment>

Parameters:

assignment - current assignment

info - info table

variables - sub-problem

getFilter

public StudentFilter getFilter()

Only consider students meeting the given filter.

withFilter

public BacktrackSelection withFilter(StudentFilter filter)

Only consider students meeting the given filter.

variableSelected

public boolean variableSelected(Assignment<Request,Enrollment> assignment,
                                long iteration,
                                Request variable)

Description copied from interface: SolverListener

A variable was selected

Specified by:

variableSelected in interface SolverListener<Request,Enrollment>

Parameters:

assignment - current assignment

iteration - current iteration

variable - selected variable

Returns:

if false is returned the variable will be discarded (search continues with the next variable selection)

valueSelected

public boolean valueSelected(Assignment<Request,Enrollment> assignment,
                             long iteration,
                             Request variable,
                             Enrollment value)

Description copied from interface: SolverListener

A value was selected

Specified by:

valueSelected in interface SolverListener<Request,Enrollment>

Parameters:

assignment - current assignment

iteration - current iteration

variable - selected variable

value - selected variable

Returns:

if false is returned the selected value is not assigned

neighbourSelected

public boolean neighbourSelected(Assignment<Request,Enrollment> assignment,
                                 long iteration,
                                 Neighbour<Request,Enrollment> neighbour)

Description copied from interface: SolverListener

A neighbour was selected

Specified by:

neighbourSelected in interface SolverListener<Request,Enrollment>

Parameters:

assignment - current assignment

iteration - current iteration

neighbour - neighbour

Returns:

if false is returned the selected neighbour is not assigned

neighbourFailed

public void neighbourFailed(Assignment<Request,Enrollment> assignment,
                            long iteration,
                            Neighbour<Request,Enrollment> neighbour)

Description copied from interface: SolverListener

Called when ParallelSolver failed to assign the given neighbour

Specified by:

neighbourFailed in interface SolverListener<Request,Enrollment>

Parameters:

assignment - current assignment

iteration - current iteration

neighbour - neighbour