Linear Program

Author

Anqi Fu and Balasubramanian Narasimhan

Introduction

A linear program is an optimization problem with a linear objective and affine inequality constraints. A common standard form is the following:

$\begin{array}{ll} minimize & c^{T} x \\ subject to & A x \leq b . \end{array}$

Here $A \in R^{m \times n}$ , $b \in R^{m}$ , and $c \in R^{n}$ are problem data and $x \in R^{n}$ is the optimization variable. The inequality constraint $A x \leq b$ is elementwise.

For example, we might have $n$ different products, each constructed out of $m$ components. Each entry $A_{i j}$ is the amount of component $i$ required to build one unit of product $j$ . Each entry $b_{i}$ is the total amount of component $i$ available. We lose $c_{j}$ for each unit of product $j$ ( $c_{j} < 0$ indicates profit). Our goal then is to choose how many units of each product $j$ to make, $x_{j}$ , in order to minimize loss without exceeding our budget for any component.

In addition to a solution $x^{⋆}$ , we obtain a dual solution $λ^{⋆}$ . A positive entry $λ_{i}^{⋆}$ indicates that the constraint $a_{i}^{T} x \leq b_{i}$ holds with equality for $x^{⋆}$ and suggests that changing $b_{i}$ would change the optimal value.

Example

In the following code, we solve a linear program with CVXR.

## Generate a random non-trivial linear program
set.seed(1)
m <- 15
n <- 10
s0 <- rnorm(m)
lamb0 <- pmax(-s0, 0)
s0 <- pmax(s0, 0)
x0 <- rnorm(n)
A <- matrix(rnorm(m * n), nrow = m, ncol = n)
b <- A %*% x0 + s0
c_vec <- -t(A) %*% lamb0

## Define and solve the CVXR problem
x <- Variable(n)
constraints <- list(A %*% x <= b)
prob <- Problem(Minimize(t(c_vec) %*% x), constraints)
result <- psolve(prob)
check_solver_status(prob)

## Print result
cat(sprintf("The optimal value is %f\n", result))
cat("A solution x is\n")
print(value(x))
cat("A dual solution is\n")
print(dual_value(constraints[[1]]))

The optimal value is -7.834460
A solution x is
            [,1]
 [1,]  0.3957534
 [2,]  0.2918129
 [3,]  0.8891856
 [4,]  1.0528054
 [5,]  0.3932769
 [6,]  1.1220355
 [7,]  0.8258565
 [8,]  0.6107771
 [9,] -2.2751922
[10,]  0.7058935
A dual solution is
 [1] 6.264538e-01 1.307119e-09 8.356286e-01 7.565120e-10 3.209152e-09
 [6] 8.204684e-01 1.333054e-09 9.338817e-10 1.516082e-09 3.053884e-01
[11] 1.549939e-09 2.621133e-09 6.212406e-01 2.214700e+00 1.797661e-09

Session Info

R version 4.5.2 (2025-10-31)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices datasets  utils     methods   base     

other attached packages:
[1] CVXR_1.8.0.9207

loaded via a namespace (and not attached):
 [1] slam_0.1-55       cli_3.6.5         knitr_1.51        ECOSolveR_0.6.1  
 [5] rlang_1.1.7       xfun_0.56         clarabel_0.11.2   otel_0.2.0       
 [9] gurobi_13.0-1     Rglpk_0.6-5.1     highs_1.12.0-3    cccp_0.3-3       
[13] scs_3.2.7         S7_0.2.1          jsonlite_2.0.0    backports_1.5.0  
[17] Rcplex_0.3-8      Rmosek_11.1.1     rprojroot_2.1.1   htmltools_0.5.9  
[21] gmp_0.7-5.1       piqp_0.6.2        rmarkdown_2.30    grid_4.5.2       
[25] evaluate_1.0.5    fastmap_1.2.0     yaml_2.3.12       compiler_4.5.2   
[29] codetools_0.2-20  htmlwidgets_1.6.4 Rcpp_1.1.1        here_1.0.2       
[33] osqp_1.0.0        lattice_0.22-9    digest_0.6.39     checkmate_2.3.4  
[37] Matrix_1.7-4      tools_4.5.2

Introduction

Example

Session Info

References