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
[source]¶ Bases:
object
The abstract interface for priority queues that store node data for the dispatcher.
-
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
()[source]¶ Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.
-
-
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: -
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
()[source]¶ Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.
-
-
class
pybnb.priority_queue.
CustomPriorityQueue
(sense, track_bound, _queue_type_=<class 'pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue'>)[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: -
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
()[source]¶ Returns the weakest bound of all nodes in the queue. If the queue is empty, returns None.
-
-
class
pybnb.priority_queue.
BestObjectiveFirstPriorityQueue
(sense, track_bound, _queue_type_=<class 'pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue'>)[source]¶ Bases:
pybnb.priority_queue.CustomPriorityQueue
A priority queue implementation that serves nodes with the best objective first.
-
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_=<class 'pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue'>)[source]¶ Bases:
pybnb.priority_queue.CustomPriorityQueue
A priority queue implementation that serves nodes in breadth-first order.
-
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_=<class 'pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue'>)[source]¶ Bases:
pybnb.priority_queue.CustomPriorityQueue
A priority queue implementation that serves nodes in depth-first order.
-
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.
-
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.
-
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_=<class 'pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue'>)[source]¶ Bases:
pybnb.priority_queue.CustomPriorityQueue
A priority queue implementation that assigns a random priority to each incoming node.
-
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_=<class 'pybnb.priority_queue._NoThreadingMaxPriorityFirstQueue'>)[source]¶ Bases:
pybnb.priority_queue.CustomPriorityQueue
A priority queue implementation that serves nodes with the largest gap between the local objective and bound first.
-
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.
-
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.
-