Randomized Maximization of Monotone DR-Submodular Functions on the Integer Lattice

For more details about this project, please refer to chapter 4 of my Master's Thesis.

Tech stack

• Python 3.8 or superior
• Hydra configuration framework

Initialize project

Install the virtual environment:

python3 -m venv ./venv

Activate the virtual environment:

source ./venv/bin/activate

Install third-party dependencies:

python3 -m pip install -r python/requirements.txt

How to run

This project is composed of 2 Python modules (one for each step of the application) that should be run in sequence. The output of the application is stored in the /out folder in a hierarchical fashion.

(1) Benchmark Step: python.benchmark

• Compute the ground truth density map (which associates each subset to the probability of being sampled from the ground truth distribution) only once
• Run the specified samplers over the target probabilistic submodular models, saving the history of the samples obtained in CSV

python3 -u -m python.benchmark -m \
  obj=demo_monotone,demo_monotone_skewed \
  runtime=laptop \
  algo=SSG,SGL-III-b,SGL-III-c,Soma-DR-I

(2) Plot generation Step: python.plotter

• Plot the cumulative probability distance between each sampler's outcome and the ground truth distribution

python3 -u -m python.plotter

Different types of benchmark experiments:

Run experiments on the Synthetic DR-Monotone Submodular Function

python3 -u -m python.benchmark -m obj=demo_monotone \
  runtime=laptop \
  algo=SSG,SGL-I,SGL-II,SGL-III,Soma-II,Soma-DR-I

Run experiments on the Budget Allocation Problem

python3 -u -m python.benchmark -m obj=budget_allocation \
  runtime=laptop \
  algo=SSG,SGL-I,SGL-II,SGL-III,Soma-II,Soma-DR-I

Run experiments on the Facility Location Problem

python3 -u -m python.benchmark -m obj=facility_location \
  runtime=laptop \
  algo=SSG,SGL-I,SGL-II,SGL-III,Soma-II,Soma-DR-I

Run experiments on the Synthetic Non-Monotone Submodular Function

python3 -u -m python.benchmark -m obj=demo_non_monotone \
  runtime=laptop \
  algo=SSG,SGL-I,SGL-II,SGL-II-b,Soma-II

To see the results of the experiments

The experiment results are stored in the out/ folder.

Notice

We plan on releasing this code under the MIT license, if and when accepted.