Getting Started with highs

The highs package provides an R interface to HiGHS, a high-performance solver for linear programming (LP), mixed-integer programming (MIP), and quadratic programming (QP) problems.

Linear Programming

Consider the LP:

\[ \max \; 2x_1 + 4x_2 + 3x_3 \] subject to \[ 3x_1 + 4x_2 + 2x_3 \le 60, \quad 2x_1 + x_2 + 2x_3 \le 40, \quad x_1 + 3x_2 + 2x_3 \le 80, \quad x_1, x_2, x_3 \ge 0. \]

library(highs)

L <- c(2, 4, 3)
A <- matrix(c(3, 4, 2,
              2, 1, 2,
              1, 3, 2), nrow = 3, byrow = TRUE)
rhs <- c(60, 40, 80)

sol <- highs_solve(L = L, lower = 0, A = A, rhs = rhs, maximum = TRUE)
sol$objective_value
#> [1] 76.66667
sol$primal_solution
#> [1]  0.000000  6.666667 16.666667

Mixed-Integer Programming

Adding integrality constraints makes this a MIP. Use the types argument with "I" for integer, "C" for continuous.

L <- c(3, 1, 3)
A <- rbind(c(-1,  2,  1),
           c( 0,  4, -3),
           c( 1, -3,  2))
rhs <- c(4, 2, 3)
lower <- c(-Inf, 0, 2)
upper <- c(4, 100, Inf)
types <- c("I", "C", "I")

sol <- highs_solve(L = L, lower = lower, upper = upper,
                   A = A, rhs = rhs, types = types, maximum = TRUE)
sol$objective_value
#> [1] 23.5
sol$primal_solution
#> [1] 4.0 2.5 3.0

Quadratic Programming

For QP problems, supply the Hessian matrix Q in the objective \(\frac{1}{2} x^T Q x + L^T x\):

Q <- matrix(c(8, 2, 2,
              2, 6, 0,
              2, 0, 4), nrow = 3)
L <- c(-14, -6, -12)

sol <- highs_solve(Q = Q, L = L, lower = 0)
sol$objective_value
#> [1] -23.69156
sol$primal_solution
#> [1] 1.0292208 0.4545455 2.4285714

Solver Options

Control solver behaviour with highs_control():

sol <- highs_solve(
  L = c(2, 4, 3), lower = 0,
  A = matrix(c(3, 4, 2, 2, 1, 2, 1, 3, 2), nrow = 3, byrow = TRUE),
  rhs = c(60, 40, 80), maximum = TRUE,
  control = highs_control(
    threads = 1L,
    time_limit = 60,
    log_to_console = FALSE
  )
)
sol$status_message
#> [1] "Optimal"

View all available options:

highs_available_solver_options()

Sparse Matrix Support

The A matrix can be any of the following formats:

Dense matrix
dgCMatrix or dgRMatrix from the Matrix package
matrix.csc or matrix.csr from the SparseM package
simple_triplet_matrix from the slam package

library(Matrix)
A_sparse <- Matrix(c(3, 4, 2, 2, 1, 2, 1, 3, 2),
                   nrow = 3, byrow = TRUE, sparse = TRUE)
sol <- highs_solve(L = c(2, 4, 3), lower = 0,
                   A = A_sparse, rhs = c(60, 40, 80), maximum = TRUE)
sol$objective_value
#> [1] 76.66667