Drake
Drake C++ Documentation
MixedIntegerBranchAndBoundNode Class Reference

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.

#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 MathematicalProgramResultprog_result () const
 Getter for the mathematical program result. 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...
 
bool is_explored () const
 If the mathematical program in this node has been solved and the result is stored inside this node, then we say this node has been explored. More...
 
int NumExploredNodesInSubtree () const
 Returns the total number of explored nodes in the subtree (including this node if it has been explored). 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...
 

Constructor & Destructor Documentation

◆ MixedIntegerBranchAndBoundNode() [1/2]

◆ MixedIntegerBranchAndBoundNode() [2/2]

Member Function Documentation

◆ Branch()

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::exceptionif the preconditions are not met.

◆ ConstructRootNode()

static 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::exceptionif the preconditions are not met.

◆ fixed_binary_value()

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.

◆ fixed_binary_variable()

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.

◆ is_explored()

bool is_explored ( ) const

If the mathematical program in this node has been solved and the result is stored inside this node, then we say this node has been explored.

◆ IsLeaf()

bool IsLeaf ( ) const

Determine if a node is a leaf or not.

A leaf node has no child nodes.

◆ IsRoot()

bool IsRoot ( ) const

Returns true if a node is the root.

A root node has no parent.

◆ left_child()

const MixedIntegerBranchAndBoundNode* left_child ( ) const

Getter for the left child.

◆ mutable_left_child()

MixedIntegerBranchAndBoundNode* mutable_left_child ( )

Getter for the mutable left child.

◆ mutable_parent()

MixedIntegerBranchAndBoundNode* mutable_parent ( )

Getter for the mutable parent node.

◆ mutable_right_child()

MixedIntegerBranchAndBoundNode* mutable_right_child ( )

Getter for the mutable right child.

◆ NumExploredNodesInSubtree()

int NumExploredNodesInSubtree ( ) const

Returns the total number of explored nodes in the subtree (including this node if it has been explored).

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ optimal_solution_is_integral()

bool optimal_solution_is_integral ( ) const

Getter for optimal_solution_is_integral.

Precondition
The optimization problem is solved successfully.
Exceptions
std::exceptionif the precondition is not satisfied.

◆ parent()

const MixedIntegerBranchAndBoundNode* parent ( ) const

Getter for the parent node.

◆ prog()

const MathematicalProgram* prog ( ) const

Getter for the mathematical program.

◆ prog_result()

const MathematicalProgramResult* prog_result ( ) const

Getter for the mathematical program result.

◆ remaining_binary_variables()

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

Getter for the remaining binary variables in this node.

◆ right_child()

const MixedIntegerBranchAndBoundNode* right_child ( ) const

Getter for the right child.

◆ solution_result()

SolutionResult solution_result ( ) const

Getter for the solution result when solving the optimization program.

◆ solver_id()

const SolverId& solver_id ( ) const

Getter for solver id.


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