Drake

A node in the branchandbound (bnb) tree.
The whole branchandbound tree solves the mixedinteger problem min f(x) (1) s.t g(x) ≤ 0 z ∈ {0, 1} where the binary variables z are a subset of the decision variables x. In this node, we will fix some binary variables to either 0 and 1, and relax the rest of the binary variables to continuous variables between 0 and 1. Namely we will solve the following problem with all variables being continuous min f(x) (2) s.t g(x) ≤ 0 z_fixed = b_fixed 0 ≤ z_relaxed ≤ 1 where z_fixed, z_relaxed is a partition of the original binary variables z. z_fixed is the fixed binary variables, z_relaxed is the relaxed binary variables. b_fixed is a vector containing the assigned values of the fixed binary variables z_fixed, b_fixed only contains value either 0 or 1.
Each node is created from its parent node, by fixing one binary variable to either 0 or 1.
#include <drake/solvers/branch_and_bound.h>
Public Member Functions  
void  Branch (const symbolic::Variable &binary_variable) 
Branches on binary_variable , and creates two child nodes. More...  
bool  IsRoot () const 
Returns true if a node is the root. More...  
bool  IsLeaf () const 
Determine if a node is a leaf or not. More...  
const MathematicalProgram *  prog () const 
Getter for the mathematical program. More...  
const MathematicalProgramResult *  prog_result () const 
Getter for the mathematical program result. More...  
const MixedIntegerBranchAndBoundNode *  left_child () const 
Getter for the left child. More...  
MixedIntegerBranchAndBoundNode *  mutable_left_child () 
Getter for the mutable left child. More...  
const MixedIntegerBranchAndBoundNode *  right_child () const 
Getter for the right child. More...  
MixedIntegerBranchAndBoundNode *  mutable_right_child () 
Getter for the mutable right child. More...  
const MixedIntegerBranchAndBoundNode *  parent () const 
Getter for the parent node. More...  
MixedIntegerBranchAndBoundNode *  mutable_parent () 
Getter for the mutable parent node. More...  
const symbolic::Variable &  fixed_binary_variable () const 
Getter for the binary variable, whose value was not fixed in the parent node, but is fixed to either 0 or 1 in this node. More...  
int  fixed_binary_value () const 
Getter for the value of the binary variable, which was not fixed in the parent node, but is fixed to either 0 or 1 in this node. More...  
const std::list< symbolic::Variable > &  remaining_binary_variables () const 
Getter for the remaining binary variables in this node. More...  
SolutionResult  solution_result () const 
Getter for the solution result when solving the optimization program. More...  
bool  optimal_solution_is_integral () const 
Getter for optimal_solution_is_integral. More...  
const SolverId &  solver_id () const 
Getter for solver id. More...  
Does not allow copy, move, or assignment  
MixedIntegerBranchAndBoundNode (const MixedIntegerBranchAndBoundNode &)=delete  
MixedIntegerBranchAndBoundNode &  operator= (const MixedIntegerBranchAndBoundNode &)=delete 
MixedIntegerBranchAndBoundNode (MixedIntegerBranchAndBoundNode &&)=delete  
MixedIntegerBranchAndBoundNode &  operator= (MixedIntegerBranchAndBoundNode &&)=delete 
Static Public Member Functions  
static std::pair< std::unique_ptr< MixedIntegerBranchAndBoundNode >, std::unordered_map< symbolic::Variable::Id, symbolic::Variable > >  ConstructRootNode (const MathematicalProgram &prog, const SolverId &solver_id) 
Construct the root node from an optimization program. More...  

delete 

delete 
void Branch  (  const symbolic::Variable &  binary_variable  ) 
Branches on binary_variable
, and creates two child nodes.
In the left child node, the binary variable is fixed to 0. In the right node, the binary variable is fixed to 1. Solves the optimization program in each child node.
binary_variable  This binary variable is fixed to either 0 or 1 in the child node. 
std::runtime_error  if the preconditions are not met. 

static 
Construct the root node from an optimization program.
For the mixedinteger optimization program min f(x) (1) s.t g(x) ≤ 0 z ∈ {0, 1} we will construct a root node for this mixedinteger program. In the root node, it enforces all the costs and constraints in the original program, except the binary constraint z ∈ {0, 1}. Instead, it enforces the relaxed constraint to 0 ≤ z ≤ 1. So the root node contains the program min f(x) (2) s.t g(x) ≤ 0 0 ≤ z ≤ 1 This optimization program is solved during the node construction.
prog  The mixedinteger optimization program (1) in the documentation above. 
solver_id  The ID of the solver for the optimization program. 
(node,map_old_vars_to_new_vars)  node is the root node of the tree, that contains the optimization program (2) in the documentation above. This root node has no parent. We also need to recreate new decision variables in the root node, from the original optimization program (1), since the binary variables will be converted to continuous variables in (2). We thus return the map from the old variables to the new variables. 
std::runtime_error  if the preconditions are not met. 
int fixed_binary_value  (  )  const 
Getter for the value of the binary variable, which was not fixed in the parent node, but is fixed to either 0 or 1 in this node.
const symbolic::Variable& fixed_binary_variable  (  )  const 
Getter for the binary variable, whose value was not fixed in the parent node, but is fixed to either 0 or 1 in this node.
bool IsLeaf  (  )  const 
Determine if a node is a leaf or not.
A leaf node has no child nodes.
bool IsRoot  (  )  const 
Returns true if a node is the root.
A root node has no parent.
const MixedIntegerBranchAndBoundNode* left_child  (  )  const 
Getter for the left child.
MixedIntegerBranchAndBoundNode* mutable_left_child  (  ) 
Getter for the mutable left child.
MixedIntegerBranchAndBoundNode* mutable_parent  (  ) 
Getter for the mutable parent node.
MixedIntegerBranchAndBoundNode* mutable_right_child  (  ) 
Getter for the mutable right child.

delete 

delete 
bool optimal_solution_is_integral  (  )  const 
Getter for optimal_solution_is_integral.
std::runtime_error  if the precondition is not satisfied. 
const MixedIntegerBranchAndBoundNode* parent  (  )  const 
Getter for the parent node.
const MathematicalProgram* prog  (  )  const 
Getter for the mathematical program.
const MathematicalProgramResult* prog_result  (  )  const 
Getter for the mathematical program result.
const std::list<symbolic::Variable>& remaining_binary_variables  (  )  const 
Getter for the remaining binary variables in this node.
const MixedIntegerBranchAndBoundNode* right_child  (  )  const 
Getter for the right child.
SolutionResult solution_result  (  )  const 
Getter for the solution result when solving the optimization program.
const SolverId& solver_id  (  )  const 
Getter for solver id.