cuFlock

cuFlock is a high-performance parallel simplex solver designed to solve the Transportation Problem using NVIDIA CUDA. It provides various implementations, including parallel UV and Stepping Stone methods, and supports integration with Gurobi for comparison.

If you use this code for your research, please cite our paper: Paper Link

@article{MAHAJAN2024104790,
title = {GPU-accelerated transportation simplex algorithm},
journal = {Journal of Parallel and Distributed Computing},
volume = {184},
pages = {104790},
year = {2024},
issn = {0743-7315},
doi = {https://doi.org/10.1016/j.jpdc.2023.104790},
url = {https://www.sciencedirect.com/science/article/pii/S0743731523001600},
author = {Mohit Mahajan and Rakesh Nagi}
}

Prerequisites

To build and run cuFlock, you will need:

• CUDA Toolkit (tested with /usr/local/cuda)
• C++ Compiler (supporting C++14)
• OpenMP
• Gurobi Optimizer (optional, required only for Gurobi-based methods)

Build Instructions

The repository contains multiple Makefiles depending on your environment and whether you have Gurobi installed.

Build without Gurobi

Use this if you only want to use the GPU-based parallel algorithms:

make -f Makefile_without_gurobi

Build with Gurobi

Use this for Gurobi comparison methods. Ensure you update the GUROBI_HOME path in the Makefile if necessary:

make -f Makefile_with_gurobi

The default gurobi installation instructions are provided here

The build process will create the cuFlock executable inside the ./bin/ directory.

Execution

The cuFlock executable requires an input data file (-i) and an algorithm specification (-a).

Usage

./bin/cuFlock -i <data_file.dat> -a <algorithm>

Supported Algorithms (-a)

• parallel_uv: Parallel UV method on GPU.
• parallel_ss: Parallel Stepping Stone method on GPU.
• switch_hybrid: A hybrid switching method.
• cpu_lp_solve: Standard LP solve using Gurobi (requires building with Gurobi).

Data Inputs

Example problem instances are included in the data directory

Example

To run the Stepping Stone method on a specific dataset:

./bin/cuFlock -i ./data/uszip_TransportModel_100_100_1.dat -a parallel_ss

Batch Processing

Several scripts are provided for running batch tests:

• run_batch_ss.sh: Runs a batch of tests using the Stepping Stone method.
• run_batch_uv_parallel.sh: Runs a batch of tests using the UV method.
• run_batch_switch.sh: Runs tests using the hybrid switching method.

Irrelevant and Legacy Files

The following files and directories are considered legacy or irrelevant to the current direct usage of the repository and can be ignored or removed:

• archive/: Contains old implementations and scratch files.
• jobscript1.sh / jobscript2.sh: These are environment-specific SLURM scripts (Delta Cluster) and may need modification for other environments. Not useful for env's outside of UIUC network.
• vogel_batch.sh: Older test script.
• utilities/uszips.csv: Data utility file not directly used by the solver.