FirstOrderLp.jl

Introduction

This repository contains experimental code for solving linear and quadratic programming problems using first-order methods. It provides basic utilities and data structures for reading MPS files, rescaling, and implementing saddle-point methods. Specialized implementations are present for Mirror Prox and Primal-Dual Hybrid Gradient.

A C++ implementation of the PDLP algorithm is included in OR-Tools. We recommend the OR-Tools version of PDLP to all potential users. This repository is intended exclusively for supporting experiments and publications.

Related papers

The following papers describe the methods implemented in this repository and use FirstOrderLp for computational experiments:

• Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
• Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness
• Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming

One-time setup

Install Julia 1.6.0 or later. From the root directory of the repository, run:

$ julia --project=scripts -e 'import Pkg; Pkg.instantiate()'

This setup needs to be run again only if the dependencies change.

Running

Use one of the following two scripts to solve LP instances. All commands below assume that the current directory is the working directory.

solve_qp.jl

This is the recommended script for using FirstOrderLp. The results are written to JSON and text files; see the source for the description of the output formats.

To see the meaning of each argument:

$ julia --project=scripts scripts/solve_qp.jl --help

To solve a test instance with PDHG:

$ julia --project=scripts scripts/solve_qp.jl \
--instance_path test/trivial_lp_model.mps --iteration_limit 5000 \
--method pdhg --output_dir /tmp/first_order_lp_solve

solve_lp_external.jl

This script provides an interface similar to solve_qp but for calling external solvers for baselines. This script does not support quadratic objectives.

To solve a test instance with SCS's indirect mode:

$ julia --project=scripts scripts/solve_lp_external.jl \
--instance_path test/trivial_lp_model.mps --iteration_limit 5000 \
--solver scs-indirect --tolerance 1e-7 --output_dir /tmp/scs_solve

To solve a test with HiGHS's interior-point mode:

$ julia --project=scripts scripts/solve_lp_external.jl \
--instance_path test/trivial_lp_model.mps --solver highs-ipm \
--tolerance 1e-7 --output_dir /tmp/highs_solve

Loading the module

Use the following commands to load the FirstOrderLp module from Julia and to view the docstrings:

$ julia --project
…
julia> import FirstOrderLp
julia> ?  # Switch to the help> prompt.
help> FirstOrderLp.optimize
…
help> FirstOrderLp
…

Running the tests

To run the module’s tests run:

$ julia --color=yes --project -e 'import Pkg; Pkg.test("FirstOrderLp")'

Interpreting the output

When the verbosity option is greater than 2, a table of iteration stats will be printed with the following headings (split into six groups).

runtime

#iter = the current iteration number.

#kkt = the cumulative number of times the KKT matrix is multiplied.

seconds = the cumulative solve time in seconds.

residuals

pr norm = the euclidean norm of primal residuals (i.e., the constraint violation).

du norm = the euclidean norm of the dual residuals.

gap = the gap between the primal and dual objective.

solution information

pr obj = the primal objective value.

pr norm = the euclidean norm of the primal variable vector.

du norm = the euclidean norm of the dual variable vector.

relative residuals

rel pr = the euclidean norm of the primal residuals, relative to the right-hand-side.

rel dul = the euclidean norm of the dual residuals, relative to the primal linear objective.

rel gap = the relative optimality gap.

primal ray (verbosity greater than seven only)

pr norm = the euclidean norm of the primal residuals for the primal ray problem.

linear = the linear part of the primal ray objective.

qu norm = the norm of the quadratic part of the primal ray objective.

dual ray (verbosity greater than seven only)

du norm = the norm of the dual part of the dual ray.

dual obj = the dual ray objective value.

Auto-formatting Julia code

A one-time step is required to use the auto-formatter:

$ julia --project=formatter -e 'import Pkg; Pkg.instantiate()'

Run the following command to auto-format all Julia code in this directory before submitting changes:

$ julia --project=formatter -e 'using JuliaFormatter; format(".")'

Disclaimer

This is not an official Google product.