pybnb.solver

Branch-and-bound solver implementation.

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

class pybnb.solver.Solver(comm=<class 'pybnb.solver._NoArgumentGiven'>, dispatcher_rank=0)

A branch-and-bound solver.

Parameters

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

• dispatcher_rank (int, optional) – The process with this rank will be designated as the dispatcher process. If MPI functionality is disabled (by setting comm=None), this keyword must be 0. (default: 0)

property is_worker

Indicates if this process has been designated as a worker.

property is_dispatcher

Indicates if this process has been designated as the dispatcher.

property comm

The full MPI communicator that includes the dispatcher and all workers. Will be None if MPI functionality has been disabled.

property worker_comm

The worker MPI communicator. Will be None on any processes for which Solver.is_worker is False, or if MPI functionality has been disabled.

property worker_count

The number of worker processes associated with this solver.

collect_worker_statistics()

Collect individual worker statistics about the most recent solve.

Returns

A dictionary whose keys are the different statistics collected, where each entry is a list storing a value for each worker.

Return type

dict

save_dispatcher_queue()

Saves the dispatcher queue.

Returns

queue – If this process is the dispatcher, this method will return an object storing any nodes currently in the dispatcher queue. If this process is not the dispatcher, this method will return None. The returned object can be used to reinitialize a solve (e.g., with different algorithms settings) by assigning it to the initialize_queue keyword of the Solver.solve() method.

Return type

pybnb.dispatcher.DispatcherQueueData or None

solve(problem, best_objective=None, best_node=None, disable_objective_call=False, absolute_gap=0, relative_gap=None, scale_function=<function _default_scale>, queue_tolerance=<class 'pybnb.convergence_checker._auto_queue_tolerance'>, branch_tolerance=0, comparison_tolerance=0, objective_stop=None, bound_stop=None, node_limit=None, time_limit=None, queue_limit=None, track_bound=True, initialize_queue=None, queue_strategy='bound', log_interval_seconds=1.0, log_new_incumbent=True, log=<class 'pybnb.solver._NoArgumentGiven'>, disable_signal_handlers=False)

Solve a problem using branch-and-bound.

Note

Parameters for this function are treated differently depending on whether the process is a worker or dispatcher. For the serial case (no MPI), the single process is both a worker and a dispatcher. For the parallel case, exactly one process is a dispatcher and all other processes are workers. A (W) in the parameter description indicates that it is only used by worker processes (ignored otherwise). A (D) in the parameter description indicates that it is only used by the dispatcher process (ignored otherwise). An (A) indicates that it is used by all processes, and it is assumed the same value is provided for each process; otherwise, the behavior is undefined.

Parameters

• problem (pybnb.Problem) – An object defining a branch-and-bound problem.

• best_objective (float, optional) – Initializes the solve with an assumed best objective. Both this and the best_node option can be set to different values on all processes. The dispatcher will collect all values and use the best. Note that setting this option at, or too close to, the true optimal objective value may prevent the solver from collecting a node that stores the optimal user state information, so use this option with care. The recommended way to re-continue a solve from a known candidate solution is to assign the best_node attribute of a results object to the best_node solve option. Also note that the best node will be tracked separately from the given initial best objective until a node is found that improves upon the best objective. If this never happens, the best_node attribute on the solver results may be None or may have an objective that is worse than the objective attribute of the solver results. (default: None)

• best_node (Node, optional) – Initializes the solve with an assumed best node. This option can (and should) be used in place of the best_objective option when a best node from a previous solve has been collected. It can also be assigned a node object that was created manually by the user. The objective attribute is the only property of the node that will affect the solve. It must be set to a numeric value. (default: None)

• disable_objective_call (bool, optional) – (W) Disables requests for an objective value from subproblems. (default: False)

• absolute_gap (float, optional) – (A) The maximum absolute difference between the global bound and best objective for the problem to be considered solved to optimality. Setting to None will disable this optimality check. By default, this option also controls eligibility for the queue. See the “queue_tolerance” setting for more information. (default: 0)

• relative_gap (float, optional) – (A) The maximum relative difference (absolute difference scaled by max{1.0,|objective|}) between the global bound and best objective for the problem to be considered solved to optimality. The default setting of None means this optimality check is not used. (default: None)

• scale_function (function, optional) – (A) A function with signature f(bound, objective) -> float that returns a positive scale factor used to convert the absolute difference between the bound and objective into a relative difference. The relative difference is compared with the relative_gap convergence tolerance to determine if the solver should terminate. The default is equivalent to max{1.0,|objective|}. Other examples one could use are max{|bound|,|objective|}, (|bound|+|objective|)/2, etc.

• queue_tolerance (float, optional) – (A) The absolute tolerance used when deciding if a node is eligible to enter the queue. The difference between the node bound and the incumbent objective must be greater than this value. Leaving this argument at its default value indicates that this tolerance should be set equal to the “absolute_gap” setting. Setting this to zero means that nodes whose bound is equal to the incumbent objective are not eligible to enter the queue. Setting this to larger values can be used to limit the queue size, but it should be kept small enough to allow absolute and relative optimality tolerances to be met. This option can also be set to None to allow nodes with a bound equal to (but not greater than) the incumbent objective to enter the queue.

• branch_tolerance (float, optional) – (A) The absolute tolerance used when deciding if the computed objective and bound for a node are sufficiently different to branch into the node. The default value of zero means that branching will occur if the bound is not exactly equal to the objective. This option can be set to None to enable branching for nodes with a bound and objective that are exactly equal. (default: 0)

• comparison_tolerance (float, optional) – (A) The absolute tolerance used when deciding if two objective or bound values are sufficiently different to be considered improved or worsened. This tolerance controls when the solver considers a new incumbent objective to be found. It also controls when warnings are output about bounds becoming worse on child nodes. Setting this to larger values can be used to avoid the above solver actions due to insignificant numerical differences, but it is better to deal with these numerical issues by rounding numbers to a reliable precision before returning them from the problem methods. (default: 0)

• objective_stop (float, optional) – (A) If provided, the solve will terminate when a feasible objective is found that is at least as good as the specified value, and the termination_condition flag on the results object will be set to ‘objective_limit’. If this value is infinite, the solve will terminate as soon as a finite objective is found. (default: None)

• bound_stop (float, optional) – (A) If provided, the solve will terminate when the global bound on the objective is at least as good as the specified value, and the termination_condition flag on the results object will be set to ‘objective_limit’. If this value is infinite, the solve will terminate as soon as a finite bound is found. (default: None)

• node_limit (int, optional) – (D) If provided, the solve will begin to terminate once this many nodes have been served from the dispatcher queue, and the termination_condition flag on the results object will be set to ‘node_limit’. (default: None)

• time_limit (float, optional) – (D) If provided, the solve will begin to terminate once this amount of time has passed, and the termination_condition flag on the results object will be set to ‘time_limit’. Note that the solve may run for an arbitrarily longer amount of time, depending how long worker processes spend completing their final task. (default: None)

• queue_limit (int, optional) – (D) If provided, the solve will begin to terminate once the size of the dispatcher queue exceeds this amount, and the termination_condition flag on the results object will be set to ‘queue_limit’. Note that the queue may become arbitrarily larger than this limit, depending how many child nodes are returned from worker processes on their final update. (default: None)

• track_bound (bool, optional) – (D) Indicates whether the dispatcher should track the global queue bound while running. Setting this to false can reduce the overhead of dispatcher updates for some priority queue strategies. (default: True)

• initialize_queue (pybnb.dispatcher.DispatcherQueueData, optional) – (D) Initializes the dispatcher queue with that remaining from a previous solve (obtained by calling Solver.save_dispatcher_queue() after the solve). If left as None, the queue will be initialized with a single root node created by calling problem.save_state. (default: None)

• queue_strategy (QueueStrategy or tuple) – (D) Sets the strategy for prioritizing nodes in the central dispatcher queue. See the QueueStrategy enum for the list of acceptable values. This keyword can be assigned one of the enumeration attributes or an equivalent string name. This keyword can also be assigned a tuple of choices to define a lexicographic sorting strategy. (default: ‘bound’)

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

• log_new_incumbent (bool, optional) – (D) 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. (default: True)

• log (logging.Logger, optional) – (D) A log object where solver output should be sent. The default value causes all output to be streamed to the console. Setting to None disables all output.

• disable_signal_handlers (bool, optional) – (D) Setting to true disables the registering of signal handlers that allow gracefully terminating a solve early. (default: False)

Returns

results – An object storing information about the solve.

Return type

SolverResults

pybnb.solver.summarize_worker_statistics(stats, stream=<_io.TextIOWrapper name='<stdout>' mode='w' encoding='UTF-8'>)

Writes a summary of workers statistics to an output stream.

Parameters

• stats (dict) – A dictionary of worker statistics returned from a call to collect_worker_statistics().

• stream (file-like object, or string, optional) – A file-like object or a filename where results should be written to. (default: sys.stdout)

pybnb.solver.solve(problem, comm=<class 'pybnb.solver._NoArgumentGiven'>, dispatcher_rank=0, log_filename=None, results_filename=None, **kwds)

Solves a branch-and-bound problem and returns the solution.

Note

This function also collects and summarizes runtime workload statistics, which may introduce additional overhead. This overhead can be avoided by directly instantiating a Solver object and calling the Solver.solve() method.

Parameters

• problem (pybnb.Problem) – An object that defines a branch-and-bound problem

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

• dispatcher_rank (int, optional) – The process with this rank will be designated the dispatcher process. If MPI functionality is disabled (by setting comm=None, or when comm.size==1), this keyword must be left at 0. (default: 0)

• log_filename (string, optional) – A filename where solver output should be sent in addition to console. This keyword will be ignored if the log keyword is set. (default: None)

• results_filename (string, optional) – Saves the solver results into a YAML-formatted file with the given name. (default: None)

• **kwds – Additional keywords to be passed to Solver.solve(). See that method for additional keyword documentation.

Returns

results – An object storing information about the solve.

Return type

SolverResults