3.1 Linear program
The smallest interesting problem is a linear program: a linear objective over a polyhedron. We solve
maximize x₀ + x₁
subject to 0 ≤ x₀ ≤ 1, 0 ≤ x₁ ≤ 1
whose optimum is x = (1, 1). SCS minimizes, so we minimize −x₀ − x₁; the bounds become four positive-orthant inequalities (upper bounds x_i ≤ 1 and lower bounds written as −x_i ≤ 0).
(require scs)
Every example exports a run-example thunk so the test submodule and the scs documentation can drive it.
(provide run-example)
Standard form.
SCS solves Ax + s = b, s ∈ K. With K the positive orthant the slack s = b − Ax ≥ 0 encodes Ax ≤ b. Stacking the four bounds, the constraint matrix has one row per inequality:
(define A (scs:matrix 4 2 1 0 ; x0 <= 1 0 1 ; x1 <= 1 -1 0 ; -x0 <= 0, i.e. x0 >= 0 0 -1)) ; -x1 <= 0, i.e. x1 >= 0
The right-hand side carries the bounds, the objective c = (−1, −1) asks to maximize x₀ + x₁, and make-cone declares all four rows as positive-orthant inequalities. Tightening #:eps-abs/#:eps-rel sharpens the solution for the test’s tolerance.
(solve #:A A #:b #(1.0 1.0 0.0 0.0) #:c #(-1.0 -1.0) #:cone (make-cone #:positive 4) #:settings (make-settings #:eps-abs 1e-9 #:eps-rel 1e-9))
Running it.
run-example returns an scs-result; scs-result-x is the primal solution:
(scs-result-status (run-example)) ; "solved" (scs-result-x (run-example)) ; #(1.0 1.0)
The companion harness "test/01-linear-program.rkt" drives this and checks the optimum (run with raco test).