Drake
MixedIntegerBranchAndBoundNode Class Reference

A node in the branch-and-bound (bnb) tree. More...

#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 MathematicalProgramprog () const
 Getter for the mathematical program. More...
 
const MixedIntegerBranchAndBoundNodeleft_child () const
 Getter for the left child. More...
 
MixedIntegerBranchAndBoundNodemutable_left_child ()
 Getter for the mutable left child. More...
 
const MixedIntegerBranchAndBoundNoderight_child () const
 Getter for the right child. More...
 
MixedIntegerBranchAndBoundNodemutable_right_child ()
 Getter for the mutable right child. More...
 
const MixedIntegerBranchAndBoundNodeparent () const
 Getter for the parent node. More...
 
MixedIntegerBranchAndBoundNodemutable_parent ()
 Getter for the mutable parent node. More...
 
const symbolic::Variablefixed_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 SolverIdsolver_id () const
 Getter for solver id. More...
 
Does not allow copy, move, or assignment
 MixedIntegerBranchAndBoundNode (const MixedIntegerBranchAndBoundNode &)=delete
 
MixedIntegerBranchAndBoundNodeoperator= (const MixedIntegerBranchAndBoundNode &)=delete
 
 MixedIntegerBranchAndBoundNode (MixedIntegerBranchAndBoundNode &&)=delete
 
MixedIntegerBranchAndBoundNodeoperator= (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...
 

Detailed Description

A node in the branch-and-bound (bnb) tree.

The whole branch-and-bound tree solves the mixed-integer 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.

Constructor & Destructor Documentation

Here is the caller graph for this function:

Member Function Documentation

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.

Parameters
binary_variableThis binary variable is fixed to either 0 or 1 in the child node.
Precondition
binary_variable is in remaining_binary_variables_;
Exceptions
std::runtime_errorif the preconditions are not met.

Here is the call graph for this function:

Here is the caller graph for this function:

std::pair< std::unique_ptr< MixedIntegerBranchAndBoundNode >, std::unordered_map< symbolic::Variable::Id, symbolic::Variable > > ConstructRootNode ( const MathematicalProgram prog,
const SolverId solver_id 
)
static

Construct the root node from an optimization program.

For the mixed-integer optimization program min f(x) (1) s.t g(x) ≤ 0 z ∈ {0, 1} we will construct a root node for this mixed-integer 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.

Parameters
progThe mixed-integer optimization program (1) in the documentation above.
solver_idThe ID of the solver for the optimization program.
Return values
(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.
Precondition
prog should contain binary variables.
solver_id can be either Gurobi or Scs.
Exceptions
std::runtime_errorif the preconditions are not met.

Here is the call graph for this function:

Here is the caller graph for this function:

int fixed_binary_value ( ) const
inline

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
inline

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
inline

Determine if a node is a leaf or not.

A leaf node has no child nodes.

Here is the caller graph for this function:

bool IsRoot ( ) const

Returns true if a node is the root.

A root node has no parent.

Here is the call graph for this function:

const MixedIntegerBranchAndBoundNode* left_child ( ) const
inline

Getter for the left child.

Here is the caller graph for this function:

MixedIntegerBranchAndBoundNode* mutable_left_child ( )
inline

Getter for the mutable left child.

MixedIntegerBranchAndBoundNode* mutable_parent ( )
inline

Getter for the mutable parent node.

MixedIntegerBranchAndBoundNode* mutable_right_child ( )
inline

Getter for the mutable right child.

bool optimal_solution_is_integral ( ) const

Getter for optimal_solution_is_integral.

Precondition
The optimization problem is solved successfully.
Exceptions
aruntime error if the precondition is not satisfied.

Here is the caller graph for this function:

const MixedIntegerBranchAndBoundNode* parent ( ) const
inline

Getter for the parent node.

const MathematicalProgram* prog ( ) const
inline

Getter for the mathematical program.

Here is the caller graph for this function:

const std::list<symbolic::Variable>& remaining_binary_variables ( ) const
inline

Getter for the remaining binary variables in this node.

Here is the caller graph for this function:

const MixedIntegerBranchAndBoundNode* right_child ( ) const
inline

Getter for the right child.

Here is the caller graph for this function:

SolutionResult solution_result ( ) const
inline

Getter for the solution result when solving the optimization program.

Here is the call graph for this function:

Here is the caller graph for this function:

const SolverId& solver_id ( ) const
inline

Getter for solver id.

Here is the call graph for this function:

Here is the caller graph for this function:


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