Getting Started¶
Installation¶
You can install pybnb
with pip
:
$ pip install pybnb
pybnb
requires mpi4py
to solve problems in
parallel. However, it will also solve problems in serial if
this module is not available. Thus, mpi4py
is not listed
as a package requirement, and it may need to be installed in
a separate step.
Complete Example¶
The code below shows a complete example script that (1) defines a problem, (2) creates a solver, and (3) solves the problem.
# simple.py
class Simple(pybnb.Problem):
def __init__(self):
self._xL, self._xU = 0, 1
#
# required methods
#
def sense(self):
return pybnb.minimize
def objective(self):
return round(self._xU - self._xL, 3)
def bound(self):
return -((self._xU - self._xL) ** 2)
def save_state(self, node):
node.state = (self._xL, self._xU)
def load_state(self, node):
(self._xL, self._xU) = node.state
def branch(self):
xL, xU = self._xL, self._xU
xM = 0.5 * (xL + xU)
child = pybnb.Node()
child.state = (xL, xM)
yield child
child = pybnb.Node()
child.state = (xM, xU)
yield child
#
# optional methods
#
def notify_solve_begins(self, comm, worker_comm, convergence_checker):
pass
def notify_new_best_node(self, node, current):
pass
def notify_solve_finished(self, comm, worker_comm, results):
pass
problem = Simple()
solver = pybnb.Solver()
results = solver.solve(problem, absolute_gap=1e-8)
To solve the problem in serial, the example script should be launched with the python interpretor:
$ python simple.py
To solve the problem in parallel, the example script should
be launched using the same command as above, only wrapped
with mpiexec
(specifying the number processes):
$ mpiexec -n 4 python simple.py
Note that the parallel solve implementation used by
pybnb
always designates exactly one process as a
dispatcher. If more than one process is involved in a
solve, the dispatcher will only manage the global work
queue, leaving the processing of all branch-and-bound nodes
to the remaining processes. Thus, one should not expect any
parallel speedup until at least three processes are used to
solve a problem.
More Examples¶
pybnb
is distributed with a number of example problem
implementations. Each example can be run in serial or in
parallel with the mpiexec
command. Some examples require
additional python packages or external binaries that are not
listed as dependencies for pybnb
(e.g., pyomo
). See
the comments at the top of each example file for a brief
explanation.
The examples directory included with the source repository is organized into two top-level directories.
command_line_problems: Includes basic problem implementations that expose all
pybnb
solver options as command-line arguments. Simply execute one of the available examples with--help
as an argument to see the list of available solver options.
lipschitz_1d.py (faster with
numba
, but it is optional)bin_packing.py (requires:
pyomo
+ipopt
binary)rosenbrock_2d.py (requires:
pyomo
+ipopt
binary)scripts: Includes problem implementations along with various usages of
pybnb
ranging from simple to advanced. Some of the examples accept a small set of command-line options, but mostpybnb
solver options are hard-coded and must be manually adjusted within each example file.
range_reduction_pyomo.py (requires:
pyomo
+ipopt
binary)tsp/tsp_byedge.py (requires:
numpy
)
Defining a Problem¶
To define a branch-and-bound problem with pybnb
, one
must define a class that implements the Problem
interface, which includes defining
at least the six required methods shown below.
import pybnb
class MyProblem(pybnb.Problem):
def __init__(self): ...
# required methods
def sense(self): ...
def objective(self): ...
def bound(self): ...
def save_state(self, node): ...
def load_state(self, node): ...
def branch(self): ...
# optional methods
def notify_solve_begins(self,
comm,
worker_comm,
convergence_checker):
...
def notify_new_best_node(self,
node,
current):
...
def notify_solve_finished(self,
comm,
worker_comm,
results):
...
Note
The Problem
base
class is a purely abstract interface that adds no
additional data to a problem implementation. It is not
required to call Problem.__init__
when defining the
__init__
method on a derived class.
The remainder of this section includes a detailed description of each of the required methods.
This is the easiest method to define for a branch-and-bound problem. It should return the objective sense of the problem, which should always be one of
minimize
ormaximize
, and should not change what it returns over the lifetime of a problem. For instance, to define a problem with an objective value that should be minimized, the implementation would look something like:class MyProblem(pybnb.Problem): def sense(self): return pybnb.minimizeThe
Problem
base class defines two additional convenience methodsProblem.infeasible_objective()
andProblem.unbounded_objective()
that return +inf or -inf, depending on the return value ofProblem.sense()
.This method should return a valid bound for the objective function over the current problem domain (as defined by the current problem state), or it can return
self.unbounded_objective()
if a finite bound can not be determined.This method should return a value for the objective function that is feasible for the current problem domain (as defined by the current problem state), or it can return
self.infeasible_objective()
if a feasible objective value can not be determined.This method should save any relevant state information about the problem onto the
state
attribute of node argument. If one wishes to utilize the MPI-based parallel solver, the only requirement for what goes into the node state is that it can be serialized using thepickle
ordill
modules. By default,pybnb
is configured to use thepickle
module for node serialization. See the section titled Serialization Configuration for details on how to adjust this and related settings.This method should load the problem state stored on the
state
attribute of the node argument. The code block below shows an example pair ofsave_state
andload_state
implementations.class MyProblem(pybnb.Problem): def __init__(self): self._L = 0.0 self._U = 1.0 def save_state(self, node): node.state = (self._L, self._U) def load_state(self, node): (self._L, self._U) = node.stateThis method should partition the problem domain defined by the current user state into zero or more child states and return them on new nodes. A child node can be created by directly instantiating a
pybnb.Node
object. Note that for the branching process to make sense, the bound computed from the child states should improve (or not be worse than) the bound for their parent node. Once the child bound is computed, the solver will issue a warning if it is found to be worse than the bound from its parent node, as this is indicative of a programming error or other numerical issues.Note that any child nodes returned from
Problem.branch()
will automatically be assigned the bound and objective from their parent for potential use in determining their prioritization in the global work queue. Users can override this by manually assigning a value to one or both of these node attributes before yielding them from the branch method.Additionally, further control over the prioritization of a child node can be achieved by setting the queue_strategy solve option to “custom”, and then directly assigning a value to the
queue_priority
attribute of the child node before it is yielded.
Solving a Problem¶
There are two approaches to solving a branch-and-bound
problem with pybnb
. The first is to simply call the
solve
convenience
function. This will create a Solver
object, call the Solver.solve
method, and report the results
as well as additional timing information about the solve.
import pybnb
problem = MyProblem()
results = pybnb.solve(problem,
relative_gap=1e-4)
The second approach is to manually create a Solver
object and call the
Solver.solve
method
directly.
Both approaches can solve a problem in serial or
parallel. The difference is that the solve
convenience function provides a few
additional options that simplify the process of saving
solver output and results to a file. Additionally,
collecting the timing information reported by this function
adds some additional communication overhead to the end of
the solve; thus, the second approach of directly using a
Solver
can be more efficient.
Creating a Solver¶
The following example shows how to create a solver object.
import pybnb
solver = pybnb.Solver()
By default, the solver will automatically use
mpi4py.MPI.COMM_WORLD
as the communicator, and the rank
0 process will act as the dispatcher. If the mpi4py
module is not available, this will result in an
ImportError
. The optional keywords comm and
dispatcher_rank can be used to change the default
behavior.
When a solver is created with Solver(comm=None)
, this
will disable any attempted import of mpi4py
, allowing
problems to be solved without the use of any parallel
functionality. The comm keyword can also be assigned a
communicator different from mpi4py.MPI.COMM_WORLD
. If
the solver communicator includes more than one process, the
dispatcher_rank keyword can be assigned a process rank
to control which process is designated as the dispatcher.
However the solver is initialized, the following assertions
hold true for the is_dispatcher
and is_worker
attributes of the solver
object.
if (solver.comm is None) or \
(solver.comm.size == 1):
assert solver.is_dispatcher and \
solver.is_worker
else:
if solver.comm.rank == <dispatcher_rank>:
assert solver.is_dispatcher and \
(not solver.is_worker)
else:
assert (not solver.is_dispatcher) and \
solver.is_worker
How the Solver Calls the Problem Methods¶
The following block of pseudocode provides a high-level overview of how the solver calls the methods on a user-defined problem. Highlighted lines show where problem methods are called.
1 def solve(problem, ...):
2 #
3 # solve initialization
4 #
5 sense = problem.sense()
6 problem.notify_solve_begins(...)
7 root = Node()
8 problem.save_state(root)
9
10 #
11 # solve loop
12 #
13 while <solve_not_terminated>:
14 node, best_node = dispatcher.update(...)
15 if <conditional_1>:
16 problem.notify_new_best_node(node=best_node,
17 current=False)
18 problem.load_state(node)
19 bound = problem.bound()
20 if <conditional_2>:
21 objective = problem.objective()
22 if <conditional_3>:
23 problem.notify_new_best_node(node=node,
24 current=True)
25 if <conditional_4>:
26 children = problem.branch()
27
28 #
29 # solve finalization
30 #
31 problem.load_state(root)
32 problem.notify_solve_finished(...)
Note that during the main solve loop (starting on line 13), it is safe to assume that the six highlighted problem methods between line 13 and line 25 will be called in the relative order shown. The conditions under which these methods will be called are briefly discussed below:
<conditional_1> (line 15): This condition is met when the best_node received from the dispatcher is not unbounded and improves upon the best node currently known to the worker process (i.e., has a better objective). By default, the check for objective improvement is exact, but it can be relaxed by assigning a nonzero value to the comparison_tolerance keyword of the
Solver.solve
method.<conditional_2> (line 20): This condition is met when the bound computed by the problem for the current node makes it eligible for the queue relative to the best objective known to the process. By default, this is true when the bound is better than the best objective by any nonzero amount, but this behavior can be influenced using the queue_tolerance keyword of the
Solver.solve
method.<conditional_3> (line 22): This condition is met when the objective computed by the problem for the current node is not unbounded and improves upon the objective of the best node currently known to the process. By default, the check for improvement is exact, but it can be relaxed by assigning a nonzero value to the comparison_tolerance keyword of the
Solver.solve
method.<conditional_4> (line 25): This condition is met when the objective computed by the problem for the current node is not unbounded, when <conditional_2> is still satisfied (based on a potentially new best objective), and when the difference between the node’s updated bound and objective satisfies the branching tolerance. By default, the branching tolerance is zero, meaning that any nonzero distance between these two values will satisfy this check, but this can be adjusted using the branching_tolerance keyword of the
Solver.solve
method.