Drake
MixedIntegerBranchAndBound Class Reference

Given a mixed-integer optimization problem (MIP) (or more accurately, mixed binary problem), solve this problem through branch-and-bound process. More...

#include <drake/solvers/branch_and_bound.h>

Public Types

enum  VariableSelectionMethod { kUserDefined, kLeastAmbivalent, kMostAmbivalent }
 Different methods to pick a branching variable. More...
 
enum  NodeSelectionMethod { kUserDefined, kDepthFirst, kMinLowerBound }
 Different methods to pick a branching node. More...
 
using NodeSelectFun = std::function< MixedIntegerBranchAndBoundNode *(const MixedIntegerBranchAndBound &)>
 The function signature for the user defined method to pick a branching node or a branching variable. More...
 
using VariableSelectFun = std::function< const symbolic::Variable *(const MixedIntegerBranchAndBoundNode &)>
 
using NodeCallbackFun = std::function< void(const MixedIntegerBranchAndBoundNode &, MixedIntegerBranchAndBound *bnb)>
 The function signature for user defined node callback function. More...
 

Public Member Functions

 MixedIntegerBranchAndBound (const MathematicalProgram &prog, const SolverId &solver_id)
 Construct a branch-and-bound tree from a mixed-integer optimization program. More...
 
SolutionResult Solve ()
 Solve the mixed-integer problem (MIP) through a branch and bound process. More...
 
double GetOptimalCost () const
 Get the optimal cost. More...
 
double GetSubOptimalCost (int nth_suboptimal_cost) const
 Get the n'th sub-optimal cost. More...
 
double GetSolution (const symbolic::Variable &mip_var, int nth_best_solution=0) const
 Get the n'th best integral solution for a variable. More...
 
template<typename Derived >
std::enable_if< std::is_same< typename Derived::Scalar, symbolic::Variable >::value, Eigen::Matrix< double, Derived::RowsAtCompileTime, Derived::ColsAtCompileTime > >::type GetSolution (const Eigen::MatrixBase< Derived > &mip_vars, int nth_best_solution=0) const
 Get the n'th best integral solution for some variables. More...
 
const symbolic::VariableGetNewVariable (const symbolic::Variable &old_variable) const
 Given an old variable in the original mixed-integer program, return the corresponding new variable in the branch-and-bound process. More...
 
template<typename Derived >
std::enable_if< is_eigen_scalar_same< Derived, symbolic::Variable >::value, MatrixDecisionVariable< Derived::RowsAtCompileTime, Derived::ColsAtCompileTime > >::type GetNewVariables (const Eigen::MatrixBase< Derived > &old_variables) const
 Given a matrix of old variables in the original mixed-integer program, return a matrix of corresponding new variables in the branch-and-bound process. More...
 
void SetNodeSelectionMethod (NodeSelectionMethod node_selection_method)
 The user can choose the method to pick a node for branching. More...
 
void SetUserDefinedNodeSelectionFunction (NodeSelectFun fun)
 Set the user-defined method to pick the branching node. More...
 
void SetVariableSelectionMethod (VariableSelectionMethod variable_selection_method)
 The user can choose the method to pick a variable for branching in each node. More...
 
void SetUserDefinedVariableSelectionFunction (VariableSelectFun fun)
 Set the user-defined method to pick the branching variable. More...
 
void SetSearchIntegralSolutionByRounding (bool flag)
 Set the flag to true if the user wants to search an integral solution in each node, after the optimization problem in that node is solved. More...
 
void SetUserDefinedNodeCallbackFunction (NodeCallbackFun fun)
 The user can set a defined callback function in each node. More...
 
bool IsLeafNodeFathomed (const MixedIntegerBranchAndBoundNode &leaf_node) const
 If a leaf node is fathomed, then there is no need to branch on this node any more. More...
 
const MixedIntegerBranchAndBoundNoderoot () const
 Getter for the root node. More...
 
