bande::BranchControl Class Reference

Central control of branching algorithm. More...

#include <BranchControl.hh>

Collaboration diagram for bande::BranchControl:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 BranchControl (Solutions &sols)
 Constructor.
virtual ~BranchControl ()
 Destructor.
IntegerProgramgetIP ()
 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.
Solutionssols
 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

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:

Generated on Fri Aug 21 08:17:18 2009 for bande by  doxygen 1.6.0