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

    All Methods Instance Methods Concrete Methods
    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.)