source: project/release/3/glpk/trunk/glpk-eggdoc.scm @ 10875

Last change on this file since 10875 was 10875, checked in by Ivan Raikov, 12 years ago

Added an entry for release 1.1

File size: 20.4 KB
Line 
1
2(use eggdoc srfi-13)
3
4(define (s+ . rest) (string-concatenate (map ->string rest)))
5(define (sw+ w lst) (string-intersperse (map ->string lst) w))
6
7(define (make-lpx-parameter-doc name typ comment )
8  (if (list? typ)
9      (let ((variants (map cadr typ)))
10        `(procedure ,(s+ "lpx:" name ":: LPX [ * (" (sw+ " | " variants) ")] -> LPX | VALUE")
11                    ,comment))
12      `(procedure ,(s+ "lpx:" name ":: LPX [ * " (string-upcase (->string typ)) "] -> LPX | VALUE")
13                  ,comment)))
14
15         
16
17(define doc
18  `((eggdoc:begin
19     (name "glpk")
20     (description "GNU Linear Programming Kit (GLPK)")
21     (author (url "http://chicken.wiki.br/ivan raikov" "Ivan Raikov"))
22
23     (history 
24      (version "1.1" "Added chicken-glpk.h to file manifest")
25      (version "1.0" "Initial release"))
26
27     (requires)
28
29     (usage "(require-extension glpk)")
30
31     (download "glpk.egg")
32
33     (documentation
34     
35      (p (url "http://www.gnu.org/software/glpk/" "GLPK")
36         " is a package for solving linear programming and mixed integer programming problems. " )
37
38      (p "The Chicken GLPK egg provides a Scheme interface to "
39         "a large subset of the GLPK procedures for problem setup and solving.  "
40         "Below is a list of procedures that are included in this egg, "
41         "along with brief descriptions. This egg has been tested with "
42         "GLPK version 4.28. ")
43
44      (subsection "Problem constructors and predicates"
45
46          (procedure "lpx:empty-problem:: () -> LPX"
47                     (p "This procedure creates a new problem that has no rows or columns."))
48
49          (procedure "lpx:make-problem:: DIR * PBOUNDS * XBOUNDS * OBJCOEFS * CONSTRAINTS * [ORDER] -> LPX"
50                     ((p "This procedure creates a new problem with the specified parameters. ")
51                     (ul 
52                      (li "Argument " (tt "DIR") " specifies the optimization direction flag. It can be "
53                          "one of " (tt "'maximize") " or  " (tt "'minimize") ". ")
54                      (li "Argument " (tt "PBOUNDS") " is a list that specifies the type and bounds "
55                          "for each row of the problem object. Each element of this list can take one "
56                          "of the following forms: " 
57                          (symbol-table 
58                            (describe "'(unbounded)" 
59                                      ("Free (unbounded) variable, " (tt "-Inf <= x <= +Inf")))
60                            (describe "'(lower-bound LB)" 
61                                      ("Variable with lower bound, " (tt "LB <= x <= +Inf")))
62                            (describe "'(upper-bound UB)" 
63                                      ("Variable with upper bound, " (tt "-Inf <= x <= UB")))
64                            (describe "'(double-bounded LB UB)" 
65                                      ("Double-bounded variable, " (tt "LB <= x <= UB")))
66                            (describe "'(fixed LB UB)" 
67                                      ("Fixed variable, " (tt "LB = x = UB")))))
68                      (li "Argument " (tt "XBOUNDS") " is a list that specifies the type and bounds "
69                          "for each column (structural variable) of the problem object. "
70                          "Each element of this list can take one of the forms described for parameter "
71                          (tt "PBOUNDS") ". ")
72                      (li "Argument " (tt "OBJCOEFS") " is a list that specifies the objective coefficients "
73                          "for each column (structural variable). This list must be of the same length as "
74                          (tt "XBOUNDS") ". ")
75                      (li "Argument " (tt "OBJCOEFS") " is a list that specifies the objective coefficients "
76                          "for each column (structural variable). ")
77                      (li "Argument " (tt "CONSTRAINTS") " is an SRFI-4 " (tt "f64vector") " that represents "
78                          "the problem's constraint matrix (in row-major or column-major order). ")
79                      (li "Optional argument " (tt "ORDER") " specifies the element order of the constraints matrix. " 
80                          "It can be one of " (tt "'row-major") " or " (tt "'column-major") ". ")
81                      )))
82
83          (procedure "lpx?:: OBJECT -> BOOL"
84                     (p "Returns true if the given object was created by " (tt "lpx:empty-problem") " or "
85                        (tt "lpx:make-problem") ", false otherwise. " ))
86
87
88          )  ;; end subsection
89     
90
91      (subsection "Problem accessors and modifiers"
92                 
93                  (procedure "lpx:set-problem-name:: LPX * NAME -> LPX"
94                             "Sets problem name. ")
95                  (procedure "lpx:get-problem-name:: LPX -> NAME"
96                             "Returns the name of the given problem. ")
97                 
98                  (procedure "lpx:set-direction:: LPX * DIR -> LPX"
99                             ("Specifies the optimization direction flag, which can be "
100                              "one of " (tt "'maximize") " or  " (tt "'minimize") ". "))
101                  (procedure "lpx:get-direction:: LPX -> DIR"
102                             "Returns the optimization direction for the given problem. ")
103                 
104                  (procedure "lpx:set-class:: LPX * CLASS -> LPX"
105                             ("Sets problem class (linear programming or mixed-integer programming. "
106                              "Argument " (pp "CLASS") " can be one of " (tt "'lp") " or " (tt "'mip") ". "))
107
108                  (procedure "lpx:get-class:: LPX -> CLASS"
109                             "Returns the problem class. ")
110                 
111                  (procedure "lpx:add-rows:: LPX * N -> LPX"
112                             ("This procedure adds " (tt "N") " rows (constraints) to the given problem. "
113                              "Each new row is initially unbounded and has an empty list of constraint "
114                              "coefficients. "))
115
116                  (procedure "lpx:add-columns:: LPX * N -> LPX"
117                             ("This procedure adds " (tt "N") " columns (structural variables) to the given problem. "))
118                 
119                  (procedure "lpx:set-row-name:: LPX * I * NAME -> LPX"
120                             "Sets the name of row " (tt "I") ".")
121
122                  (procedure "lpx:set-column-name:: LPX * J * NAME -> LPX"
123                             "Sets the name of column " (tt "J") ".")
124
125                  (procedure "lpx:get-row-name:: LPX * I -> NAME"
126                             "Returns the name of row " (tt "I") ".")
127
128                  (procedure "lpx:get-column-name:: LPX * J -> NAME"
129                             "Returns the name of column " (tt "J") ".")
130
131                  (procedure "lpx:get-num-rows:: LPX -> N"
132                             "Returns the current number of rows in the given problem. ")
133
134                  (procedure "lpx:get-num-columns:: LPX -> N"
135                             "Returns the current number of columns in the given problem. ")
136
137                  (procedure "lpx:set-row-bounds:: LPX * I * BOUNDS -> LPX"
138                             ("Sets bounds for row " (tt "I") " in the given problem. "
139                              "Argument " (tt "BOUNDS") " specifies the type and bounds "
140                              "for the specified row. It can take one of the following forms: " 
141                              (symbol-table 
142                               (describe "'(unbounded)" 
143                                         ("Free (unbounded) variable, " (tt "-Inf <= x <= +Inf")))
144                               (describe "'(lower-bound LB)" 
145                                         ("Variable with lower bound, " (tt "LB <= x <= +Inf")))
146                               (describe "'(upper-bound UB)" 
147                                         ("Variable with upper bound, " (tt "-Inf <= x <= UB")))
148                               (describe "'(double-bounded LB UB)" 
149                                         ("Double-bounded variable, " (tt "LB <= x <= UB")))
150                               (describe "'(fixed LB UB)" 
151                                         ("Fixed variable, " (tt "LB = x = UB"))))))
152
153                  (procedure "lpx:set-column-bounds:: LPX * J * BOUNDS -> LPX"
154                             ("Sets bounds for column " (tt "J") " in the given problem. "
155                              "Argument " (tt "BOUNDS") " specifies the type and bounds "
156                              "for the specified column. It can take one of the following forms: " 
157                              (symbol-table 
158                               (describe "'(unbounded)" 
159                                         ("Free (unbounded) variable, " (tt "-Inf <= x <= +Inf")))
160                               (describe "'(lower-bound LB)" 
161                                         ("Variable with lower bound, " (tt "LB <= x <= +Inf")))
162                               (describe "'(upper-bound UB)" 
163                                         ("Variable with upper bound, " (tt "-Inf <= x <= UB")))
164                               (describe "'(double-bounded LB UB)" 
165                                         ("Double-bounded variable, " (tt "LB <= x <= UB")))
166                               (describe "'(fixed LB UB)" 
167                                         ("Fixed variable, " (tt "LB = x = UB"))))))
168
169                  (procedure "lpx:set-objective-coefficient:: LPX * J * COEF -> LPX"
170                             "Sets the objective coefficient at column " (tt "J") " (structural variable). ")
171                 
172                  (procedure "lpx:set-column-kind:: LPX * J * KIND -> LPX"
173                             ("Sets the kind of column " (tt "J") " (structural variable). "
174                              "Argument " (tt "KIND") " can be one of the following: "
175                              (symbol-table
176                               (describe "'iv" "integer variable")
177                               (describe "'cv" "continuous variable"))))
178                       
179                  (procedure "lpx:load-constraint-matrix:: LPX * F64VECTOR * NROWS * NCOLS [* ORDER] -> LPX"
180                             ("Loads the constraint matrix for the given problem. "
181                              "The constraints matrix is represented as an SRFI-4 " (tt "f64vector") 
182                              " (in row-major or column-major order). "
183                              "Optional argument " (tt "ORDER") 
184                              " specifies the element order of the constraints matrix. " 
185                              "It can be one of " (tt "'row-major") " or " (tt "'column-major") ". "))
186                             
187                  (procedure "lpx:get-column-primals:: LPX -> F64VECTOR"
188                             "Returns the primal values of all structural variables (columns). ")
189
190                  (procedure "lpx:get-objective-value:: LPX -> NUMBER"
191                             "Returns the current value of the objective function. ")
192
193
194                  ) ;; end subsection
195
196      (subsection "Problem control parameters"
197
198                  (p "The procedures in this section retrieve or set control parameters of GLPK problem object. "
199                     "If a procedure is invoked only with a problem object as an argument, it will return "
200                     "the value of its respective control parameter. If it is invoked with an additional argument, "
201                     "that argument is used to set a new value for the control parameter. ")
202
203                 
204                  ,(make-lpx-parameter-doc
205                    'message_level `((0 none) (1 error) (2 normal) (3 full))
206                    "Level of messages output by solver routines."
207                    )
208
209                  ,(make-lpx-parameter-doc 
210                    'scaling `((0 none) (1 equilibration) (2 geometric-mean) (3 geometric-mean+equilibration))
211                    "Scaling option."
212                    )
213
214                  ,(make-lpx-parameter-doc 
215                    'use_dual_simplex `bool
216                    "Dual simplex option."
217                    )
218                       
219                  ,(make-lpx-parameter-doc 
220                    'pricing `((0 textbook) (1 steepest-edge))
221                    "Pricing option (for both primal and dual simplex)."
222                    )
223
224                  ,(make-lpx-parameter-doc 
225                    'solution_rounding `bool
226                    "Solution rounding option."
227                    )
228
229                  ,(make-lpx-parameter-doc 
230                    'iteration_limit `int
231                    "Simplex iteration limit."
232                    )
233
234                  ,(make-lpx-parameter-doc 
235                    'iteration_count `int
236                    "Simplex iteration count."
237                    )
238
239                  ,(make-lpx-parameter-doc 
240                    'branching_heuristic `((0 first) (1 last) (2 driebeck+tomlin))
241                    "Branching heuristic option (for MIP only)."
242                    )
243
244                  ,(make-lpx-parameter-doc 
245                    'backtracking_heuristic `((0 dfs) (1 bfs) (2 best-projection) (3 best-local-bound))
246                    "Backtracking heuristic option (for MIP only)."
247                    )
248
249                  ,(make-lpx-parameter-doc 
250                    'use_presolver `bool
251                    "Use the LP presolver."
252                    )
253
254                  ,(make-lpx-parameter-doc 
255                    'relaxation `real
256                    "Relaxation parameter used in the ratio test."
257                    )
258                 
259                  ,(make-lpx-parameter-doc 
260                    'time_limit `real
261                    "Searching time limit, in seconds."
262                    )
263
264
265                  ) ;; end subsection
266
267      (subsection "Scaling & solver procedures"
268                 
269                  (procedure "lpx:scale-problem:: LPX -> LPX"
270                             ("This procedure performs scaling of of the constraints matrix in order "
271                              "to improve its numerical properties. ")
272                             )
273                 
274                  (procedure "lpx:simplex:: LPX -> STATUS"
275                             ("This procedure solves the given LP problem using the simplex method.  "
276                              "It can return one of the following status codes: "
277                              (symbol-table
278                               (describe "LPX_E_OK" "the LP problem has been successfully solved")
279
280                               (describe "LPX_E_BADB" "Unable to start
281the search, because the initial basis specified in the problem object
282is invalid--the number of basic (auxiliary and structural) variables
283is not the same as the number of rows in the problem object. ")
284
285                               (describe "LPX_E_SING" "Unable to start
286the search, because the basis matrix corresponding to the initial
287basis is singular within the working precision. ")
288
289                               (describe "LPX_E_COND" "Unable to start
290the search, because the basis matrix corresponding to the initial
291basis is ill-conditioned, i.e. its condition number is too large. ")
292
293                               (describe "LPX_E_BOUND" "Unable to start
294the search, because some double-bounded (auxiliary or structural)
295variables have incorrect bounds. ")
296
297                               (describe "LPX_E_FAIL" "The search was
298prematurely terminated due to the solver failure. ")
299
300                               (describe "LPX_E_OBJLL" "The search was
301prematurely terminated, because the objective function being maximized
302has reached its lower limit and continues decreasing (the dual simplex
303only). ")
304
305                               (describe "LPX_E_OBJUL" "The search was
306prematurely terminated, because the objective function being minimized
307has reached its upper limit and continues increasing (the dual simplex
308only). ")
309
310                               (describe "LPX_E_ITLIM" "The search was
311prematurely terminated, because the simplex iteration limit has been
312exceeded. ")
313
314                               (describe "LPX_E_TMLIM" "The search was
315prematurely terminated, because the time limit has been exceeded. ")
316
317                               (describe "LPX_E_NOPFS" "The LP problem
318instance has no primal feasible solution (only if the LP presolver is used). ")
319
320                               (describe "LPX_E_NODFS" "The LP problem
321instance has no dual feasible solution (only if the LP presolver is used)."))
322                               
323                              ))
324
325
326                  (procedure "lpx:integer:: LPX -> STATUS"
327                             "Solves an MIP problem using the branch-and-bound method. ")
328
329                  ) ;; end subsection
330
331      )
332
333     (examples (pre #<<EOF
334;;
335;; Two Mines Linear programming example from
336;;
337;; http://people.brunel.ac.uk/~mastjjb/jeb/or/basicor.html#twomines
338;;
339
340;; Two Mines Company
341;;
342;; The Two Mines Company owns two different mines that produce an ore
343;; which, after being crushed, is graded into three classes: high,
344;; medium and low-grade. The company has contracted to provide a
345;; smelting plant with 12 tons of high-grade, 8 tons of medium-grade
346;; and 24 tons of low-grade ore per week. The two mines have different
347;; operating characteristics as detailed below.
348;;
349;; Mine    Cost per day ($'000)    Production (tons/day)               
350;;                                High    Medium    Low
351;; X       180                     6       3         4
352;; Y       160                     1       1         6
353;;
354;;                                 Production (tons/week)
355;;                                High    Medium    Low
356;; Contract                       12       8        24
357;;
358;; How many days per week should each mine be operated to fulfill the
359;; smelting plant contract?
360;;
361
362(require-extension srfi-4)
363(require-extension glpk)
364
365;; (1) Unknown variables
366;;
367;;      x = number of days per week mine X is operated
368;;      y = number of days per week mine Y is operated
369;;
370;; (2) Constraints
371;;
372;;
373;;    * ore production constraints - balance the amount produced with
374;;      the quantity required under the smelting plant contract
375;;
376;;      High    6x + 1y >= 12
377;;      Medium  3x + 1y >= 8
378;;      Low     4x + 6y >= 24
379;;
380;; (3) Objective
381;;
382;;     The objective is to minimise cost which is given by 180x + 160y.
383;;
384;;     minimise  180x + 160y
385;;     subject to
386;;         6x + y >= 12
387;;         3x + y >= 8
388;;         4x + 6y >= 24
389;;         x <= 5
390;;         y <= 5
391;;         x,y >= 0
392;;
393;; (4) Auxiliary variables (rows)
394;;
395;;  p = 6x + y
396;;  q = 3x + y
397;;  r = 4x + 6y
398;;
399;;  12 <= p < +inf
400;;   8 <= q < +inf
401;;  24 <= r < +inf
402
403(define pbounds `((lower-bound 12) (lower-bound 8) (lower-bound 24)))
404
405;; (5) Structural variables (columns)
406;;
407;;  0 <= x <= 5
408;;  0 <= y <= 5
409
410(define xbounds  `((double-bounded 0 5) (double-bounded 0 5)))
411
412;; (6) Objective coefficients: 180, 160
413
414(define objcoefs (list 180 160))
415
416
417;; Constraints matrix (in row-major order)
418;;
419;;   6  1   
420;;   3  1   
421;;   4  6   
422
423(define constraints (f64vector 6 1 3 1 4 6))
424
425;; Create the problem definition & run the solver
426(let ((lpp (lpx:make-problem 'minimize pbounds xbounds objcoefs constraints)))
427  (lpx:scale-problem lpp)
428  (lpx:use_presolver lpp #t)
429  (let ((status (lpx:simplex lpp)))
430    (print "solution status = " status)
431    (print "objective value = " (lpx:get-objective-value lpp))
432    (print "primals = " (lpx:get-column-primals lpp))))
433
434EOF
435)
436     (license
437      "Copyright Ivan Raikov and the Okinawa Institute of Science and Technology.
438
439This program is free software: you can redistribute it and/or modify
440it under the terms of the GNU General Public License as published by
441the Free Software Foundation, either version 3 of the License, or (at
442your option) any later version.
443
444This program is distributed in the hope that it will be useful, but
445WITHOUT ANY WARRANTY; without even the implied warranty of
446MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
447General Public License for more details.
448
449A full copy of the GPL license can be found at
450<http://www.gnu.org/licenses/>.")))))
451
452
453(define glpk-eggdoc:css (make-parameter #<<EOF
454 <!--
455      CODE {
456            color: #666666;
457          }
458/*   DT.definition EM { font-weight: bold; font-style: normal; } */
459
460     DT.definition { 
461                   background: #eee;
462                   color: black;
463                   padding: 0.2em 1em 0.2em 0.7em;
464                   margin-left: 0.2em;
465border: 1px solid #bbc;
466                   font-family: "Andale Mono", monospace;
467                   /* font-size: 1.2em; */
468                   
469                 }
470     DD {
471                   margin-top: 0.8em;
472                   margin-bottom: 0.8em;
473     }
474     DIV.subsection {
475                    border-top: 1px solid #448;
476                    padding-left: 1em;
477                    margin-bottom: 1.2em;
478     }
479     DIV.subsubsection {
480                    border-top: 1px dotted #99c;
481                    /* border-left: 1px solid #99c; */
482                    padding-left: 1em;
483                    margin-bottom: 1.2em;
484     }
485     DIV.subsubsubsection {
486                    border-top: 1px solid #ddf;
487                    padding-left: 1em;
488                    margin-bottom: 1.2em;
489     }
490
491         DIV.section {
492                 margin-bottom: 1.5em;
493         }
494         a:link {
495                 color: #336;
496         }
497         a:visited { color: #666; }
498         a:active  { color: #966; }
499         a:hover   { color: #669; }
500         body { margin: 0; padding: 0; background: #fff; color: #000; font: 9pt "Lucida Grande", "Verdana", sans-serif; }
501         H2 {
502                 background: #336;
503                 color: #fff;
504                 padding-top: 0.5em;
505                 padding-bottom: 0.5em;
506                 padding-left: 16px;
507                 margin: 0 0 1em 0;
508        }
509        UL LI {
510                list-style: none;
511        }
512        TT {
513                font-family: "Andale Mono", monospace;
514                /* font-size: 1.2em; */
515        }
516        H3 {
517                color: #113;
518                margin-bottom: 0.5em;
519        }
520        H4, H5, H6 {
521                color: #113;
522                margin-bottom: 1.0em;
523        }
524        H5 {
525                font-weight: normal;
526                font-style: italic;
527                font-size: 100%;
528                margin-top: 1.2em;
529        }
530        H6 {
531                font-weight: bold;
532                font-size: 85%;
533                margin-top: 1.2em;
534        }
535     DIV#eggheader {
536         text-align: center;
537                 float: right;
538                 margin-right: 2em;
539     }
540     DIV#header IMG {
541            /* display: block; margin-left: auto; margin-right: auto;  */
542            /* float: right; */
543            border: none;  /* firefox */
544     }
545     DIV#footer {
546                background: #bbd;
547                padding: 0.7em ;
548                border-top: 1px solid #cce;
549     }
550     DIV#footer hr {
551                display: none;
552     }
553     DIV#footer a {
554                float: left;
555     }
556     DIV#revision-history {
557         float: right;
558     }
559     
560     DIV#body {
561                 margin: 1em 1em 1em 16px;
562         }
563
564     DIV#examples PRE {
565       background: #eef;
566       padding: 0.1em;
567       border: 1px solid #aac;
568     }
569     PRE#license, DIV#examples PRE {
570       padding: 0.5em;
571     }
572     DIV#examples PRE {
573       /* font-size: 85%; */
574     }
575     PRE { font-family: "Andale Mono", monospace; }
576     TABLE {
577       background: #eef;
578       padding: 0.2em;
579       border: 1px solid #aac;
580       border-collapse: collapse;
581       width: 100%;
582     }
583     TABLE.symbol-table TD.symbol {
584          width: 15em;
585          font-family: "Andale Mono", monospace;
586          vertical-align: top;
587          /* font-size: 1.2em; */
588     }
589     TABLE.symbol-table TD {
590          font-family: "Andale Mono", monospace;
591          vertical-align: top;
592          /* font-size: 1.2em; */
593     }
594     TH {
595       text-align: left;
596       border-bottom: 1px solid #aac;
597       padding: 0.25em 0.5em 0.25em 0.5em;
598     } 
599     TD { padding: 0.25em 0.5em 0.25em 0.5em; }
600     -->
601EOF
602))
603
604
605(if (eggdoc->html doc 
606                   `( (eggdoc-style . ,(lambda (tag)
607                         `("<style type=\"text/css\">" ,(glpk-eggdoc:css)
608                           "</style>")))
609                      (documentation *macro* . ,(lambda (tag . elts)
610                        (let* ((sections
611                                (pre-post-order elts
612                                                `((subsection   ;; (subsection level "content ...")
613                                                   ((*text* . ,(lambda (tag str) str)))
614                                                   . ,(lambda (tag head-word . elems)
615                                                        `(li (a (@ (href ,(string-append "#" head-word)))
616                                                                ,head-word))))
617                                                  (*default*
618                                                   . ,(lambda (tag . elems) (list)))
619                                                 
620                                                  (*text* . ,(lambda (trigger str) (list))))))
621                               (toc `(div (@ (class "toc"))
622                                          (ol ,sections))))
623                          `(section "Documentation" ,(cons toc elts)))))
624                      ,@(eggdoc:make-stylesheet doc) ))
625
626    (void))
Note: See TracBrowser for help on using the repository browser.