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
Простенький ботик для троллинга с интерфейсом #Yakima_Visus

Bot-Trolling-Vk Простенький ботик для троллинга с интерфейсом #Yakima_Visus Установка pip install vk_api pip install requests если там еще чото будет

Yakima Visus 4 Oct 11, 2022
A totally unrealistic cell growth/reproduction simulation.

A totally unrealistic cell growth/reproduction simulation.

Andrien Wiandyano 1 Oct 24, 2021
A hackers attempt at an MVP anki plugin

my anki plugin if you have found this by accident, you should probably run away this is nothing more than a hackers attempt at an MVP anki plugin I re

Chris Hall 1 Nov 02, 2021
A script to automatically update bot status at GitHub as well as in Telegram channel.

A simple & short repository to show your bot's status in your GitHub README.md file as well as in you channel.

Jainam Oswal 55 Dec 13, 2022
A tool to quickly create codeforces contest directories with templates.

Codeforces Template Tool I created this tool to help me quickly set up codeforces contests/singular problems with templates. Tested for windows, shoul

1 Jun 02, 2022
Table (Finnish Taulukko) glued together to transform into hands-free living.

taulukko Table (Finnish Taulukko) glued together to transform into hands-free living. Installation Preferred way to install is as usual (for testing o

Stefan Hagen 2 Dec 14, 2022
Combines power of torch, numerical methods to conquer and solve ALL {O,P}DEs

torch_DE_solver Combines power of torch, numerical methods and math overall to conquer and solve ALL {O,P}DEs There are three examples to provide a li

Natural Systems Simulation Lab 28 Dec 12, 2022
Swubcase - The shitty programming language

What is Swubcase? Swubcase is easy-to-use programming language that can fuck you

5 Jun 19, 2022
Script de monitoramento de telemetria para missões espaciais, cansat e foguetemodelismo.

Aeroespace_GroundStation Script de monitoramento de telemetria para missões espaciais, cansat e foguetemodelismo. Imagem 1 - Dashboard realizando moni

Vinícius Azevedo 5 Nov 27, 2022
Procedural 3D data generation pipeline for architecture

Synthetic Dataset Generator Authors: Stanislava Fedorova Alberto Tono Meher Shashwat Nigam Jiayao Zhang Amirhossein Ahmadnia Cecilia bolognesi Dominik

Computational Design Institute 49 Nov 25, 2022
Konomi: Kind and Optimized Next brOadcast watching systeM Infrastructure

Konomi 備考・注意事項 現在 α 版で、まだ実験的なプロダクトです。通常利用には耐えないでしょうし、サポートもできません。 安定しているとは到底言いがたい品質ですが、それでも構わない方のみ導入してください。 使い方などの説明も用意できていないため、自力でトラブルに対処できるエンジニアの方以外に

tsukumi 243 Dec 30, 2022
MiniJVM is simple java virtual machine written by python language, it can load class file from file system and run it.

MiniJVM MiniJVM是一款使用python编写的简易JVM,能够从本地加载class文件并且执行绝大多数指令。 支持的功能 1.从本地磁盘加载class并解析 2.支持绝大多数指令集的执行 3.支持虚拟机内存分区以及对象的创建 4.支持方法的调用和参数传递 5.支持静态代码块的初始化 不支

keguoyu 60 Apr 01, 2022
This repository contains Python Projects for Beginners as well as for Intermediate Developers built by Contributors.

Python Projects {Open Source} Introduction The repository was built with a tree-like structure in mind, it contains collections of Python Projects. Mo

Gaurav Pandey 115 Apr 30, 2022
In this project, we'll be creating a virtual personal assistant for ourselves using our favorite programming language

In this project, we'll be creating a virtual personal assistant for ourselves using our favorite programming language, Python. We can perform several offline as well as online operations using the bo

Ashutosh Krishna 188 Jan 03, 2023
YourX: URL Clusterer With Python

YourX | URL Clusterer Screenshots Instructions for running Install requirements

ARPSyndicate 1 Mar 11, 2022
The LiberaPay archive module for the SeanPM life archive project.

By: Top README.md Read this article in a different language Sorted by: A-Z Sorting options unavailable ( af Afrikaans Afrikaans | sq Shqiptare Albania

Sean P. Myrick V19.1.7.2 1 Aug 26, 2022
Dotfiles for my configurations!

Dotfiles Repo Welcome! Over here, you can find my dotfiles for various applications, including QTile, Alacritty, Kitty, LunarVim, and more! Make sure

class PythonAddict 3 Jan 10, 2022
Datamol is a python library to work with molecules.

Datamol is a python library to work with molecules. It's a layer built on top of RDKit and aims to be as light as possible.

datamol 276 Dec 19, 2022
A streamlit app for exploring image search results from HuggingPics

title emoji colorFrom colorTo sdk app_file pinned huggingpics-explorer 🤗 blue red streamlit app.py false huggingpics-explorer A streamlit app for exp

Nathan Raw 4 Sep 10, 2022
Automated Birthday Wisher built using Python

Automated Birthday Wisher This Automation of wishing Birthday is achieved using Python. Never forget to wish birthday! Table of contents Overview Scre

yashviradia 1 Nov 29, 2021