cuPDLP-C

cuPDLP is now available in COPT 7.1!

Code for solving LP on GPU using the first-order algorithm -- PDLP.

This is the C implementation of the Julia version cuPDLP.jl.

Compile

We use CMAKE to build CUPDLP. The current version switches to HiGHS project (previously, Coin-OR CLP).

Please compile with HiGHS 1.6.0 and CUDA 12.3.

Note that if you install HiGHS using the precompiled binaries, the compressed MPS files cannot be read. You can build and install with the zlib support from source, see this page to find out more. Once you setup HiGHS and CUDA, set the following environment variables.

export HIGHS_HOME=/path-to-highs
export CUDA_HOME=/path-to-cuda

By setting -DBUILD_CUDA=ON (by default OFF, i.e., the CPU version), you have the GPU version of cuPDLP-C.

Examples

• use the debug mode:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Debug -DBUILD_CUDA=ON ..
cmake --build . --target plc

then you can find the binary plc in the folder <cuPDLP-C>/build/bin/.

• when using the release mode, we suggest the following options,

cmake -DBUILD_CUDA=ON \
-DCMAKE_C_FLAGS_RELEASE="-O2 -DNDEBUG" \
-DCMAKE_CXX_FLAGS_RELEASE="-O2 -DNDEBUG" \
-DCMAKE_CUDA_FLAGS_RELEASE="-O2 -DNDEBUG" ..

Alternative Interfaces

The Python Interface

If you wish to use the Python interface, use the following steps:

git submodule update --init --recursive

then build the target pycupdlp

cmake --build . --target pycupdlp 

(Optional) You may checkout the setup scripts under pycupdlp.

Usage

Usage example: set nIterLim to 5000 and solve.

./bin/plc -fname <mpsfile> -nIterLim 5000

For the helper: use -h.

./bin/plc -h

or

./bin/plc <something> -h <something>

The PDLP Algorithm

Consider the generic linear programming problem:

$$ \begin{aligned} \min\\ & c^\top x \\ \text{s.t.}\\ & A x = b \\ & Gx \geq h \\ & l \leq x \leq u \end{aligned} $$

Equivalently, we solve the following saddle-point problem,

$$ \max_{y_1,\text{free}, y_2\geq 0}\min_{l\leq x\leq u}c^\top x - y^\top Kx + q^\top y $$

where dual variables $y^\top=(y_1^\top, y_2^\top)$, $K^\top = (A^\top, G^\top)$, $q^\top=(b^\top, h^\top)$.

Primal-Dual Hybrid Gradient (PDHG) algorithm takes the step as follows,

$$ \begin{aligned} x^{k+1} &= \Pi_{l\leq x\leq u} (x^k - \tau (c - K^\top y^k)) \\ y^{k+1} &= \Pi_{y_2\geq 0} (y^k + \sigma (q - K(2x^{k+1} - x^k))) \end{aligned} $$

The termination criteria contain the primal feasibility, dual feasibility, and duality gap.

$$ \begin{aligned} \left\\| \begin{matrix} Ax-b \\\\ (h - Gx)^+ \end{matrix} \right\\| &\leq \epsilon (1 + \\|q\\|) \\ \\|c - K^\top y - \lambda\\|&\leq \epsilon(1 + \\|c\\|) \\ |q^\top y + l^\top \lambda^+ - u^\top \lambda^- - c^\top x| &\leq \epsilon(1 + |c^\top x| + |q^\top y + l^\top \lambda^+ - u^\top \lambda^-|) \end{aligned} $$

where $\lambda = \Pi_\Lambda(c - K^\top y)$

$$ \lambda_i \begin{cases} = 0 & l_i=-\infty, u_i=+\infty\\ \leq 0 & l_i=-\infty, u_i<+\infty\\ \geq 0 & l_i<-\infty, u_i=+\infty\\ \text{free} & l_i>-\infty, u_i<+\infty \end{cases}.$$

$\\|\cdot\\|$ is 2-norm, and $|\cdot|$ is absolute value.

Authors

Dongdong Ge, Haodong Hu, Qi Huangfu, Jinsong Liu, Tianhao Liu, Haihao Lu, Jinwen Yang, Yinyu Ye, Chuwen Zhang

Contact

• Jinsong Liu <github.com/JinsongLiu6>
• Tianhao Liu <github.com/SkyLiu0>
• Chuwen Zhang <github.com/bzhangcw>