pybnb.dispatcher

Branch-and-bound dispatcher implementation.

Copyright by Gabriel A. Hackebeil (gabe.hackebeil@gmail.com).

class pybnb.dispatcher.DispatcherQueueData(nodes, worst_terminal_bound, sense)

A namedtuple storing data that can be used to initialize a dispatcher queue.

nodes

A list of Node objects.

Type

list

worst_terminal_bound

The worst bound of any node where branching did not continue.

Type

float or None

sense

The objective sense for the problem that produced this queue.

Type

{minimize, maximize}

bound()

Returns the global bound defined by this queue data.

class pybnb.dispatcher.StatusPrinter(dispatcher, log, log_interval_seconds=1.0)

Logs status information about the branch-and-bound solve.

Parameters

• dispatcher (pybnb.dispatcher.Dispatcher) – The central dispatcher that will be monitored.

• log (logging.Logger) – A log object where solver output should be sent.

• log_interval_seconds (float) – The approximate maximum time (in seconds) between solver log updates. More time may pass between log updates if no updates have been received from any workers, and less time may pass if a new incumbent is found. (default: 1.0)

log_info(msg)

Pass a message to log.info

log_warning(msg)

Pass a message to log.warning

log_debug(msg)

Pass a message to log.debug

log_error(msg)

Pass a message to log.error

log_critical(msg)

Pass a message to log.critical

new_objective(report=True)

Indicate that a new objective has been found

Parameters

report (bool, optional) – Indicate whether or not to force the next tic log output. (default: False)

tic(force=False)

Provide an opportunity to log output if certain criteria are met.

Parameters

force (bool, optional) – Indicate whether or not to force logging of output, even if logging criteria are not met. (default: False)

class pybnb.dispatcher.DispatcherBase

The base dispatcher implementation with some core functionality shared by the distributed and local implementations.

initialize(best_objective, best_node, initialize_queue, queue_strategy, converger, node_limit, time_limit, queue_limit, track_bound, log, log_interval_seconds, log_new_incumbent)

Initialize the dispatcher for a new solve.

Parameters

• best_objective (float) – The assumed best objective to start with.

• best_node (Node) – A node storing the assumed best objective.

• initialize_queue (pybnb.dispatcher.DispatcherQueueData) – The initial queue.

• queue_strategy (QueueStrategy) – Sets the strategy for prioritizing nodes in the central dispatcher queue. See the QueueStrategy enum for the list of acceptable values.

• converger (pybnb.convergence_checker.ConvergenceChecker) – The branch-and-bound convergence checker object.

• node_limit (int or None) – An integer representing the maximum number of nodes to processes before beginning to terminate the solve. If None, no node limit will be enforced.

• time_limit (float or None) – The maximum amount of time to spend processing nodes before beginning to terminate the solve. If None, no time limit will be enforced.

• queue_limit (int or None) – The maximum allowed queue size. If exceeded, the solve will terminate. If None, no size limit on the queue will be enforced.

• log (logging.Logger) – A log object where solver output should be sent.

• log_interval_seconds (float) – The approximate maximum time (in seconds) between solver log updates. More time may pass between log updates if no updates have been received from any workers, and less time may pass if a new incumbent is found.

• log_new_incumbent (bool) – Controls whether updates to the best objective are logged immediately (overriding the log interval). Setting this to false can be useful when frequent updates to the incumbent are expected and the additional logging slows down the dispatcher.

log_info(msg)

Pass a message to log.info

log_warning(msg)

Pass a message to log.warning

log_debug(msg)

Pass a message to log.debug

log_error(msg)

Pass a message to log.error

log_critical(msg)

Pass a message to log.critical

save_dispatcher_queue()

Saves the current dispatcher queue. The result can be used to re-initialize a solve.

Returns

queue_data – An object storing information that can be used to re-initialize the dispatcher queue to its current state.

Return type

pybnb.dispatcher.DispatcherQueueData

class pybnb.dispatcher.DispatcherLocal

The central dispatcher for a serial branch-and-bound algorithm.

initialize(best_objective, best_node, initialize_queue, queue_strategy, converger, node_limit, time_limit, queue_limit, track_bound, log, log_interval_seconds, log_new_incumbent)

Initialize the dispatcher. See the pybnb.dispatcher.DispatcherBase.initialize() method for argument descriptions.

update(best_objective, best_node, terminal_bound, solve_info, node_list)

Update local worker information.

Parameters

• best_objective (float or None) – A new potential best objective found by the worker.

• best_node (Node or None) – A new potential best node found by the worker.

• terminal_bound (float or None) – The worst bound of any terminal nodes that were processed by the worker since the last update.

• solve_info (_SolveInfo) – The most up-to-date worker solve information.

• node_list (list) – A list of nodes to add to the queue.

Returns

• solve_finished (bool) – Indicates if the dispatcher has terminated the solve.

• new_objective (float) – The best objective known to the dispatcher.

• best_node (Node or None) – The best node known to the dispatcher.

• data (Node or None) – If solve_finished is false, a new node for the worker to process. Otherwise, a tuple containing the global bound, the termination condition string, and the number of explored nodes.

class pybnb.dispatcher.DispatcherDistributed(comm)

The central dispatcher for a distributed branch-and-bound algorithm.

Parameters

comm (mpi4py.MPI.Comm, optional) – The MPI communicator to use. If set to None, this will disable the use of MPI and avoid an attempted import of mpi4py.MPI (which avoids triggering a call to MPI_Init()).

initialize(best_objective, best_node, initialize_queue, queue_strategy, converger, node_limit, time_limit, queue_limit, track_bound, log, log_interval_seconds, log_new_incumbent)

Initialize the dispatcher. See the pybnb.dispatcher.DispatcherBase.initialize() method for argument descriptions.

update(best_objective, best_node, terminal_bound, solve_info, node_list, source)

Update local worker information.

Parameters

• best_objective (float or None) – A new potential best objective found by the worker.

• best_node (Node or None) – A new potential best node found by the worker.

• terminal_bound (float or None) – The worst bound of any terminal nodes that were processed by the worker since the last update.

• solve_info (_SolveInfo) – The most up-to-date worker solve information.

• node_list (list) – A list of nodes to add to the queue.

• source (int) – The worker process rank that the update came from.

Returns

• solve_finished (bool) – Indicates if the dispatcher has terminated the solve.

• new_objective (float) – The best objective value known to the dispatcher.

• best_node (Node or None) – The best node known to the dispatcher.

• data (array.array or None) – If solve_finished is false, a data array representing a new node for the worker to process. Otherwise, a tuple containing the global bound, the termination condition string, and the number of explored nodes.

serve()

Start listening for distributed branch-and-bound commands and map them to commands in the local dispatcher interface.

save_dispatcher_queue()

Saves the current dispatcher queue. The result can be used to re-initialize a solve.

Returns

queue_data – An object storing information that can be used to re-initialize the dispatcher queue to its current state.

Return type

pybnb.dispatcher.DispatcherQueueData