HPR-LP-MATLAB: A MATLAB Solver for Linear Programming

A MATLAB implementation of the Halpern Peaceman-Rachford (HPR) method for solving linear programming (LP) problems on CPUs.

---

LP Problem Formulation

$$ \begin{array}{ll} \underset{x \in \mathbb{R}^n}{\min} \quad & \langle c, x \rangle \\ \text{s.t.} \quad & L \leq A x \leq U, \\ & l \leq x \leq u . \end{array} $$

---

Getting Started

Prerequisites

Before using HPR-LP, make sure the following dependencies are installed:

• MATLAB (Recommended version: R2020a or later)
• C++ Compiler (Required for MEX compilation; e.g., GCC on Linux/macOS, MSVC on Windows)

To set up the HPR-LP environment, run the setup script in MATLAB:

cd /path/to/HPR-LP/matlab
setup_hprlp  % Compiles MEX reader and configures paths

---

Usage 1: Test Instances in MPS Format

Setting Data and Result Paths

Before running the scripts, please modify run_single_file.m or run_dataset.m in the scripts directory to specify the data path and result path according to your setup.

Running a Single Instance

To test the script on a single instance (.mps file):

% Set parameters (optional)
params = HPRLPParameters();
params.stoptol = 1e-4;
params.time_limit = 3600;

% Solve from MPS file
results = runFile('your_problem.mps', params);

% Check results
fprintf('Status: %s\n', results.output_type);
fprintf('Objective: %.6e\n', results.primal_obj);

Running All Instances in a Directory

To process all .mps files in a directory:

% Configure parameters
params = HPRLPParameters();
params.stoptol = 1e-4;
params.time_limit = 600;

% Run on all files in the directory
runDataset('/path/to/mps/files', '/path/to/results', params);

---

Usage 2: Define Your LP Model in MATLAB Scripts

Example 1: Define an LP Instance Directly in MATLAB

This example demonstrates how to construct and solve a linear programming problem directly in MATLAB without relying on MPS files.

run('demo/demo_Abc.m')

The script demonstrates:

• Direct matrix-based LP formulation
• Setting up the problem: min c'*x subject to AL ≤ A*x ≤ AU, l ≤ x ≤ u
• Solving with HPR-LP
• Accessing solution values

Example problem from the demo:

% Define LP: min -3*x1 - 5*x2
%     s.t. -x1 - 2*x2 >= -10
%          -3*x1 - x2 >= -12
%          x1 >= 0, x2 >= 0

A = sparse([-1 -2; -3 -1]);
AL = [-10; -12];
AU = [Inf; Inf];
c = [-3; -5];
l = [0; 0];
u = [Inf; Inf];
obj_constant = 0.0;

params = HPRLPParameters();
params.stoptol = 1e-4;

result = runAbc(A, c, AL, AU, l, u, obj_constant, params);

fprintf('Objective value: %.10f\n', result.primal_obj);
fprintf('x1 = %.10f\n', full(result.x(1)));
fprintf('x2 = %.10f\n', full(result.x(2)));

---

Parameters

Below is a list of the parameters in HPR-LP along with their default values and usage:

Parameter	Default Value	Description
time_limit	3600	Maximum allowed runtime (seconds) for the algorithm.
stoptol	1e-4	Stopping tolerance for convergence checks.
max_iter	intmax	Maximum number of iterations allowed.
check_iter	150	Number of iterations to check residuals.
use_Ruiz_scaling	true	Whether to apply Ruiz scaling.
use_Pock_Chambolle_scaling	true	Whether to use the Pock-Chambolle scaling.
use_bc_scaling	true	Whether to use the scaling for b and c.
print_frequency	-1 (auto)	Print the log every print_frequency iterations.

---

Result Explanation

After solving an instance, you can access the result variables as shown below:

% Example from demo/demo_Abc.m
fprintf('Objective value: %.10f\n', result.primal_obj);
fprintf('x1 = %.10f\n', full(result.x(1)));
fprintf('x2 = %.10f\n', full(result.x(2)));

Category	Variable	Description
Iteration Counts	iter	Total number of iterations performed by the algorithm.
	iter_4	Number of iterations required to achieve an accuracy of 1e-4.
	iter_6	Number of iterations required to achieve an accuracy of 1e-6.
	iter_8	Number of iterations required to achieve an accuracy of 1e-8.
Time Metrics	time	Total time in seconds taken by the algorithm.
	time_4	Time in seconds taken to achieve an accuracy of 1e-4.
	time_6	Time in seconds taken to achieve an accuracy of 1e-6.
	time_8	Time in seconds taken to achieve an accuracy of 1e-8.
	power_time	Time in seconds used by the power method.
Objective Values	primal_obj	The primal objective value obtained.
	gap	The gap between the primal and dual objective values.
Residuals	residuals	Relative residuals of the primal feasibility, dual feasibility, and duality gap.
Algorithm Status	output_type	The final status of the algorithm: - OPTIMAL: Found optimal solution - MAX_ITER: Max iterations reached - TIME_LIMIT: Time limit reached
Solution Vectors	x	The final solution vector x.
	y	The final solution vector y.
	z	The final solution vector z.

---

Reference

Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, and Xinyuan Zhao, "HPR-LP: An implementation of an HPR method for solving linear programming", arXiv:2408.12179 (August 2024), Mathematical Programming Computation 17 (2025), doi.org/10.1007/s12532-025-00292-0.

---

Available HPR-LP Implementations

For the C implementation on GPUs, please visit the following repository:

https://github.com/PolyU-IOR/HPR-LP-C

For the Julia implementation on CPUs and GPUs, please visit the following repository:

https://github.com/PolyU-IOR/HPR-LP

For the Python implementation on GPUs, please visit the following repository:

https://github.com/PolyU-IOR/HPR-LP-Python

For the MATLAB implementation on CPUs, please visit the following repository:

https://github.com/PolyU-IOR/HPR-LP-MATLAB