Drake
MixedIntegerBranchAndBound Class Reference

Given a mixed-integer optimization problem (MIP) (or more accurately, mixed binary problem), solve this problem through branch-and-bound process. More...

#include <drake/solvers/branch_and_bound.h>

## Public Types

enum  VariableSelectionMethod { kUserDefined, kLeastAmbivalent, kMostAmbivalent }
Different methods to pick a branching variable. More...

enum  NodeSelectionMethod { kUserDefined, kDepthFirst, kMinLowerBound }
Different methods to pick a branching node. More...

using NodeSelectFun = std::function< MixedIntegerBranchAndBoundNode *(const MixedIntegerBranchAndBound &)>
The function signature for the user defined method to pick a branching node or a branching variable. More...

using VariableSelectFun = std::function< const symbolic::Variable *(const MixedIntegerBranchAndBoundNode &)>

using NodeCallbackFun = std::function< void(const MixedIntegerBranchAndBoundNode &, MixedIntegerBranchAndBound *bnb)>
The function signature for user defined node callback function. More...

## Public Member Functions

MixedIntegerBranchAndBound (const MathematicalProgram &prog, const SolverId &solver_id)
Construct a branch-and-bound tree from a mixed-integer optimization program. More...

SolutionResult Solve ()
Solve the mixed-integer problem (MIP) through a branch and bound process. More...

double GetOptimalCost () const
Get the optimal cost. More...

double GetSubOptimalCost (int nth_suboptimal_cost) const
Get the n'th sub-optimal cost. More...

double GetSolution (const symbolic::Variable &mip_var, int nth_best_solution=0) const
Get the n'th best integral solution for a variable. More...

template<typename Derived >
std::enable_if< std::is_same< typename Derived::Scalar, symbolic::Variable >::value, Eigen::Matrix< double, Derived::RowsAtCompileTime, Derived::ColsAtCompileTime > >::type GetSolution (const Eigen::MatrixBase< Derived > &mip_vars, int nth_best_solution=0) const
Get the n'th best integral solution for some variables. More...

const symbolic::VariableGetNewVariable (const symbolic::Variable &old_variable) const
Given an old variable in the original mixed-integer program, return the corresponding new variable in the branch-and-bound process. More...

template<typename Derived >
std::enable_if< is_eigen_scalar_same< Derived, symbolic::Variable >::value, MatrixDecisionVariable< Derived::RowsAtCompileTime, Derived::ColsAtCompileTime > >::type GetNewVariables (const Eigen::MatrixBase< Derived > &old_variables) const
Given a matrix of old variables in the original mixed-integer program, return a matrix of corresponding new variables in the branch-and-bound process. More...

void SetNodeSelectionMethod (NodeSelectionMethod node_selection_method)
The user can choose the method to pick a node for branching. More...

void SetUserDefinedNodeSelectionFunction (NodeSelectFun fun)
Set the user-defined method to pick the branching node. More...

void SetVariableSelectionMethod (VariableSelectionMethod variable_selection_method)
The user can choose the method to pick a variable for branching in each node. More...

void SetUserDefinedVariableSelectionFunction (VariableSelectFun fun)
Set the user-defined method to pick the branching variable. More...

void SetSearchIntegralSolutionByRounding (bool flag)
Set the flag to true if the user wants to search an integral solution in each node, after the optimization problem in that node is solved. More...

void SetUserDefinedNodeCallbackFunction (NodeCallbackFun fun)
The user can set a defined callback function in each node. More...

bool IsLeafNodeFathomed (const MixedIntegerBranchAndBoundNode &leaf_node) const
If a leaf node is fathomed, then there is no need to branch on this node any more. More...

const MixedIntegerBranchAndBoundNoderoot () const
Getter for the root node. More...

double best_upper_bound () const
Getter for the best upper bound. More...

double best_lower_bound () const
Getter for the best lower bound. More...

const std::multimap< double, Eigen::VectorXd > & solutions () const
Getter for the solutions. More...

void set_absolute_gap_tol (double tol)
Setter for the absolute gap tolerance. More...

double absolute_gap_tol () const
Getter for the absolute gap tolerance. More...

void set_relative_gap_tol (double tol)
Setter for the relative gap tolerance. More...

double relative_gap_tol () const
Geeter for the relative gap tolerance. More...

## Friends

class MixedIntegerBranchAndBoundTester

## Detailed Description

Given a mixed-integer optimization problem (MIP) (or more accurately, mixed binary problem), solve this problem through branch-and-bound process.

We will first replace all the binary variables with continuous variables, and relax the integral constraint on the binary variables z ∈ {0, 1} with continuous constraints 0 ≤ z ≤ 1. In the subsequent steps, at each node of the tree, we will fix some binary variables to either 0 or 1, and solve the rest of the variables. Notice that we will create a new set of variables in the branch-and-bound process, since we need to replace the binary variables with continuous variables.

## ◆ NodeCallbackFun

 using NodeCallbackFun = std::function

The function signature for user defined node callback function.

## ◆ NodeSelectFun

 using NodeSelectFun = std::function

