Packing using perturbed prediction
This page contains a program which implements the algorithm proposed in "Online Primal-Dual Algorithms with Predictions for
Packing Problems" by
Nguyễn Kim Thắng and Christoph Dürr.
Don't hesitate to contact us if you have some difficulties to use it.
Python source code
- adAuctions.py:
This file implements the online algorithm proposed in the above mentioned paper.
- gen_lognormal.py:
generates the problem instance, in form of a bipartite graph.
On one side you have 10000 items and on the other side you have 100 bidders.
For every item, 6 bidders are chosen at random, and edges created between them.
The weight of each edge is chosen according to a log normal distribution with mean 0.5 and standard deviation 0.5,
truncated to the interval [0,10].
The units of these values are Euros.
The budget of every bidder is a 1/10 fraction of all its offers, but ensured to be at least 10 Euros.
- main.py: This is the main program.
It receives as command line argument the prediction error \(\epsilon\).
First it computes the optimal fractional solution and the optimal integral solution,
using the generic linear programming solver Gurobi.
Hence Gurobi and Pulp must be installed for the program to work properly.
In order to save running time, these solutions are written in a file called cache.txt, and read in subsequent calls.
As a result, if some parameter of the data set is changed, this cache file needs to be deleted manually before running the program.
The output of the program is written in two text files called ratio_\(\epsilon\).dat and violate_\(\epsilon\).dat.
The content of these files can be plotted using TikZ in LaTeX.
- plot_tikz.tex: A sample LaTeX file to visualize the plots produced by the main program above.