double best_upper_bound () const
 Getter for the best upper bound. More...
 
double best_lower_bound () const
 Getter for the best lower bound. More...
 
const std::multimap< double, Eigen::VectorXd > & solutions () const
 Getter for the solutions. More...
 
void set_absolute_gap_tol (double tol)
 Setter for the absolute gap tolerance. More...
 
double absolute_gap_tol () const
 Getter for the absolute gap tolerance. More...
 
void set_relative_gap_tol (double tol)
 Setter for the relative gap tolerance. More...
 
double relative_gap_tol () const
 Geeter for the relative gap tolerance. More...
 

Friends

class MixedIntegerBranchAndBoundTester
 

Detailed Description

Given a mixed-integer optimization problem (MIP) (or more accurately, mixed binary problem), solve this problem through branch-and-bound process.

We will first replace all the binary variables with continuous variables, and relax the integral constraint on the binary variables z ∈ {0, 1} with continuous constraints 0 ≤ z ≤ 1. In the subsequent steps, at each node of the tree, we will fix some binary variables to either 0 or 1, and solve the rest of the variables. Notice that we will create a new set of variables in the branch-and-bound process, since we need to replace the binary variables with continuous variables.

Member Typedef Documentation

◆ NodeCallbackFun

The function signature for user defined node callback function.

◆ NodeSelectFun

The function signature for the user defined method to pick a branching node or a branching variable.

◆ VariableSelectFun

Member Enumeration Documentation

◆ NodeSelectionMethod

enum NodeSelectionMethod
strong

Different methods to pick a branching node.

Enumerator
kUserDefined 

User defined.

kDepthFirst 

Pick the node with the most binary variables fixed.

kMinLowerBound 

Pick the node with the smallest optimal cost.

◆ VariableSelectionMethod

Different methods to pick a branching variable.

Enumerator
kUserDefined 

User defined.

kLeastAmbivalent 

Pick the variable whose value is closest to 0 or 1.

kMostAmbivalent 

Pick the variable whose value is closest to 0.5.

Constructor & Destructor Documentation

◆ MixedIntegerBranchAndBound()

MixedIntegerBranchAndBound ( const MathematicalProgram prog,
const SolverId solver_id 
)
explicit

Construct a branch-and-bound tree from a mixed-integer optimization program.

Parameters
progA mixed-integer optimization program.
solver_idThe ID of the solver for the optimization.

Member Function Documentation

◆ absolute_gap_tol()

double absolute_gap_tol ( ) const
inline

Getter for the absolute gap tolerance.

◆ best_lower_bound()

double best_lower_bound ( ) const
inline

Getter for the best lower bound.

◆ best_upper_bound()

double best_upper_bound ( ) const
inline

Getter for the best upper bound.

◆ GetNewVariable()

const symbolic::Variable & GetNewVariable ( const symbolic::Variable old_variable) const

Given an old variable in the original mixed-integer program, return the corresponding new variable in the branch-and-bound process.

Parameters
old_variableA variable in the original mixed-integer program.
Return values
new_variableThe corresponding variable in the branch-and-bound procedure.
Precondition
old_variable is a variable in the mixed-integer program, passed in the constructor of this MixedIntegerBranchAndBound.
Exceptions
std::runtime_errorif the pre-condition fails.

◆ GetNewVariables()

std::enable_if< is_eigen_scalar_same<Derived, symbolic::Variable>::value, MatrixDecisionVariable<Derived::RowsAtCompileTime, Derived::ColsAtCompileTime> >::type GetNewVariables ( const Eigen::MatrixBase< Derived > &  old_variables) const
inline

Given a matrix of old variables in the original mixed-integer program, return a matrix of corresponding new variables in the branch-and-bound process.

Parameters
old_variablesVariables in the original mixed-integer program.
Return values
new_variablesThe corresponding variables in the branch-and-bound procedure.

◆ GetOptimalCost()

double GetOptimalCost ( ) const

Get the optimal cost.

