A parallel branch-and-bound engine for Python.

Overview

pybnb

PyPI-Status PyPI-Versions PyPI-Downloads

Testing-Status Coverage-Status Documentation-Status

Codacy-Grade Mypy Black

A parallel branch-and-bound engine for Python. (https://pybnb.readthedocs.io)

This software is copyright (c) by Gabriel A. Hackebeil ([email protected]).

This software is released under the MIT software license. This license, including disclaimer, is available in the 'LICENSE' file.

Quick Start

Define a problem:

# simple.py

import pybnb
class Simple(pybnb.Problem):
    def __init__(self):
        self.bounds = [0.0,1.0]
    def sense(self):
        return pybnb.minimize
    def objective(self):
        return round(self.bounds[1] - self.bounds[0], 3)
    def bound(self):
        return -(self.bounds[1] - self.bounds[0])**2
    def save_state(self, node):
        node.state = self.bounds
    def load_state(self, node):
        self.bounds = node.state
    def branch(self):
        L, U = self.bounds
        mid = 0.5 * (L + U)
        for l,u in [(L,mid), (mid,U)]:
            child = pybnb.Node()
            child.state = (l,u)
            yield child

Write a solve script:

# solve_simple.py

import simple
problem = simple.Simple()
results = pybnb.solve(problem,
                      absolute_gap=1e-9)

Run the script:

$ mpirun -np 4 python solve_simple.py

Using non-default solver options:
 - absolute_gap: 1e-09 (default: 0)

Starting branch & bound solve:
 - dispatcher pid: 34902 (Ozymandias.local)
 - worker processes: 3
---------------------------------------------------------------------------------------------------------------------------
         Nodes        |                      Objective Bounds                        |              Work
      Expl    Unexpl  |      Incumbent           Bound     Rel. Gap         Abs. Gap | Time (s)  Nodes/Sec Imbalance   Idle
         0         1  |            inf            -inf          inf%             inf |      0.0       0.00     0.00%      0
*        1         2  |              1              -1  200.0000000%               2 |      0.0    1226.99   300.00%      1
*        2         3  |            0.5              -1  150.0000000%             1.5 |      0.0    2966.04   150.00%      0
*        4         5  |           0.25           -0.25   50.0000000%             0.5 |      0.0    8081.95    75.00%      0
*        8         9  |          0.125         -0.0625   18.7500000%          0.1875 |      0.0   12566.90    37.50%      0
      Expl    Unexpl  |      Incumbent           Bound     Rel. Gap         Abs. Gap | Time (s)  Nodes/Sec Imbalance   Idle
*       16        17  |          0.062       -0.015625    7.7625000%        0.077625 |      0.0   15352.74    18.75%      0
*       32        33  |          0.031     -0.00390625    3.4906250%      0.03490625 |      0.0   15981.49    18.75%      0
*       64        65  |          0.016   -0.0009765625    1.6976563%    0.0169765625 |      0.0   18740.68    18.75%      0
*      128       129  |          0.008   -0.0002441406    0.8244141%  0.008244140625 |      0.0   21573.51    11.72%      0
*      256       257  |          0.004   -6.103516e-05    0.4061035%  0.004061035156 |      0.0   22166.96     8.20%      0
      Expl    Unexpl  |      Incumbent           Bound     Rel. Gap         Abs. Gap | Time (s)  Nodes/Sec Imbalance   Idle
*      512       513  |          0.002   -1.525879e-05    0.2015259%  0.002015258789 |      0.0   21177.00     5.86%      0
*     1024      1025  |          0.001   -3.814697e-06    0.1003815%  0.001003814697 |      0.1   19978.42     9.38%      0
*     2048      2049  |              0   -9.536743e-07    0.0000954% 9.536743164e-07 |      0.1   21606.45     5.42%      0
     24029     24030  |              0   -1.490116e-08    0.0000015% 1.490116119e-08 |      1.1   21961.03     5.98%      0
     46159     46160  |              0    -3.72529e-09    0.0000004% 3.725290298e-09 |      2.1   22120.75     5.73%      0
      Expl    Unexpl  |      Incumbent           Bound     Rel. Gap         Abs. Gap | Time (s)  Nodes/Sec Imbalance   Idle
     65537     65538  |              0   -9.313226e-10    0.0000001% 9.313225746e-10 |      3.0   22459.50     6.20%      0
---------------------------------------------------------------------------------------------------------------------------

Absolute optimality tolerance met
Optimal solution found!

solver results:
 - solution_status: optimal
 - termination_condition: optimality
 - objective: 0
 - bound: -9.313226e-10
 - absolute_gap: 9.313226e-10
 - relative_gap: 9.313226e-10
 - nodes: 65537
 - wall_time: 2.96 s
 - best_node: Node(objective=0)

Number of Workers:        3
Load Imbalance:       6.20%
 - min: 21355 (proc rank=3)
 - max: 22710 (proc rank=1)
Average Worker Timing:
 - queue:      80.78% [avg time: 109.6 us, count: 65537]
 - load_state:  0.44% [avg time: 596.1 ns, count: 65537]
 - bound:       0.59% [avg time: 796.1 ns, count: 65537]
 - objective:   3.52% [avg time:   4.7 us, count: 65537]
 - branch:      3.36% [avg time:   4.6 us, count: 65537]
 - other:      11.31% [avg time:  15.3 us, count: 65537]
Comments
  • Redesigning Node Serialization

    Redesigning Node Serialization

    This is a major rewrite of the serialization strategy for nodes.

    Improvements include:

    • much faster serial performance (especially with pypy)
    • removed numpy as a dependency
    • any pickle-able object can be assigned to node.state (no longer needs to be a numpy float array)
      • old way:
      def save_state(self, node):
          node.resize(2)
          node.state[:] = (self.lb, self.ub)
      def load_state(self, node):
          self.lb, self.ub = node.state[:]
      
      • new way:
      def save_state(self, node):
          node.state = (self.lb, self.ub)
      def load_state(self, node):
          self.lb, self.ub = node.state
      
    • lexicographic node priorities can now be used (fixes #4):
      • example: solver.solve(problem, queue_strategy=('bound','objective'))
    • added a config object to allow users to adjust serialization settings (e.g., use dill instead of pickle)
    opened by ghackebeil 6
  • Getting the answers & path out?

    Getting the answers & path out?

    Hey, cool library!

    Maybe I'm missing something here, but it doesn't seem like there's any way to get the answers or the path to the answers out? SolverResults doesn't have the best node and there's no bookeeping to keep the chain of nodes?

    opened by MisterTea 4
  • Access solver attributes within problem

    Access solver attributes within problem

    Hi ! Thank you for the development of this package ! I was wondering if there was a way to call the solver attributes inside the problem methods. For instance, I would like to have access to the best objective within the bound method in the following way :

    class Problem(pybnb.Problem):
        ...
        def bound(self):
            best_objective = self.retrieve_solver_attribute("best_objective")
            return do_bounding_using_best_objective()
        ...
    

    Thank you for your answer, Théo

    opened by TheoGuyard 2
  • Obtain optimal assignment

    Obtain optimal assignment

    Hi Gabriel

    Thanks for a great project!

    I am struggling to find a way to obtain the variables' assignments once I have solved the example knapsack problem and obtained an optimal solution. Somehow I cannot access the decision variables' values leading to the obtained optimal objective value.

    I am assuming there must be a way to obtain the values of each integer variables in the results object, but I cannot figure out how. I have gone through the documentation, but can't seem to find anything. Any help? :)

    opened by alexberndt 2
  • Option to disable queue bound tracking

    Option to disable queue bound tracking

    This PR adds a solver option, track_bound, that allows one to disable functionality that tracks the global queue bound until the solve terminates. This can significantly reduce the overhead for certain queue implementations (except for worst-bound first, which tracks the bound for free).

    opened by ghackebeil 1
  • [WIP] Drop Support for Python 2.x

    [WIP] Drop Support for Python 2.x

    This PR tracks changes that can be made when support for Python 2 is dropped at the end of 2019. So far, changes are almost entirely cosmetic:

    • drop enum34 and six dependency
    • replace class Name(object): with class Name:
    • drop 2 or 3 lines that dealt with bytes <-> str casting
    • use keyword-only arguments

    Type annotations are not included in this PR as they are not entirely supported in Python 3.5. In particular, x: <type> = <value> is only supported outside function declarations in Python 3.6+.

    opened by ghackebeil 1
  • Issue when bound() and objective() methods return numpy types (parallel only)

    Issue when bound() and objective() methods return numpy types (parallel only)

    If the objective/bound computation uses NumPy and happens to return, for instance, a numpy.float64 type, this creates issues when serializing these node attributes through marshal.dumps(...). When the dispatcher receives the node, the call to marshal.loads produces an object of type bytes rather than a number that can be used for computation.

    I think the best fix is to add some code on the worker side that appropriately casts the objective/bound value returned from the problem to an int or float built-in type (possibly do the same with the queue_priority attribute in case the user sets this).

    An alternative would be to use pickle to serialize these node attributes, but I believe this can be noticeable slower than marshal (double check this).

    bug 
    opened by ghackebeil 1
  • Knapsack example

    Knapsack example

    Can you include a knapsack implementation in your examples? I'm struggling a bit with the documentation. It would be helpful for newcomers to familiarize with your library.

    opened by ggaylord 1
  • Formalize nested solver implementation

    Formalize nested solver implementation

    Things to address:

    • [ ] Setting up the communicator tree and listeners could be made easier
    • [ ] Allow load balance and timing statistics to be sent up to the root solver
    TODO 
    opened by ghackebeil 1
  • Allow lexicographic node prioritization in the queue

    Allow lexicographic node prioritization in the queue

    This would require allowing a tuple to be assigned to Node.queue_priority rather than just a number. One could utilize this either by implementing a custom queue strategy, or by setting the queue_strategy option to a tuple of queue strategy names.

    TODO 
    opened by ghackebeil 0
  • Automatically save the best node

    Automatically save the best node

    It can currently be done by the user using optional Problem methods, but it should probably done by the solver.

    Possible implementation:

    • When a worker thinks it has a new best node, send it to the dispatcher on the next update.
    • The dispatcher sends the best node to workers on the final update (or possibly earlier with every update).
    • If load_solution=True (new solver options, default True), load_state will be called with this node rather than the root at the end of the solve. If load_solution=False, the node will be placed on the results object.
    TODO 
    opened by ghackebeil 0
  • Multihreading instead of multiprocessing

    Multihreading instead of multiprocessing

    Hi there, Will there ever be a multithreading support instead of the already implemented multiprocess version? This may be very useful if multiple nodes share a child, and the bound() function makes use of all parents infos.

    opened by DarioSimonato 1
Releases(0.6.2)
  • 0.6.2(Dec 10, 2019)

  • 0.6.1(Mar 30, 2019)

  • 0.6.0(Mar 12, 2019)

    This is a major release that changes default optimality and tolerance settings to make solver behavior more intuitive. It also includes a new option for reducing dispatcher overhead for non-default queue strategies.

    Source code(tar.gz)
    Source code(zip)
  • 0.5.2(Feb 13, 2019)

    This is a minor release that adds a configuration option to enable compression and fixes a serialization issues when the bound or objective Problem methods return NumPy scalar types.

    Source code(tar.gz)
    Source code(zip)
  • 0.5.1(Feb 11, 2019)

    This is a minor release that includes some improvements to the documentation as well as fixes for some edge case behavior for unbounded problems.

    Source code(tar.gz)
    Source code(zip)
  • 0.5.0(Feb 10, 2019)

    This is a major release that includes some backward incompatible changes. Major changes include:

    • automatically saving the best node (rather than just the best objective)
    • changing the signature of the branch method so that it has more clear semantics
    • removing / renaming some of the optional problem callbacks
    • adding built-in support for nested solver implementations
    Source code(tar.gz)
    Source code(zip)
  • 0.4.0(Jan 31, 2019)

  • 0.3.0(Jan 21, 2019)

    This is a major release that includes some backward incompatible changes. Major changes include

    • renaming of a few solver options
    • addition of options for early termination of a solve
    • new queue management strategies
    • improvements to the online documentation
    Source code(tar.gz)
    Source code(zip)
  • 0.2.9(Dec 3, 2018)

  • 0.2.8(Nov 26, 2018)

  • 0.2.7(Nov 26, 2018)

  • 0.2.6(Jul 13, 2018)

    This minor release includes changes that improve dispatcher performance. It also includes an additional queue strategy that prioritizes nodes with the best objective first.

    Source code(tar.gz)
    Source code(zip)
  • 0.2.5(May 30, 2018)

  • 0.2.4(May 26, 2018)

    This release fixes a bug in pyomo_tools that left uncollected messages on the communicator. See the CHANGELOG for additional details about this release.

    Source code(tar.gz)
    Source code(zip)
  • 0.2.3(May 22, 2018)

  • 0.2.2(May 22, 2018)

  • 0.2.0(May 22, 2018)

Owner
Gabriel Hackebeil
Gabriel Hackebeil
A normal phoneNumber tracker made with python.

A normal phoneNumber tracker made with python.

CLAYZANE 2 Dec 30, 2021
Reference management solution using Python and Notion.

notion-scholar Reference management solution using Python and Notion. The main idea of this app is to allow to furnish a Notion database using a BibTe

Thomas Hirtz 69 Dec 21, 2022
Always fill your package requirements without the user having to do anything! Simple and easy!

WSL Should now work always-fill-reqs-python3 Always fill your package requirements without the user having to do anything! Simple and easy! Supported

Hashm 7 Jan 19, 2022
An Insurance firm providing tour insurance is facing higher claim frequency

An Insurance firm providing tour insurance is facing higher claim frequency. Data is collected from the past few years. Made a model which predicts the claim status using CART, RF & ANN and compare t

1 Jan 27, 2022
This repo is a collection of programs and websites templates too

📢 Register here for Hacktoberfest and make four pull requests (PRs) between October 1st-31st to grab free SWAGS 🔥 . IMPORTANT While making pull requ

Binayak Jha - 2 7 Oct 03, 2022
The little-endian version of MessagePack

MessagePackEL This is the little-endian version of MessagePack, except the endianness is different, the rest is exactly the same as MessagePack. C lib

dukelec 9 May 13, 2022
A module to develop and apply old-style links

Old-Linkage-Dev (OLD) Old Linkage Development is a module to develop and apply old-style links. Old-style links stand for some traditional or conventi

Tarcadia 2 Dec 04, 2021
SimilarWeb for Team ACT v.0.0.1

SimilarWeb for Team ACT v.0.0.1 This module has been built to provide a better environment specifically for Similarweb in Team ACT. This module itself

Sunkyeong Lee 0 Dec 29, 2021
Create or join a private chatroom without any third-party middlemen in less than 30 seconds, available through an AES encrypted password protected link.

PY-CHAT Create or join a private chatroom without any third-party middlemen in less than 30 seconds, available through an AES encrypted password prote

1 Nov 24, 2021
Basic cryptography done in Python for study purposes

criptografia Criptografia básica feita em Python para fins de estudo Converte letras em numeros partindo do indice 0 e vice-versa A criptografia é fei

Carlos Eduardo 2 Dec 05, 2021
Collatz Sanısını Test Eden Ve Kanıtlayan Bir Python Programı

Collatz Sanısı Collatz Sanısını Test Eden Ve Kanıtlayan Bir Python Programı. Kullanım Terminalde: 1- git clone https://github.com/detherminal/Collatz-

Cemal Mert 2 May 07, 2022
This is a modified variation of abhiTronix's vidgear. In this variation, it is possible to write the output file anywhere regardless the permissions.

Info In order to download this package: Windows 10: Press Windows+S, Type PowerShell (cmd in older versions) and hit enter, Type pip install vidgear_n

Ege Akman 3 Jan 30, 2022
Unofficial Python implementation of the DNMF overlapping community detection algorithm

DNMF Unofficial Python implementation of the Discrete Non-negative Matrix Factorization (DNMF) overlapping community detection algorithm Paper Ye, Fan

Andrej Janchevski 3 Nov 30, 2021
Mines all the moneys and stuff and things.

NFT Miner NFT Miner - Version 1.1.0 - Quick Fix Since the whole NFT thing started booming on Twitter it's been hard not to see one of those ugly ass m

8w8 1 Dec 13, 2021
List of resources for learning Category Theory

A curated list of resources for studying category theory. As resources aimed at mathematicians are abundant, this list is aimed at materials whose target audience is not people with a graduate-level

Bruno Gavranović 100 Jan 01, 2023
Final project for ENGG 5402 Advanced Robotics in CUHK

Final project Final project Update Foundations Ubuntu virtual machine Ubuntu How to use Github to keep tracking the change of code version? Docker Set

Junjia Liu 8 Aug 01, 2022
A Regex based linter tool that works for any language and works exclusively with custom linting rules.

renag Documentation Available Here Short for Regex (re) Nag (like "one who complains"). Now also PEGs (Parsing Expression Grammars) compatible with py

Ryan Peach 12 Oct 20, 2022
Pykeeb - A small Python script that prints out currently connected keyboards

pykeeb 🐍 ⌨️ A small Python script that detects and prints out currently connect

Jordan Duabe 1 May 08, 2022
How to create the game Rock, Paper, Scissors in Python

Rock, Paper, Scissors! If you want to learn how to do interactive games using Python, then this is great start for you. In this code, You will learn h

SplendidSpidey 1 Dec 18, 2021
This is a batch script created to WEB-DL.

widevine-L3-WEB-DL-Script This is a batch script created to WEB-DL. Works well with .mpd files , for m3u8 please use n_m3u8 program (not included in t

Paranjay Singh 312 Dec 31, 2022