# Efficient-GLP

This package contains an implementation of the Coordinate Linear Variance Reduction (CLVR) algorithm for Generalized Linear Programming (GLP) problems, and the support framework for conducting various numerical experiments. Please refer to our paper for details.


## Installing the Julia packages to run experiments

```
julia> import Pkg
julia> Pkg.add(["Arpack", "CSV", "Dates", "LinearAlgebra", "Logging", "SparseArrays"])
```


## A brief overview

The bulk of the code for running the experiments is located within `src`, and all implemented algorithms including CLVR are located under `src/algorithms`. We use Julia scripts to conduct our experiments and they are located within `scripts`.



## To reproduce our experiments

For reproducibility, we provide a script for running our experiments, located under `scripts/run_algos.jl`. The datasets for running the experiments are assumed to be located insider `./data`. To run an experiement:

```
julia scripts/run_algo.jl <dataset> <gamma> <algo1>...<algo4>
```

where `<gamma>` is a positive value to balance the primal and dual distances to a Nash equilibrium.


## A basic example


All problem instances must be wrapped into a problem instance before passing into algorithms. For example, in the case of standard form linear programs considerd in the paper where we want to 

$$
\max_{x \in \mathbb{R}^d} c^T x \quad \mathrm{s.t.} \quad A x = b, x \ge 0.
$$

Translating this problem instance into code, we have
```
include("./src/problems/standardLP.jl")

A_T = sparse([1 2; 3 4])  # Transpose of A is used due to Julia's Sparse CSC Matrix
b = Array{Float64}([1; 2])
c = Array{Float64}([-1; 1])

problem = StandardLinearProgram(A_T, b, c)
```

Next, we need to specify some exit criteria.

```
include("../src/algorithms/utils/exitcriterion.jl")

maxiter = 1e5
maxtime = 60
targetaccuracy = 1e-7
loggingfreq = 1
exitcriterion = ExitCriterion(maxiter, maxtime, targetaccuracy, loggingfreq)
```

Then to run the clvr algorithm with restart, we can simply set the algorithm parameters and run
```
# Common algo parameters
blocksize = 1
R = sqrt(blocksize)
γ = 0.1
restartfreq = Inf  # For restart when metric halves, set restartfreq=Inf 

run_results = clvr_lazy_restart_x_y(
    problem,
    exitcriterion;
    blocksize=blocksize,
    R=R * clvr_R_multiplier,
    γ=γ,
    restartfreq=restartfreq,
)
```