◆ GetSolution() [1/2]

double GetSolution ( const symbolic::Variable mip_var,
int  nth_best_solution = 0 
) const

Get the n'th best integral solution for a variable.

The best solutions are sorted in the ascending order based on their costs. Each solution is found in a separate node in the branch-and-bound tree, so the values of the binary variables are different in each solution.

Parameters
mip_varA variable in the original MIP.
nth_best_solution.The index of the best integral solution.
Precondition
mip_var is a variable in the original MIP.
nth_best_solution is between 0 and solutions().size().
Exceptions
std::runtime_errorif the preconditions are not satisfied.

◆ GetSolution() [2/2]

std::enable_if< std::is_same<typename Derived::Scalar, symbolic::Variable>::value, Eigen::Matrix<double, Derived::RowsAtCompileTime, Derived::ColsAtCompileTime> >::type GetSolution ( const Eigen::MatrixBase< Derived > &  mip_vars,
int  nth_best_solution = 0 
) const
inline

Get the n'th best integral solution for some variables.

The best solutions are sorted in the ascending order based on their costs. Each solution is found in a separate node in the branch-and-bound tree, so

Parameters
mip_varsVariables in the original MIP.
nth_best_solution.The index of the best integral solution.
Precondition
mip_vars are variables in the original MIP.
nth_best_solution is between 0 and solutions().size().
Exceptions
std::runtime_errorif the preconditions are not satisfied.

◆ GetSubOptimalCost()

double GetSubOptimalCost ( int  nth_suboptimal_cost) const

Get the n'th sub-optimal cost.

The costs are sorted in the ascending order. The sub-optimal costs do not include the optimal cost.

Parameters
nth_suboptimal_costThe n'th sub-optimal cost.
Precondition
nth_suboptimal_cost is between 0 and solutions().size() - 1.
Exceptions
std::runtime_errorif the precondition is not satisfied.

◆ IsLeafNodeFathomed()

bool IsLeafNodeFathomed ( const MixedIntegerBranchAndBoundNode leaf_node) const

If a leaf node is fathomed, then there is no need to branch on this node any more.

A leaf node is fathomed is any of the following conditions are satisfied:

  1. The optimization problem in the node is infeasible.
  2. The optimal cost of the node is larger than the best upper bound.
  3. The optimal solution to the node satisfies all the integral constraints.
  4. All binary variables are fixed to either 0 or 1 in this node.
Parameters
leaf_nodeA leaf node to check if it is fathomed.
Precondition
The node should be a leaf node.
Exceptions
std::runtime_errorif the precondition is not satisfied.

◆ relative_gap_tol()

double relative_gap_tol ( ) const
inline

Geeter for the relative gap tolerance.

◆ root()

const MixedIntegerBranchAndBoundNode* root ( ) const
inline

Getter for the root node.

Note that this is aliased for the lifetime of this object.

◆ set_absolute_gap_tol()

void set_absolute_gap_tol ( double  tol)
inline

Setter for the absolute gap tolerance.

The branch-and-bound will terminate if its difference between its best upper bound and best lower bound is below this gap tolerance.

◆ set_relative_gap_tol()

void set_relative_gap_tol ( double  tol)
inline

Setter for the relative gap tolerance.

The branch-and-bound will terminate if (best_upper_bound() - best_lower_bound()) / abs(best_lower_bound()) is smaller than this tolerance.

◆ SetNodeSelectionMethod()

void SetNodeSelectionMethod ( NodeSelectionMethod  node_selection_method)
inline

The user can choose the method to pick a node for branching.

We provide options such as "depth first" or "min lower bound".

Parameters
node_selection_methodThe option to pick a node. If the option is NodeSelectionMethod::kUserDefined, then the user should also provide the method to pick a node through SetUserDefinedNodeSelectionFunction.

◆ SetSearchIntegralSolutionByRounding()

void SetSearchIntegralSolutionByRounding ( bool  flag)
inline

