Debian Codegraph @

lib/math/simplex.scm

raw
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)))