fast-online-packing 0.0.1

A fast algorithm for online packing.

Fast Online Packing

An implementation of Agrawal & Devanur's Online Stochastic Packing Algorithm, described in "Fast Algorithms for Online Stochastic Convex Programming".
Explore the docs »

About The Project

This is an implementation of the Online Packing algorithm presented by Agrawal & Devanur on "Fast Algorithms for Online Stochastic Convex Programming" (Algorithm 6.1), published in SODA'15. This algorithm tries to solve the Online Packing problem in the random-order model. You can learn more about it in the docs.

This project aims to provide a clear understanding of the algorithm, enlighten possible implementation dificulties and be used in fast prototyping scenarios. It was not designed for runtime performance nor for use in production environments.

In addition, this library provides a Packing Problem module that describes and enforces the Online Packing problem. This module can be used independently to assist the development of other algorithms for this same problem.

External Usage Dependencies

• Python-MIP
• Google ORTools

Installation

First, check that you have Python 3.9+:

python3 --version

Then, you can install the library with the following command:

pip install fast-online-packing

Usage

from fast_online_packing import instance_generator as generator
from fast_online_packing.online_solver import OnlineSolver

n_instants = 400
cost_dim = 5

delta = 0.3
values, costs, cap, e = generator.generate_valid_instance(
    delta, n_instants, cost_dim, items_per_instant=3)

# instantiate the solver
s = OnlineSolver(cost_dim, n_instants, cap, e, PythonMIPSolver)

for v, c in zip(values, costs):
    # ask the solver which item should we pack
    chosen_idx = s.pack_one(v, c)
    
    if chosen_idx == -1:
      print("No item chosen this round.")
    else:
      print("Algorithm picked item with index ", chosen_idx)
      item_value = v[chosen_idx]
      item_cost_vector = c[chosen_idx]

For more examples, please refer to the Documentation

Further Development / Contributing

Clone the repo somewhere inside your project:

git clone https://github.com/dbeyda/fast-online-packing

Install development dependencies:

pip install -r fast-online-learning/requirements.txt

Install the cloned repo using the --editable option:

pip install -e <path/to/fast-online-packing>

Develop, develop, develop. When you're finished, make to update and run the tests, and update and generate new docs.

Tests

Tests were developed using PyTest. There is one test for each module, all located under the tests/ folder.

To run all tests, use the following command:

pytest .

If you want to output the test log to a file, you can do:

pytest . > testlog.txt

Generating New Documentation

Documentation is provided in the HTML format and was generated with Sphinx. API reference was generated automatically with autodoc from docstrings. Documentation source files are found in the docs_src folder, and generated HTML docs are in the docs/ folder. This arrangement facilitates deploying the docs to GitHub Pages.

To generate new documentation:

cd docs_src
make github

Sphinx will read the .rst files in docs_src/ to generate new HTML files in the docs/ folder.

---

License

Distributed under the MIT License. See LICENSE.txt for more information.

Contact

David Beyda - [e-mail]

Project Link: https://github.com/dbeyda/fast-online-packing

Disclaimer

This package was implemented as the Final Programming Assignment of my Msc. in PUC-Rio. It was developed only by me. This project is an independent work. It is not the original / official implementation of Agrawal & Devanur's paper.