org.cpsolver.studentsct.heuristics.selection

## Class BranchBoundSelection

- java.lang.Object
- - org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection

- All Implemented Interfaces:
    NeighbourSelection<Request,Enrollment>, InfoProvider<Request,Enrollment>, SolverListener<Request,Enrollment>
  Direct Known Subclasses:
    AssignInitialSelection, CriticalCoursesBranchAndBoundSelection, MinCreditBranchAndBoundSelection, OnlineSelection, ResectionIncompleteStudentsSelection, ResectionUnassignedStudentsSelection, SuggestionSelection

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

  Section all students using incremental branch & bound (no unassignments). All students are taken in a random order, for each student a branch & bound algorithm is used to find his/her best schedule on top of all other existing student schedules (no enrollment of a different student is unassigned).
  Parameters:

  Related Solver Parameters
  Parameter | Type | Comment
  --- | --- | ---
  Neighbour.BranchAndBoundTimeout | `Integer` | Timeout for each neighbour selection (in milliseconds).
  Neighbour.BranchAndBoundMinimizePenalty | `Boolean` | If true, section penalties (instead of section values) are minimized: overall penalty is minimized together with the maximization of the number of assigned requests and minimization of distance conflicts -- this variant is to better mimic the case when students can choose their sections (section times).

  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` | `BranchBoundSelection.BranchBoundNeighbour` Branch & bound neighbour -- a schedule of a student
    `class` | `BranchBoundSelection.Selection` Branch & bound selection for a student

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected boolean` | `iBranchWhenSelectedHasNoConflict`
    `protected DistanceConflict` | `iDistanceConflict`
    `protected double` | `iDistConfWeight`
    `protected StudentFilter` | `iFilter`
    `protected boolean` | `iMinimizePenalty`
    `protected StudentSectioningModel` | `iModel`
    `protected long` | `iNbrIterations`
    `protected long` | `iNbrNoSolution`
    `protected long` | `iNbrStudents`
    `protected long` | `iNbrTimeoutReached`
    `protected StudentOrder` | `iOrder`
    `protected StudentQuality` | `iStudentQuality`
    `protected LinkedList<Student>` | `iStudents`
    `protected int` | `iTimeout`
    `protected TimeOverlapsCounter` | `iTimeOverlaps`
    `protected boolean` | `iTimesToAvoidHeuristics`
    `protected long` | `iTotalTime`
    `static boolean` | `sDebug`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `BranchBoundSelection(DataProperties properties)` Constructor

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `addStudent(Student student)`
    `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
    `BranchBoundSelection.Selection` | `getSelection(Assignment<Request,Enrollment> assignment, Student student)` Branch & bound selection for a student
    `void` | `init(Solver<Request,Enrollment> solver)` Criterion initialization
    `void` | `init(Solver<Request,Enrollment> solver, String name)` Initialize
    `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 Student` | `nextStudent()`
    `Neighbour<Request,Enrollment>` | `selectNeighbour(Solution<Request,Enrollment> solution)` Select neighbour.
    `void` | `setModel(StudentSectioningModel model)`
    `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
    `BranchBoundSelection` | `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

    - #### iTimeout

          protected int iTimeout

    - #### iDistanceConflict

          protected DistanceConflict iDistanceConflict

    - #### iTimeOverlaps

          protected TimeOverlapsCounter iTimeOverlaps

    - #### iStudentQuality

          protected StudentQuality iStudentQuality

    - #### iModel

          protected StudentSectioningModel iModel

    - #### sDebug

          public static boolean sDebug

    - #### iStudents

          protected LinkedList<Student> iStudents

    - #### iMinimizePenalty

          protected boolean iMinimizePenalty

    - #### iOrder

          protected StudentOrder iOrder

    - #### iDistConfWeight

          protected double iDistConfWeight

    - #### iBranchWhenSelectedHasNoConflict

          protected boolean iBranchWhenSelectedHasNoConflict

    - #### iTimesToAvoidHeuristics

          protected boolean iTimesToAvoidHeuristics

    - #### iFilter

          protected StudentFilter iFilter

    - #### iNbrIterations

          protected long iNbrIterations

    - #### iTotalTime

          protected long iTotalTime

    - #### iNbrTimeoutReached

          protected long iNbrTimeoutReached

    - #### iNbrNoSolution

          protected long iNbrNoSolution

    - #### iNbrStudents

          protected long iNbrStudents

  - ### Constructor Detail

    - #### BranchBoundSelection

          public BranchBoundSelection(DataProperties properties)

      Constructor
      Parameters:
        `properties` - configuration

  - ### Method Detail

    - #### init

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

      Initialize
      Parameters:
        `solver` - current solver
        `name` - phase name

    - #### setModel

          public void setModel(StudentSectioningModel model)

    - #### 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

    - #### nextStudent

          protected Student nextStudent()

    - #### addStudent

          public void addStudent(Student student)

    - #### selectNeighbour

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

      Select neighbour. All students are taken, one by one in a random order. For each student a branch & bound search is employed.
      Specified by:
        `selectNeighbour` in interface `NeighbourSelection<Request,Enrollment>`
      Parameters:
        `solution` - given solution
      Returns:
        a neighbour assignment

    - #### getSelection

          public BranchBoundSelection.Selection getSelection(Assignment<Request,Enrollment> assignment,
                                                             Student student)

      Branch & bound selection for a student
      Parameters:
        `assignment` - current assignment
        `student` - selected student
      Returns:
        selection

    - #### 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 BranchBoundSelection 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