Central control of branching algorithm. More...
Public Member Functions
|BranchControl (Solutions &sols)|
|IntegerProgram &||getIP ()|
|Public access to private ip member. |
|Run search, return when all solutions have been found. |
Private Member Functions
|void||branch (int depth)|
|Recursive method to search one branch. |
|Choose branching column. |
|Current integer program. |
|Keep track of changes, used for switching between branches. |
|Record solutions. |
|Collect some statistical informations. |
Central control of branching algorithm.
This class coordinates the search for solutions. It is probably the most interesting class of the whole project.
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.
|depth||number of branching points between the root of the search tree and the current subtree.|
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().
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.
Referenced by branch().
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().