net.sf.cpsolver.studentsct.heuristics.selection
Class SwapStudentSelection

java.lang.Object
  net.sf.cpsolver.studentsct.heuristics.selection.SwapStudentSelection

All Implemented Interfaces:

NeighbourSelection, ProblemStudentsProvider

public class SwapStudentSelection
extends Object
implements NeighbourSelection, ProblemStudentsProvider

Pick a student (one by one) with an incomplete schedule, try to find an improvement, identify problematic students.

For each request that does not have an assignment and that can be assined (see Student.canAssign(Request)) a randomly selected sub-domain is visited. For every such enrollment, a set of conflicting enrollments is computed and a possible student that can get an alternative enrollment is identified (if there is any). For each such move a value (the cost of moving the problematic student somewhere else) is computed and the best possible move is selected at the end. If there is no such move, a set of problematic students is identified, i.e., the students whose enrollments are preventing this student to get a request.

Each student can be selected for this swap move multiple times, but only if there is still a request that can be resolved. At the end (when there is no other neighbour), the set of all such problematic students can be returned using the ProblemStudentsProvider interface.

Parameters:

Parameter	Type	Comment
Neighbour.SwapStudentsTimeout	Integer	Timeout for each neighbour selection (in milliseconds).
Neighbour.SwapStudentsMaxValues	Integer	Limit for the number of considered values for each course request (see CourseRequest.computeRandomEnrollments(int)).

Version:

StudentSct 1.1 (Student Sectioning)
Copyright (C) 2007 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

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 2.1 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

Nested Class Summary

class	SwapStudentSelection.Selection This class looks for a possible swap move for the given student
static class	SwapStudentSelection.SwapStudentNeighbour Neighbour that contains the swap

Field Summary

protected StudentOrder	iOrder
static boolean	sDebug

Constructor Summary

SwapStudentSelection(DataProperties properties)
Constructor

Method Summary

static Enrollment	bestSwap(Enrollment conflict, Enrollment enrl, Set problematicStudents) Identify the best swap for the given student
HashSet	getProblemStudents() List of problematic students
SwapStudentSelection.Selection	getSelection(Student student) Selection subclass for a student
void	init(Solver solver) Initialization
Neighbour	selectNeighbour(Solution solution) For each student that does not have a complete schedule, try to find a request and a student that can be moved out of an enrollment so that the selected student can be assigned to the selected request.

Methods inherited from class java.lang.Object

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

Field Detail

sDebug

public static boolean sDebug

iOrder

protected StudentOrder iOrder

Constructor Detail

SwapStudentSelection

public SwapStudentSelection(DataProperties properties)

Constructor

Parameters:

properties - configuration

Method Detail

init

public void init(Solver solver)

Initialization

Specified by:

init in interface NeighbourSelection

selectNeighbour

public Neighbour selectNeighbour(Solution solution)

For each student that does not have a complete schedule, try to find a request and a student that can be moved out of an enrollment so that the selected student can be assigned to the selected request.

Specified by:

selectNeighbour in interface NeighbourSelection

Parameters:

solution - given solution

Returns:

a neighbour assignment

getProblemStudents

public HashSet getProblemStudents()

List of problematic students

Specified by:

getProblemStudents in interface ProblemStudentsProvider

getSelection

public SwapStudentSelection.Selection getSelection(Student student)

Selection subclass for a student

bestSwap

public static Enrollment bestSwap(Enrollment conflict,
                                  Enrollment enrl,
                                  Set problematicStudents)

Identify the best swap for the given student

Parameters:

conflict - conflicting enrollment

enrl - enrollment that is visited (to be assigned to the given student)

problematicStudents - the current set of problematic students

Returns:

best alternative enrollment for the student of the conflicting enrollment