An implementation of Agrawal & Devanur's Online Stochastic Packing Algorithm, described in "Fast Algorithms for Online Stochastic Convex Programming".
Explore the docs »
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.
First, check that you have Python 3.9+:
python3 --version
Then, you can install the library with the following command:
pip install fast-online-packingfrom 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)
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
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 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
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.
Distributed under the MIT License. See LICENSE.txt for more information.
David Beyda - dbeyda@poli.ufrj.br
Project Link: https://github.com/dbeyda/fast-online-packing
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.