Set the flag to true if the user wants to search an integral solution in each node, after the optimization problem in that node is solved.

The program can search for an integral solution based on the solution to the optimization program in the node, by rounding the binary variables to the nearest integer value, and solve for the continuous variables. If a solution is obtained in this new program, then this solution is an integral solution to the mixed-integer program.

◆ SetUserDefinedNodeCallbackFunction()

void SetUserDefinedNodeCallbackFunction ( NodeCallbackFun  fun)
inline

The user can set a defined callback function in each node.

This function is called after the optimization is solved in each node.

◆ SetUserDefinedNodeSelectionFunction()

void SetUserDefinedNodeSelectionFunction ( NodeSelectFun  fun)
inline

Set the user-defined method to pick the branching node.

This method is used if the user calls SetNodeSelectionMethod(NodeSelectionMethod::kUserDefined).

For example, if the user has defined a function LeftMostNode that would return the left-most unfathomed node in the tree, then the user could do

MixedIntegerBranchAndBoundNode* LeftMostNodeInSubTree(
const MixedIntegerBranchAndBound& branch_and_bound,
const MixedIntegerBranchAndBoundNode& subtree_root) {
// Starting from the subtree root, find the left most leaf node that is
not fathomed.
blah
}
// Use a lambda function as the NodeSelectionFun
bnb->SetUserDefinedNodeSelectionFunction([](
const MixedIntegerBranchAndBound& branch_and_bound) {
return LeftMostNodeInSubTree(branch_and_bound,
*(branch_and_bound.root()));

A more detailed example can be found in solvers/test/branch_and_bound_test.cc in TestSetUserDefinedNodeSelectionFunction.

Note
The user defined function should pick an un-fathomed leaf node for branching.
Exceptions
std::_runtimeerror if the node is not a leaf node, or it is fathomed.

◆ SetUserDefinedVariableSelectionFunction()

void SetUserDefinedVariableSelectionFunction ( VariableSelectFun  fun)
inline

Set the user-defined method to pick the branching variable.

This method is used if the user calls SetVariableSelectionMethod(VariableSelectionMethod::kUserDefined).

For example, if the user has defined a function FirstVariable, that would return the first un-fixed binary variable in this branch as

SymbolicVariable* FirstVariable(const MixedIntegerBranchAndBoundNode& node)
{
return node.remaining_binary_variables().begin();
}

The user can then set the branch-and-bound to use this function to select the branching variable as

// Set VariableSelectFun by using a function pointer.
bnb.SetUserDefinedVariableSelectionFunction(FirstVariable);

◆ SetVariableSelectionMethod()

void SetVariableSelectionMethod ( VariableSelectionMethod  variable_selection_method)
inline

The user can choose the method to pick a variable for branching in each node.

We provide options such as "most ambivalent" or "least ambivalent".

Parameters
variable_selection_methodThe option to pick a variable. If the option is VariableSelectionMethod::kUserDefined, then the user should also provide the method to pick a variable through SetUserDefinedVariableSelectionFunction(...).

◆ solutions()

const std::multimap<double, Eigen::VectorXd>& solutions ( ) const
inline

Getter for the solutions.

Returns a list of solutions, together with the costs evaluated at the solutions. The solutions are sorted in the ascending order based on the cost.

◆ Solve()

SolutionResult Solve ( )

Solve the mixed-integer problem (MIP) through a branch and bound process.

Return values
solution_resultIf solution_result=SolutionResult::kSolutionFound, then the best solutions are stored inside solutions(). The user can access the value of each variable(s) through GetSolution(...). If solution_result=SolutionResult::kInfeasibleConstraints, then the mixed-integer problem is primal infeasible. If solution_result=SolutionResult::kUnbounded, then the mixed-integer problem is primal unbounded.

Friends And Related Function Documentation

◆ MixedIntegerBranchAndBoundTester

friend class MixedIntegerBranchAndBoundTester
friend

The documentation for this class was generated from the following files: