pybnb.priority_queue

A collection of priority queue implementations that can be used by the dispatcher.

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

class pybnb.priority_queue.IPriorityQueue(*args, **kwds)[source]

Bases: object

The abstract interface for priority queues that store node data for the dispatcher.

size()[source]

Returns the size of the queue.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

get()[source]

Returns the next node in the queue. If the queue is empty, returns None.

bound()[source]

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)[source]

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

items()[source]

Iterates over the queued nodes in arbitrary order without modifying the queue.

class pybnb.priority_queue.WorstBoundFirstPriorityQueue(sense, track_bound)[source]

Bases: pybnb.priority_queue.IPriorityQueue

A priority queue implementation that serves nodes with the worst bound first.

Parameters
  • sense ({minimize, maximize}) – The objective sense for the problem.

  • track_bound (bool) – Indicates whether or not to track the global queue bound. Note that this particular queue implementation always tracks the global bound. This argument is ignored.

size()[source]

Returns the size of the queue.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

get()[source]

Returns the next node in the queue. If the queue is empty, returns None.

bound()[source]

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)[source]

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

items()[source]

Iterates over the queued nodes in arbitrary order without modifying the queue.

class pybnb.priority_queue.CustomPriorityQueue(sense, track_bound, _queue_type_=pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue[pybnb.node.Node])[source]

Bases: pybnb.priority_queue.IPriorityQueue

A priority queue implementation that can handle custom node priorities. It uses an additional data structure to reduce the amount of time it takes to compute a queue bound.

Parameters
  • sense ({minimize, maximize}) – The objective sense for the problem.

  • track_bound (bool) – Indicates whether or not to track the global queue bound.

size()[source]

Returns the size of the queue.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

get()[source]

Returns the next node in the queue. If the queue is empty, returns None.

bound()[source]

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)[source]

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

items()[source]

Iterates over the queued nodes in arbitrary order without modifying the queue.

class pybnb.priority_queue.BestObjectiveFirstPriorityQueue(sense, track_bound, _queue_type_=pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue[pybnb.node.Node])[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that serves nodes with the best objective first.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

class pybnb.priority_queue.BreadthFirstPriorityQueue(sense, track_bound, _queue_type_=pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue[pybnb.node.Node])[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that serves nodes in breadth-first order.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

class pybnb.priority_queue.DepthFirstPriorityQueue(sense, track_bound, _queue_type_=pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue[pybnb.node.Node])[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that serves nodes in depth-first order.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

class pybnb.priority_queue.FIFOQueue(sense, track_bound)[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that serves nodes in first-in, first-out order.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

class pybnb.priority_queue.LIFOQueue(sense, track_bound)[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that serves nodes in last-in, first-out order.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

class pybnb.priority_queue.RandomPriorityQueue(sense, track_bound, _queue_type_=pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue[pybnb.node.Node])[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that assigns a random priority to each incoming node.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

class pybnb.priority_queue.LocalGapPriorityQueue(sense, track_bound, _queue_type_=pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue[pybnb.node.Node])[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that serves nodes with the largest gap between the local objective and bound first.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

class pybnb.priority_queue.LexicographicPriorityQueue(queue_types, sense, track_bound)[source]

Bases: pybnb.priority_queue.CustomPriorityQueue

A priority queue implementation that serves nodes with the largest gap between the local objective and bound first.

sense{minimize, maximize}

The objective sense for the problem.

put(node)[source]

Puts an node in the queue, possibly updating the value of queue_priority, depending on the queue implementation. This method returns a unique counter associated with each put.

bound()

Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.

filter(func)

Removes nodes from the queue for which func(node) returns False. The list of nodes removed is returned. If the queue is empty or no nodes are removed, the returned list will be empty.

get()

Returns the next node in the queue. If the queue is empty, returns None.

items()

Iterates over the queued nodes in arbitrary order without modifying the queue.

size()

Returns the size of the queue.

pybnb.priority_queue.PriorityQueueFactory(name, *args, **kwds)[source]

Returns a new instance of the priority queue type registered under the given name.

pybnb.priority_queue.register_queue_type(name, cls)[source]

Registers a new priority queue class with the PriorityQueueFactory.