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.

#include <drake/solvers/branch_and_bound.h>

Classes
struct	Options
	Configuration settings for the MixedIntegerBranchAndBound constructor. More...

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, Options options=Options{})
	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_t< std::is_same_v< typename Derived::Scalar, symbolic::Variable >, MatrixLikewise< double, Derived > >	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::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. More...

template<typename Derived >
std::enable_if_t< is_eigen_scalar_same< Derived, symbolic::Variable >::value, MatrixLikewise< symbolic::Variable, Derived > >	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 MixedIntegerBranchAndBoundNode *	root () 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

Member Typedef Documentation

◆ NodeCallbackFun

using NodeCallbackFun = std::function<void( const MixedIntegerBranchAndBoundNode&, MixedIntegerBranchAndBound* bnb)>

The function signature for user defined node callback function.

◆ NodeSelectFun

using NodeSelectFun = std::function<MixedIntegerBranchAndBoundNode*( const MixedIntegerBranchAndBound&)>

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

◆ VariableSelectFun

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

Member Enumeration Documentation

◆ 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

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

Constructor & Destructor Documentation

◆ MixedIntegerBranchAndBound()

MixedIntegerBranchAndBound	(	const MathematicalProgram &	prog,
		const SolverId &	solver_id,
		Options	options = `Options{}`
	)

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.

Member Function Documentation

◆ absolute_gap_tol()

double absolute_gap_tol ( ) const

Getter for the absolute gap tolerance.

◆ best_lower_bound()

double best_lower_bound ( ) const

Getter for the best lower bound.

◆ best_upper_bound()

double best_upper_bound ( ) const

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::exception if the pre-condition fails.

◆ GetNewVariables()

std::enable_if_t< is_eigen_scalar_same<Derived, symbolic::Variable>::value, MatrixLikewise<symbolic::Variable, Derived> > 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.

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::exception if the preconditions are not satisfied.

◆ GetSolution() [2/2]

std::enable_if_t< std::is_same_v<typename Derived::Scalar, symbolic::Variable>, MatrixLikewise<double, Derived> > GetSolution	(	const Eigen::MatrixBase< Derived > &	mip_vars,
		int	nth_best_solution = `0`
	)		const

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::exception 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::exception 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:

The optimization problem in the node is infeasible.
The optimal cost of the node is larger than the best upper bound.
The optimal solution to the node satisfies all the integral constraints.
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::exception if the precondition is not satisfied.

◆ relative_gap_tol()

double relative_gap_tol ( ) const

Geeter for the relative gap tolerance.

◆ root()

const MixedIntegerBranchAndBoundNode* root ( ) const

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 )

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 )

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 )

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 )

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 )

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 )

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
}
MixedIntegerBranchAndBound bnb(...);
bnb.SetNodeSelectionMethod(
    MixedIntegerBranchAndBound::NodeSelectionMethod::kUserDefined);
// 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::exception if the node is not a leaf node, or it is fathomed.

◆ SetUserDefinedVariableSelectionFunction()

void SetUserDefinedVariableSelectionFunction ( VariableSelectFun fun )

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

MixedIntegerBranchAndBound bnb(...);
bnb.SetVariableSelectionMethod(
    MixedIntegerBranchAndBound:VariableSelectionMethod::kUserDefined);
// Set VariableSelectFun by using a function pointer.
bnb.SetUserDefinedVariableSelectionFunction(FirstVariable);

◆ SetVariableSelectionMethod()

void SetVariableSelectionMethod ( VariableSelectionMethod variable_selection_method )

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<double, Eigen::VectorXd>& solutions ( ) const

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.

Friends And Related Function Documentation

◆ MixedIntegerBranchAndBoundTester

friend class MixedIntegerBranchAndBoundTester

friend

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

drake/solvers/branch_and_bound.h

Detailed Description

Classes

Public Types

Public Member Functions

Friends

Member Typedef Documentation

◆ NodeCallbackFun

◆ NodeSelectFun

◆ VariableSelectFun

Member Enumeration Documentation

◆ NodeSelectionMethod

◆ VariableSelectionMethod

Constructor & Destructor Documentation

◆ MixedIntegerBranchAndBound()

Member Function Documentation

◆ absolute_gap_tol()

◆ best_lower_bound()

◆ best_upper_bound()

◆ GetNewVariable()

◆ GetNewVariables()

◆ GetOptimalCost()

◆ GetSolution() [1/2]

◆ GetSolution() [2/2]

◆ GetSubOptimalCost()

◆ IsLeafNodeFathomed()

◆ relative_gap_tol()

◆ root()

◆ set_absolute_gap_tol()

◆ set_relative_gap_tol()

◆ SetNodeSelectionMethod()

◆ SetSearchIntegralSolutionByRounding()

◆ SetUserDefinedNodeCallbackFunction()

◆ SetUserDefinedNodeSelectionFunction()

◆ SetUserDefinedVariableSelectionFunction()

◆ SetVariableSelectionMethod()

◆ solutions()

◆ Solve()

Friends And Related Function Documentation

◆ MixedIntegerBranchAndBoundTester