|
Drake
|
|
Drake
|
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 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... | |
| 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 | |
| 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::exception | if the preconditions are not met. |
|
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.
| prog | The mixed-integer 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::exception | 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 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.
| 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.
| int NumExploredNodesInSubtree | ( | ) | const |
Returns the total number of explored nodes in the subtree (including this node if it has been explored).
|
delete |
|
delete |
| bool optimal_solution_is_integral | ( | ) | const |
Getter for optimal_solution_is_integral.
| std::exception | 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.