The function signature for the user defined method to pick a branching node or a branching variable.

## ◆ VariableSelectFun

 using VariableSelectFun = std::function

## ◆ NodeSelectionMethod

 enum NodeSelectionMethod
strong

Different methods to pick a branching node.

Enumerator
kUserDefined

User defined.

kDepthFirst

Pick the node with the most binary variables fixed.

kMinLowerBound

Pick the node with the smallest optimal cost.

## ◆ VariableSelectionMethod

 strong

Different methods to pick a branching variable.

Enumerator
kUserDefined

User defined.

kLeastAmbivalent

Pick the variable whose value is closest to 0 or 1.

kMostAmbivalent

Pick the variable whose value is closest to 0.5.

## ◆ MixedIntegerBranchAndBound()

 MixedIntegerBranchAndBound ( const MathematicalProgram & prog, const SolverId & solver_id )
explicit

Construct a branch-and-bound tree from a mixed-integer optimization program.

Parameters
 prog A mixed-integer optimization program. solver_id The ID of the solver for the optimization.

## ◆ absolute_gap_tol()

 double absolute_gap_tol ( ) const
inline

Getter for the absolute gap tolerance.

## ◆ best_lower_bound()

 double best_lower_bound ( ) const
inline

Getter for the best lower bound.

## ◆ best_upper_bound()

 double best_upper_bound ( ) const
inline

Getter for the best upper bound.

## ◆ GetNewVariable()

 const symbolic::Variable & GetNewVariable ( const symbolic::Variable & old_variable ) const

Given an old variable in the original mixed-integer program, return the corresponding new variable in the branch-and-bound process.

Parameters
 old_variable A variable in the original mixed-integer program.
Return values
 new_variable The corresponding variable in the branch-and-bound procedure.
Precondition
old_variable is a variable in the mixed-integer program, passed in the constructor of this MixedIntegerBranchAndBound.
Exceptions
 std::runtime_error if the pre-condition fails.

## ◆ GetNewVariables()

 std::enable_if< is_eigen_scalar_same::value, MatrixDecisionVariable >::type GetNewVariables ( const Eigen::MatrixBase< Derived > & old_variables ) const
inline

Given a matrix of old variables in the original mixed-integer program, return a matrix of corresponding new variables in the branch-and-bound process.

Parameters
 old_variables Variables in the original mixed-integer program.
Return values
 new_variables The corresponding variables in the branch-and-bound procedure.

## ◆ GetOptimalCost()

 double GetOptimalCost ( ) const

Get the optimal cost.

## ◆ GetSolution() [1/2]

 double GetSolution ( const symbolic::Variable & mip_var, int nth_best_solution = 0 ) const

Get the n'th best integral solution for a variable.

The best solutions are sorted in the ascending order based on their costs. Each solution is found in a separate node in the branch-and-bound tree, so the values of the binary variables are different in each solution.

Parameters
 mip_var A variable in the original MIP. nth_best_solution. The index of the best integral solution.
Precondition
mip_var is a variable in the original MIP.
nth_best_solution is between 0 and solutions().size().
Exceptions
 std::runtime_error if the preconditions are not satisfied.

## ◆ GetSolution() [2/2]

 std::enable_if< std::is_same::value, Eigen::Matrix >::type GetSolution ( const Eigen::MatrixBase< Derived > & mip_vars, int nth_best_solution = 0 ) const
inline

Get the n'th best integral solution for some variables.

The best solutions are sorted in the ascending order based on their costs. Each solution is found in a separate node in the branch-and-bound tree, so

Parameters
 mip_vars Variables in the original MIP. nth_best_solution. The index of the best integral solution.
Precondition
mip_vars are variables in the original MIP.
nth_best_solution is between 0 and solutions().size().
Exceptions
 std::runtime_error if the preconditions are not satisfied.

## ◆ GetSubOptimalCost()

 double GetSubOptimalCost ( int nth_suboptimal_cost ) const

Get the n'th sub-optimal cost.

The costs are sorted in the ascending order. The sub-optimal costs do not include the optimal cost.

Parameters
 nth_suboptimal_cost The n'th sub-optimal cost.
Precondition
nth_suboptimal_cost is between 0 and solutions().size() - 1.
Exceptions
 std::runtime_error if the precondition is not satisfied.

## ◆ IsLeafNodeFathomed()

 bool IsLeafNodeFathomed ( const MixedIntegerBranchAndBoundNode & leaf_node ) const

If a leaf node is fathomed, then there is no need to branch on this node any more.

A leaf node is fathomed is any of the following conditions are satisfied:

1. The optimization problem in the node is infeasible.
2. The optimal cost of the node is larger than the best upper bound.
3. The optimal solution to the node satisfies all the integral constraints.
4. All binary variables are fixed to either 0 or 1 in this node.
Parameters
 leaf_node A leaf node to check if it is fathomed.
Precondition
The node should be a leaf node.
Exceptions
 std::runtime_error if the precondition is not satisfied.

## ◆ relative_gap_tol()

 double relative_gap_tol ( ) const
inline

Geeter for the relative gap tolerance.

## ◆ root()

 const MixedIntegerBranchAndBoundNode* root ( ) const
inline

Getter for the root node.

Note that this is aliased for the lifetime of this object.

## ◆ set_absolute_gap_tol()

 void set_absolute_gap_tol ( double tol )
inline

Setter for the absolute gap tolerance.

The branch-and-bound will terminate if its difference between its best upper bound and best lower bound is below this gap tolerance.

## ◆ set_relative_gap_tol()

 void set_relative_gap_tol ( double tol )
inline

Setter for the relative gap tolerance.

The branch-and-bound will terminate if (best_upper_bound() - best_lower_bound()) / abs(best_lower_bound()) is smaller than this tolerance.

## ◆ SetNodeSelectionMethod()

 void SetNodeSelectionMethod ( NodeSelectionMethod node_selection_method )
inline

The user can choose the method to pick a node for branching.

We provide options such as "depth first" or "min lower bound".

Parameters
 node_selection_method The option to pick a node. If the option is NodeSelectionMethod::kUserDefined, then the user should also provide the method to pick a node through SetUserDefinedNodeSelectionFunction.

## ◆ SetSearchIntegralSolutionByRounding()

 void SetSearchIntegralSolutionByRounding ( bool flag )
inline

Set the flag to true if the user wants to search an integral solution in each node, after the optimization problem in that node is solved.

The program can search for an integral solution based on the solution to the optimization program in the node, by rounding the binary variables to the nearest integer value, and solve for the continuous variables. If a solution is obtained in this new program, then this solution is an integral solution to the mixed-integer program.

## ◆ SetUserDefinedNodeCallbackFunction()

 void SetUserDefinedNodeCallbackFunction ( NodeCallbackFun fun )
inline

The user can set a defined callback function in each node.

This function is called after the optimization is solved in each node.

## ◆ SetUserDefinedNodeSelectionFunction()

 void SetUserDefinedNodeSelectionFunction ( NodeSelectFun fun )
inline

Set the user-defined method to pick the branching node.

This method is used if the user calls SetNodeSelectionMethod(NodeSelectionMethod::kUserDefined).

For example, if the user has defined a function LeftMostNode that would return the left-most unfathomed node in the tree, then the user could do

MixedIntegerBranchAndBoundNode* LeftMostNodeInSubTree(
const MixedIntegerBranchAndBound& branch_and_bound,
const MixedIntegerBranchAndBoundNode& subtree_root) {
// Starting from the subtree root, find the left most leaf node that is
not fathomed.
blah
}
// Use a lambda function as the NodeSelectionFun
bnb->SetUserDefinedNodeSelectionFunction([](
const MixedIntegerBranchAndBound& branch_and_bound) {
return LeftMostNodeInSubTree(branch_and_bound,
*(branch_and_bound.root()));

A more detailed example can be found in solvers/test/branch_and_bound_test.cc in TestSetUserDefinedNodeSelectionFunction.

Note
The user defined function should pick an un-fathomed leaf node for branching.
Exceptions
 std::_runtime error if the node is not a leaf node, or it is fathomed.

## ◆ SetUserDefinedVariableSelectionFunction()

 void SetUserDefinedVariableSelectionFunction ( VariableSelectFun fun )
inline

Set the user-defined method to pick the branching variable.

This method is used if the user calls SetVariableSelectionMethod(VariableSelectionMethod::kUserDefined).

For example, if the user has defined a function FirstVariable, that would return the first un-fixed binary variable in this branch as

SymbolicVariable* FirstVariable(const MixedIntegerBranchAndBoundNode& node)
{
return node.remaining_binary_variables().begin();
}

The user can then set the branch-and-bound to use this function to select the branching variable as

// Set VariableSelectFun by using a function pointer.
bnb.SetUserDefinedVariableSelectionFunction(FirstVariable);

## ◆ SetVariableSelectionMethod()

 void SetVariableSelectionMethod ( VariableSelectionMethod variable_selection_method )
inline

The user can choose the method to pick a variable for branching in each node.

We provide options such as "most ambivalent" or "least ambivalent".

Parameters
 variable_selection_method The option to pick a variable. If the option is VariableSelectionMethod::kUserDefined, then the user should also provide the method to pick a variable through SetUserDefinedVariableSelectionFunction(...).

## ◆ solutions()

 const std::multimap& solutions ( ) const
inline

Getter for the solutions.

Returns a list of solutions, together with the costs evaluated at the solutions. The solutions are sorted in the ascending order based on the cost.

## ◆ Solve()

 SolutionResult Solve ( )

Solve the mixed-integer problem (MIP) through a branch and bound process.

Return values
 solution_result If solution_result=SolutionResult::kSolutionFound, then the best solutions are stored inside solutions(). The user can access the value of each variable(s) through GetSolution(...). If solution_result=SolutionResult::kInfeasibleConstraints, then the mixed-integer problem is primal infeasible. If solution_result=SolutionResult::kUnbounded, then the mixed-integer problem is primal unbounded.

## ◆ MixedIntegerBranchAndBoundTester

 friend class MixedIntegerBranchAndBoundTester
friend

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