bande::BranchControl Class Reference
Central control of branching algorithm. More...
#include <BranchControl.hh>
Public Member Functions | |
| BranchControl (Solutions &sols) | |
| Constructor. | |
| virtual | ~BranchControl () |
| Destructor. | |
| IntegerProgram & | getIP () |
| Public access to private ip member. | |
| void | run () |
| Run search, return when all solutions have been found. | |
Private Member Functions | |
| void | branch (int depth) |
| Recursive method to search one branch. | |
| int | branchCol () |
| Choose branching column. | |
Private Attributes | |
| IntegerProgram | ip |
| Current integer program. | |
| UndoManager | um |
| Keep track of changes, used for switching between branches. | |
| Solutions & | sols |
| Record solutions. | |
| Statistics | statistics |
| Collect some statistical informations. | |
Detailed Description
Central control of branching algorithm.
This class coordinates the search for solutions. It is probably the most interesting class of the whole project.
Definition at line 35 of file BranchControl.hh.
Constructor & Destructor Documentation
| bande::BranchControl::BranchControl | ( | Solutions & | sols | ) | [inline] |
Constructor.
- Parameters:
-
sols the object where solutions will be collected.
Definition at line 43 of file BranchControl.hh.
Member Function Documentation
| void bande::BranchControl::branch | ( | int | depth | ) | [private] |
Recursive method to search one branch.
This is the central method of the whole program. Bit mask 1 in Settings::debug will enable debug output here.
For every invocation, IntegerProgram::solve will be called to determine whether the LP relaxation of the current problem is feasible, which is a neccessary condition for any feasible integral solution. If the LP is infeasible, the branch will return immediately.
If the current LP is feasible and all variables are fixed to integral values, then we have a new solution, which concludes the current branch as well.
If the LP is feasible but not all variables have been fixed, one variable is chosen using branchCol() and used for a case destinction, leading to two subtrees which are searched by recursive invocations.
- Parameters:
-
depth number of branching points between the root of the search tree and the current subtree.
Definition at line 65 of file BranchControl.cc.
References branchCol(), bande::IntegerProgram::checkIntSolution(), DBG, bande::Settings::debug, bande::IntegerProgram::dumpSolution(), bande::IntegerProgram::getColLower(), bande::IntegerProgram::getColName(), bande::IntegerProgram::getColSolution(), bande::IntegerProgram::getColUpper(), bande::Statistics::infeasible(), ip, bande::IntegerProgram::mkIntSolution(), bande::UndoState::restore(), bande::UndoManager::save(), bande::IntegerProgram::setColLower(), bande::IntegerProgram::setColUpper(), sols, bande::Statistics::solution(), bande::Solutions::solution(), bande::IntegerProgram::solve(), statistics, and um.
Referenced by run().
| int bande::BranchControl::branchCol | ( | ) | [private] |
Choose branching column.
When there are free variables left, one of them has to be chosen as the one on which the case destinction for branching will be made. This method implements a heuristic to make this choice.
The heuristic contains of two parts. First a column that currently has a "most fractional" solution is chosen, where most fractional means largest distance to nearest integer. If all columns are integral or near enough, then the second part will chose a column with minimum difference between upper and lower bound, in order to increase the number of fixed columns soon.
- Returns:
- the index of the chosen column, or -1 if all columns are already fixed
Definition at line 130 of file BranchControl.cc.
References bande::IntegerProgram::getColBounds(), bande::IntegerProgram::getColSolution(), bande::IntegerProgram::getNumCols(), and ip.
Referenced by branch().
| void bande::BranchControl::run | ( | ) |
Run search, return when all solutions have been found.
This is the public interface to start the branching algorithm.
Definition at line 36 of file BranchControl.cc.
References branch(), bande::Statistics::reset(), and statistics.
Referenced by bande::Settings::run().
Member Data Documentation
IntegerProgram bande::BranchControl::ip [private] |
Current integer program.
Initially this corresponds to the input program, but as the algorithm proceeds, tighter bounds will be placed on the variables, to reflect branching decisions.
The ip is part of BranchControl, not initialized as a separate object in Settings::run(), in order to avoid one pointer indirection when accessing this object. It can still be accessed fully through getIP().
Definition at line 71 of file BranchControl.hh.
Referenced by branch(), branchCol(), and getIP().
The documentation for this class was generated from the following files:
