Drake
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...

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...

## ◆ MixedIntegerBranchAndBoundNode() [1/2]

 MixedIntegerBranchAndBoundNode ( const MixedIntegerBranchAndBoundNode & )
delete

## ◆ MixedIntegerBranchAndBoundNode() [2/2]

 MixedIntegerBranchAndBoundNode ( MixedIntegerBranchAndBoundNode && )
delete

## ◆ 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_variable This binary variable is fixed to either 0 or 1 in the child node.
Precondition
binary_variable is in remaining_binary_variables_;
Exceptions
 std::runtime_error if the preconditions are not met.

## ◆ ConstructRootNode()

 static std::pair< std::unique_ptr, std::unordered_map > 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
 prog The mixed-integer optimization program (1) in the documentation above. solver_id The 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_error if 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.

## ◆ 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.

## ◆ operator=() [1/2]

 MixedIntegerBranchAndBoundNode& operator= ( MixedIntegerBranchAndBoundNode && )
delete

## ◆ operator=() [2/2]

 MixedIntegerBranchAndBoundNode& operator= ( const MixedIntegerBranchAndBoundNode & )
delete

## ◆ 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::runtime_error if 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& 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: