org.cpsolver.studentsct.online.selection

Class SuggestionsBranchAndBound

java.lang.Object

org.cpsolver.studentsct.online.selection.SuggestionsBranchAndBound

Direct Known Subclasses:

MultiCriteriaBranchAndBoundSuggestions

public class SuggestionsBranchAndBound
extends Object

Computation of suggestions using a limited depth branch and bound. For a given schedule and a selected section, compute possible changes that will be displayed to the student as suggestions. The number of suggestions is limited by Suggestions.MaxSuggestions parameter (defaults to 20). Time is limited by Suggestions.Timeout (defaults to 5000 ms), search depth is limited by Suggestions.MaxDepth parameter (default to 4).

Version:

StudentSct 1.3 (Student Sectioning)
Copyright (C) 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
class	SuggestionsBranchAndBound.EnrollmentSectionComparator Enrollment comparator (used to sort enrollments in a domain).
class	SuggestionsBranchAndBound.SectionAssignmentComparator Section comparator.
class	SuggestionsBranchAndBound.Suggestion Suggestion
static interface	SuggestionsBranchAndBound.SuggestionFilter Suggestion filter.

Field Summary

Fields

Modifier and Type	Field and Description
protected MultiCriteriaBranchAndBoundSelection.SelectionComparator	iComparator
protected int	iMatched
protected double	iMaxSectionsWithPenalty

Constructor Summary

Constructors

Constructor and Description

SuggestionsBranchAndBound(DataProperties properties, Student student, Assignment<Request,Enrollment> assignment, Hashtable<CourseRequest,Set<Section>> requiredSections, Set<FreeTimeRequest> requiredFreeTimes, Hashtable<CourseRequest,Set<Section>> preferredSections, Request selectedRequest, Section selectedSection, SuggestionsBranchAndBound.SuggestionFilter filter, double maxSectionsWithPenalty) Constructor

Method Summary

Modifier and Type	Method and Description
protected void	backtrack(ArrayList<Request> requests2resolve, TreeSet<Request> altRequests2resolve, int idx, int depth, boolean alt) Main branch and bound rutine
protected boolean	canContinue(ArrayList<Request> requests2resolve, int idx, int depth) Termination criterion
protected boolean	canContinueEvaluation() Can continue evaluation of possible enrollments
boolean	canLeaveUnassigned(Request request) Can this request be left unassigned
protected boolean	checkBound(ArrayList<Request> requests2resolve, int idx, int depth, Enrollment value, Set<Enrollment> conflicts) Check bound
protected int	compare(Assignment<Request,Enrollment> assignment, SuggestionsBranchAndBound.Suggestion s1, SuggestionsBranchAndBound.Suggestion s2) Compare two suggestions
TreeSet<SuggestionsBranchAndBound.Suggestion>	computeSuggestions() Perform the search
int	getNrMatched() Number of possible enrollments of the selected request
int	getNrSolutionsSeen() Number of possible suggestions visited
long	getTime() Return search time
boolean	isAllowed(Enrollment enrollment) Check required sections
boolean	isTimeoutReached() Was time limit reached
protected List<Enrollment>	values(Request request) Domain of a request

Methods inherited from class java.lang.Object

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

Field Detail

iComparator

protected MultiCriteriaBranchAndBoundSelection.SelectionComparator iComparator

iMatched

protected int iMatched

iMaxSectionsWithPenalty

protected double iMaxSectionsWithPenalty

Constructor Detail

SuggestionsBranchAndBound

public SuggestionsBranchAndBound(DataProperties properties,
                                 Student student,
                                 Assignment<Request,Enrollment> assignment,
                                 Hashtable<CourseRequest,Set<Section>> requiredSections,
                                 Set<FreeTimeRequest> requiredFreeTimes,
                                 Hashtable<CourseRequest,Set<Section>> preferredSections,
                                 Request selectedRequest,
                                 Section selectedSection,
                                 SuggestionsBranchAndBound.SuggestionFilter filter,
                                 double maxSectionsWithPenalty)

Constructor

Parameters:

properties - configuration

student - given student

assignment - current assignment

requiredSections - required sections

requiredFreeTimes - required free times (free time requests that must be assigned)

preferredSections - preferred sections

selectedRequest - selected request

selectedSection - selected section

filter - section filter

maxSectionsWithPenalty - maximal number of sections that have a positive over-expectation penalty OverExpectedCriterion.getOverExpected(Assignment, Section, Request)

Method Detail

getTime

public long getTime()

Return search time

Returns:

search time

isTimeoutReached

public boolean isTimeoutReached()

Was time limit reached

Returns:

true if reached

getNrSolutionsSeen

public int getNrSolutionsSeen()

Number of possible suggestions visited

Returns:

a number of solutions seen

computeSuggestions

public TreeSet<SuggestionsBranchAndBound.Suggestion> computeSuggestions()

Perform the search

Returns:

an ordered set of possible suggestions

backtrack

protected void backtrack(ArrayList<Request> requests2resolve,
                         TreeSet<Request> altRequests2resolve,
                         int idx,
                         int depth,
                         boolean alt)

Main branch and bound rutine

Parameters:

requests2resolve - remaining requests to assign

altRequests2resolve - alternative requests to assign

idx - current depth

depth - remaining depth

alt - can leave a request unassigned

values

protected List<Enrollment> values(Request request)

Domain of a request

Parameters:

request - given request

Returns:

possible enrollments (meeting the filter etc)

canContinue

protected boolean canContinue(ArrayList<Request> requests2resolve,
                              int idx,
                              int depth)

Termination criterion

Parameters:

requests2resolve - request to resolve

idx - current depth

depth - remaining depth

Returns:

true if the search can continue

canContinueEvaluation

protected boolean canContinueEvaluation()

Can continue evaluation of possible enrollments

Returns:

false if the timeout was reached

checkBound

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

Check bound

Parameters:

requests2resolve - requests to resolve

idx - current depth

depth - remaining depth

value - enrollment in question

conflicts - conflicting enrollments

Returns:

false if the branch can be cut

isAllowed

public boolean isAllowed(Enrollment enrollment)

Check required sections

Parameters:

enrollment - given enrollment

Returns:

true if the given enrollment allowed

canLeaveUnassigned

public boolean canLeaveUnassigned(Request request)

Can this request be left unassigned

Parameters:

request - given request

Returns:

true if can be left unassigned (there is no requirement)

compare

protected int compare(Assignment<Request,Enrollment> assignment,
                      SuggestionsBranchAndBound.Suggestion s1,
                      SuggestionsBranchAndBound.Suggestion s2)

Compare two suggestions

Parameters:

assignment - current assignment

s1 - first suggestion

s2 - second suggestion

Returns:

true if s1 is better than s2

getNrMatched

public int getNrMatched()

Number of possible enrollments of the selected request

Returns:

number of possible enrollment of the selected request (meeting the given filter etc.)