| 1 |
;;; |
| 2 |
;;; math/simplex.scm - Simplex solver |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2023-2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
;; Linear program solver using Revised simplex method |
| 35 |
|
| 36 |
(define-module math.simplex |
| 37 |
(use gauche.array) |
| 38 |
(use gauche.sequence) |
| 39 |
(use gauche.uvector) |
| 40 |
(use srfi.42) |
| 41 |
(export simplex-solve) |
| 42 |
) |
| 43 |
(select-module math.simplex) |
| 44 |
|
| 45 |
(define-constant *debug-dump* #f) |
| 46 |
|
| 47 |
(define-macro (debug-dump . exprs) |
| 48 |
(if *debug-dump* |
| 49 |
`(begin ,@exprs) |
| 50 |
`(begin))) |
| 51 |
|
| 52 |
;; Input and output: |
| 53 |
;; A is an m x n array |
| 54 |
;; b is a uvector of length n (bounds) |
| 55 |
;; c is a uvector of length m (coefficients) |
| 56 |
;; Compute x, uvector of length n, that minimizes or maximizes |
| 57 |
;; Z = c^T . x under the constraint of Ax <= b, x_i >= 0. |
| 58 |
|
| 59 |
;; Returns uvector of length m for solution x, or #f if it's unsolvable. |
| 60 |
|
| 61 |
;; Terminology: |
| 62 |
;; IxB : u32vector of length n, indices of basic variables |
| 63 |
;; IxN : u32vector of length m, indices of non-basic variabls |
| 64 |
;; B^ : n x n matrix, inverse of basis matrix. |
| 65 |
;; p : f64vector of length n, RHS values. |
| 66 |
|
| 67 |
;; We first extend the matrix A by adding an nxn identity matrix on its right, |
| 68 |
;; and extend c accordingly. |
| 69 |
;; Hence initially, basis matrix is an nxn identity matrix. |
| 70 |
;; Suppose the given A as 3x4 matrix: |
| 71 |
;; |
| 72 |
;; a00 a01 a02 |
| 73 |
;; a10 a11 a12 |
| 74 |
;; a20 a21 a22 |
| 75 |
;; a30 a31 a32 |
| 76 |
;; |
| 77 |
;; and the given b as uvector: |
| 78 |
;; |
| 79 |
;; b0 b1 b2 b3 |
| 80 |
;; |
| 81 |
;; and the given c as uvector: |
| 82 |
;; |
| 83 |
;; c0 c1 c2 |
| 84 |
;; |
| 85 |
;; Then the initial tableau will be as follows: |
| 86 |
;; |
| 87 |
;; -c0 -c1 -c2 0 0 0 0 |
| 88 |
;; |
| 89 |
;; a00 a01 a02 1 0 0 0 b0 |
| 90 |
;; a10 a11 a12 0 1 0 0 b1 |
| 91 |
;; a20 a21 a22 0 0 1 0 b2 |
| 92 |
;; a30 a31 a32 0 0 0 1 b3 |
| 93 |
;; |
| 94 |
;; The initial IxB is [3 4 5 6], IxN is [0 1 2]. |
| 95 |
;; Basic feasible solution is [0 0 0 b0 b1 b2 b3] |
| 96 |
|
| 97 |
;; If any of elements in b is negative, we switch to two-phase simplex method. |
| 98 |
|
| 99 |
(define (simplex-solve A b goal c) |
| 100 |
(define maximize? |
| 101 |
(case goal |
| 102 |
[(:minimize) #f] |
| 103 |
[(:maximize) #t] |
| 104 |
[else (error "Goal must be either :minimize or :maximize, but got:" |
| 105 |
goal)])) |
| 106 |
(define-values (n m Na AA cc p B^ IxB IxN) (%canonicalize A b c)) |
| 107 |
(debug-dump |
| 108 |
(print "cc=" cc) |
| 109 |
(print "IxB=" IxB) |
| 110 |
(print "IxN=" IxN) |
| 111 |
(print "p=" p) |
| 112 |
(display "AA:") |
| 113 |
(pretty-print-array AA #t :readable? #f :left #\[ :right #\])) |
| 114 |
(if (zero? Na) |
| 115 |
(%solve-1-phase n m Na AA cc p B^ IxB IxN maximize?) |
| 116 |
(%solve-2-phase n m Na AA c cc p B^ IxB IxN maximize?))) |
| 117 |
|
| 118 |
(define (%solve-1-phase n m Na AA cc p B^ IxB IxN maximize?) |
| 119 |
(receive (AA p B^ IxB IxN) |
| 120 |
(%simplex-solve n m Na AA cc p B^ IxB IxN maximize?) |
| 121 |
(%result-variable-vector n m p IxB))) |
| 122 |
|
| 123 |
(define (%solve-2-phase n m Na AA c cc p B^ IxB IxN maximize?) |
| 124 |
(define AN (%project-columns AA IxN)) |
| 125 |
(receive (AA p B^ IxB IxN) |
| 126 |
(%simplex-solve n m Na AA cc p B^ IxB IxN #f) |
| 127 |
(debug-dump |
| 128 |
(print "\nPhase 1 solution:") |
| 129 |
(print "IxB=" IxB) |
| 130 |
(print "IxN=" IxN) |
| 131 |
(print "p=" p) |
| 132 |
(display "B^:") |
| 133 |
(pretty-print-array B^ #t :readable? #f :left #\[ :right #\])) |
| 134 |
(and (%phase2-feasible? p IxB n m) |
| 135 |
;; Constrct the second phase tableau. Non-basis columns |
| 136 |
;; are the negation of the corresponding column of B^ |
| 137 |
(let* ([cc (f64vector-append (f64vector-mul c -1) |
| 138 |
(make-f64vector n 0))] |
| 139 |
[IxN (%prepare-phase2-non-basis n m IxN)] |
| 140 |
[AA (%prepare-phase2-matrix n m AN B^ IxB IxN)] |
| 141 |
[B^ (identity-array n <f64array>)]) |
| 142 |
(debug-dump |
| 143 |
(print "\nPhase 2:") |
| 144 |
(print "cc=" cc) |
| 145 |
(print "IxB=" IxB) |
| 146 |
(print "IxN=" IxN) |
| 147 |
(print "p=" p) |
| 148 |
(display "AA:") |
| 149 |
(pretty-print-array AA #t :readable? #f :left #\[ :right #\])) |
| 150 |
(receive (AA p B^ IxB IxN) |
| 151 |
(%simplex-solve n m 0 AA cc p B^ IxB IxN maximize?) |
| 152 |
(%result-variable-vector n m p IxB)))))) |
| 153 |
|
| 154 |
;; Returns the following values: |
| 155 |
;; n, m - # of rows and columns of original problem |
| 156 |
;; Na - # of auxiliary variables. If this is >zero, we need 2-phase |
| 157 |
;; method. |
| 158 |
;; AA - n x (m + n + Na) Matrix extended with slack and artificial |
| 159 |
;; varaibles. |
| 160 |
;; cc - m + n + Na element vector of coefficient row. |
| 161 |
;; p - n element vector for RHS. All elements are posivitive. |
| 162 |
;; B^ - n x n matrix, the inverse of basis array. Initially it is |
| 163 |
;; an identity matrix. |
| 164 |
;; IxB - n element integer vector for basis indices |
| 165 |
;; IxN - m + Na element integer vector for non-basis indices |
| 166 |
(define (%canonicalize A b c) |
| 167 |
(define-values (n m) (array2d-size-check A b c)) |
| 168 |
(let1 Na (fold (^[e cnt] (if (negative? e) (+ cnt 1) cnt)) 0 b) |
| 169 |
(if (zero? Na) |
| 170 |
;; single-phase |
| 171 |
(let ([AA (array-concatenate A (identity-array n <f64array>) 1)] |
| 172 |
[cc (f64vector-append (if (f64vector? c) |
| 173 |
(f64vector-mul c -1) |
| 174 |
(map-to <f64vector> - c)) |
| 175 |
(make-f64vector n 0))] |
| 176 |
[p (coerce-to <f64vector> b)] |
| 177 |
[B^ (identity-array n <f64array>)] |
| 178 |
[IxB (list->u32vector (iota n m))] |
| 179 |
[IxN (list->u32vector (iota m))]) |
| 180 |
(values n m Na AA cc p B^ IxB IxN)) |
| 181 |
;; phase 1 for two-phase |
| 182 |
(let ([AA (make-f64array (shape 0 n 0 (+ m n Na)) 0)] |
| 183 |
[cc (make-f64vector (+ m n Na) 0)] |
| 184 |
[p (coerce-to <f64vector> b)] |
| 185 |
[B^ (identity-array n <f64array>)] |
| 186 |
[IxB (make-u32vector n)] |
| 187 |
[IxN (make-u32vector (+ m Na))]) |
| 188 |
(let loop-rows ([i 0] |
| 189 |
[cs m] ; slack var column |
| 190 |
[ca (+ m n)]) ; aux var column |
| 191 |
(when (< i n) |
| 192 |
(cond [(not (negative? (~ b i))) |
| 193 |
;; We copy original A row and add a slack var. |
| 194 |
;; The slack var consists one of the basis. |
| 195 |
(do-ec (: j m) |
| 196 |
(array-set! AA i j (array-ref A i j))) |
| 197 |
(array-set! AA i cs 1) |
| 198 |
(set! (~ p i) (~ b i)) |
| 199 |
(set! (~ IxB i) cs) |
| 200 |
(loop-rows (+ i 1) (+ cs 1) ca)] |
| 201 |
[else |
| 202 |
;; We negate the original A row, subtract a slack var, |
| 203 |
;; and add an aux var The aux var consists one of the basis. |
| 204 |
(do-ec (: j m) |
| 205 |
(array-set! AA i j (- (array-ref A i j)))) |
| 206 |
(array-set! AA i cs -1) |
| 207 |
(array-set! AA i ca 1) |
| 208 |
(set! (~ p i) (- (~ b i))) |
| 209 |
(set! (~ cc ca) -1) |
| 210 |
(set! (~ IxB i) ca) |
| 211 |
(loop-rows (+ i 1) (+ cs 1) (+ ca 1))]))) |
| 212 |
;; Fill IxN |
| 213 |
(let loop-cols ([j 0] [in 0]) |
| 214 |
(when (< j (+ m n Na)) |
| 215 |
(if (find (cut = <> j) IxB) |
| 216 |
(loop-cols (+ j 1) in) |
| 217 |
(begin |
| 218 |
(set! (~ IxN in) j) |
| 219 |
(loop-cols (+ j 1) (+ in 1)))))) |
| 220 |
(values n m Na AA cc p B^ IxB IxN))))) |
| 221 |
|
| 222 |
;; Returns solved AA, p, B^, IxB, IxN. |
| 223 |
(define (%simplex-solve n m Na AA cc p B^ IxB IxN maximize?) |
| 224 |
(define pp (make-f64vector n 0)) ;cc↑B . B^ |
| 225 |
|
| 226 |
(define pivot-selection-rule 'bland) |
| 227 |
|
| 228 |
(define (compute-multiplier-vector!) |
| 229 |
(dotimes [i n] |
| 230 |
(uvector-set! pp i |
| 231 |
(sum-ec (: j n) |
| 232 |
(* (uvector-ref cc (uvector-ref IxB j)) |
| 233 |
(array-ref B^ j i)))))) |
| 234 |
|
| 235 |
;; Returns i such that IxN[i] identifies the entering variable |
| 236 |
(define (find-entering-variable) |
| 237 |
(compute-multiplier-vector!) |
| 238 |
(debug-dump |
| 239 |
(display "B^:") |
| 240 |
(pretty-print-array B^ #t :readable? #f :left #\[ :right #\]) |
| 241 |
(format #t "pp = ~s\n" pp)) |
| 242 |
(let loop ([i 0] ;loop over IxN |
| 243 |
[picked-value #f] |
| 244 |
[picked-index #f]) |
| 245 |
(if (= i m) |
| 246 |
picked-index ;if #f, we're optimal |
| 247 |
(let* ([in (u32vector-ref IxN i)] |
| 248 |
[c_in (- (uvector-ref cc in) |
| 249 |
(sum-ec (: j n) |
| 250 |
(* (uvector-ref pp j) |
| 251 |
(array-ref AA j in))))]) |
| 252 |
(debug-dump |
| 253 |
(print "c_in[" (u32vector-ref IxN i) "] = " c_in)) |
| 254 |
(if (and ((if maximize? negative? positive?) c_in) |
| 255 |
(ecase pivot-selection-rule |
| 256 |
[(min-ratio) (if maximize? |
| 257 |
(< c_in picked-value) |
| 258 |
(> c_in picked-value))] |
| 259 |
[(bland) (or (not picked-index) |
| 260 |
(< in (u32vector-ref IxN picked-index)))])) |
| 261 |
(loop (+ i 1) c_in i) |
| 262 |
(loop (+ i 1) picked-value picked-index)))))) |
| 263 |
|
| 264 |
(define (find-leaving-row A_i x_k) |
| 265 |
(debug-dump |
| 266 |
(format #t "A_i = ~s\n" A_i) |
| 267 |
(format #t "x_k = ~s\n" x_k)) |
| 268 |
(let loop ([i 0] |
| 269 |
[min-ratio +inf.0] |
| 270 |
[min-row-index -1]) |
| 271 |
(cond [(= i n) |
| 272 |
(debug-dump |
| 273 |
(format #t "leaving row: ~s\n" min-row-index)) |
| 274 |
min-row-index] |
| 275 |
[(<= (f64vector-ref x_k i) 0) |
| 276 |
(loop (+ i 1) min-ratio min-row-index)] |
| 277 |
[else |
| 278 |
(let ([ratio (/ (f64vector-ref p i) (f64vector-ref x_k i))]) |
| 279 |
(debug-dump |
| 280 |
(format #t "ratio[~s] = ~s\n" i ratio)) |
| 281 |
(if (case pivot-selection-rule |
| 282 |
[(min-ratio) (< ratio min-ratio)] |
| 283 |
[(bland) (or (< ratio min-ratio) |
| 284 |
(and (= ratio min-ratio) |
| 285 |
(< (u32vector-ref IxB i) |
| 286 |
(u32vector-ref IxB min-row-index))))]) |
| 287 |
(loop (+ i 1) ratio i) |
| 288 |
(loop (+ i 1) min-ratio min-row-index)))]))) |
| 289 |
|
| 290 |
(define (pivot! entering leaving x_k) |
| 291 |
(let ([factor (/ (f64vector-ref p leaving) |
| 292 |
(f64vector-ref x_k leaving))]) |
| 293 |
;; Make x_k[leaving] 1, and adjust the same row of B^ |
| 294 |
(dotimes [j n] |
| 295 |
(array-set! B^ leaving j |
| 296 |
(/ (array-ref B^ leaving j) |
| 297 |
(f64vector-ref x_k leaving)))) |
| 298 |
(f64vector-set! p leaving factor) |
| 299 |
;; Make x_k[i] zero, and adjust the same row of B^ |
| 300 |
(dotimes [i n] |
| 301 |
(unless (= i leaving) |
| 302 |
(dotimes [j n] |
| 303 |
(array-set! B^ i j |
| 304 |
(- (array-ref B^ i j) |
| 305 |
(* (f64vector-ref x_k i) |
| 306 |
(array-ref B^ leaving j))))) |
| 307 |
(f64vector-set! p i |
| 308 |
(- (f64vector-ref p i) |
| 309 |
(* (f64vector-ref x_k i) factor))))) |
| 310 |
;; Swap pivotted index |
| 311 |
(rotate! (u32vector-ref IxB leaving) (u32vector-ref IxN entering)) |
| 312 |
)) |
| 313 |
|
| 314 |
(let loop ([entering (find-entering-variable)] |
| 315 |
[iter 0]) |
| 316 |
(when entering |
| 317 |
(debug-dump |
| 318 |
(format #t "entering var = ~s\n" (u32vector-ref IxN entering))) |
| 319 |
(let* ([A_i (map-to <f64vector> |
| 320 |
(^i (array-ref AA i (u32vector-ref IxN entering))) |
| 321 |
(iota n))] |
| 322 |
[x_k (array-vector-mul B^ A_i)] |
| 323 |
[leaving (find-leaving-row A_i x_k)]) |
| 324 |
|
| 325 |
(when (>= leaving 0) |
| 326 |
|
| 327 |
(pivot! entering leaving x_k) |
| 328 |
|
| 329 |
(debug-dump |
| 330 |
(print "pivot!") |
| 331 |
(format #t "p=~s\n" p) |
| 332 |
(print "IxB=" IxB) |
| 333 |
(print "IxN=" IxN)) |
| 334 |
|
| 335 |
(loop (find-entering-variable) (+ iter 1)) |
| 336 |
)))) |
| 337 |
|
| 338 |
;; Results |
| 339 |
(values AA p B^ IxB IxN)) |
| 340 |
|
| 341 |
;; Create a result vector of variables |
| 342 |
(define (%result-variable-vector n m p IxB) |
| 343 |
(rlet1 rvec (make-f64vector m 0) |
| 344 |
(dotimes [i n] |
| 345 |
(when (< (u32vector-ref IxB i) m) |
| 346 |
(f64vector-set! rvec (u32vector-ref IxB i) |
| 347 |
(f64vector-ref p i)))))) |
| 348 |
|
| 349 |
|
| 350 |
;; See the phase-1 result of two-phase method to see if there's a feasible |
| 351 |
;; answer. We add aux var at the end of the tableau. If all aux vars |
| 352 |
;; in the solution is 0, it is feasible. |
| 353 |
(define (%phase2-feasible? p IxB n m) |
| 354 |
(every?-ec (: col (index ib) IxB) |
| 355 |
(or (< col (+ n m)) |
| 356 |
(zero? (uvector-ref p ib))))) |
| 357 |
|
| 358 |
;; Returns a non-basis mapping vec that excludes aux vars. |
| 359 |
(define (%prepare-phase2-non-basis n m IxN) |
| 360 |
(list->u32vector |
| 361 |
(list-ec (: j IxN) |
| 362 |
(if (< j (+ n m))) |
| 363 |
j))) |
| 364 |
|
| 365 |
;; From array X, constract a subarray Y by picking rows listed in V. |
| 366 |
(define (%project-columns X V) |
| 367 |
(let ([rows (array-length X 0)] |
| 368 |
[cols (array-length X 1)] |
| 369 |
[new-cols (size-of V)]) |
| 370 |
(rlet1 Y (make-f64array (shape 0 rows 0 new-cols) 0) |
| 371 |
(do-ec (: c (index j) V) |
| 372 |
(: r rows) |
| 373 |
(array-set! Y r j (array-ref X r c)))))) |
| 374 |
|
| 375 |
;; Construct the subject matrix for phase 2. |
| 376 |
;; AN is the non-basis columns of original array. |
| 377 |
;; B^ and IxB are from the phase1 result. |
| 378 |
;; IxN is from the phase1 result, minus aux var columns. |
| 379 |
(define (%prepare-phase2-matrix n m AN B^ IxB IxN) |
| 380 |
(define AA* (array-concatenate (array-mul B^ AN) B^ 1)) |
| 381 |
(%project-columns AA* (iota (+ n m)))) |
| 382 |
|
| 383 |
;; returns m, n of 2d array, with argument check |
| 384 |
(define (array2d-size-check a b c) |
| 385 |
(assume (= (array-rank a) 2) |
| 386 |
"Rank 2 array is required, but got:" a) |
| 387 |
(assume (every (^i (zero? (array-start a i))) '(0 1)) |
| 388 |
"Array index must be 0-based, but got:" a) |
| 389 |
(let ([rows (array-length a 0)] |
| 390 |
[cols (array-length a 1)]) |
| 391 |
(assume (= cols (size-of c)) |
| 392 |
"Coefficient vector and matrix size don't match:" c) |
| 393 |
(assume (= rows (size-of b)) |
| 394 |
"Limit value vector and matrix size don't match:" b) |
| 395 |
(values rows cols))) |