doc/info/simplex.texi

   1 @menu
   2 * Introduction to simplex::
   3 * Functions and Variables for simplex::
   4 @end menu
   5
   6 @node Introduction to simplex, Functions and Variables for simplex, Package simplex, Package simplex
   7 @section Introduction to simplex
   8
   9 @code{simplex} is a package for linear optimization using the simplex algorithm.
  10
  11 Example:
  12
  13 @c ===beg===
  14 @c load("simplex")$
  15 @c minimize_lp(x+y, [3*x+2*y>2, x+4*y>3]);
  16 @c ===end===
  17 @example
  18 (%i1) load("simplex")$
  19 (%i2) minimize_lp(x+y, [3*x+2*y>2, x+4*y>3]);
  20                   9        7       1
  21 (%o2)            [--, [y = --, x = -]]
  22                   10       10      5
  23 @end example
  24
  25 @opencatbox{Categories:}
  26 @category{Numerical methods}
  27 @category{Optimization}
  28 @category{Share packages}
  29 @category{Package simplex}
  30 @closecatbox
  31
  32 @subsection Tests for simplex
  33
  34 There are some tests in the directory @code{share/simplex/Tests}.
  35
  36 @subsubsection klee_minty
  37
  38 The function @code{klee_minty} produces input for @code{linear_program}, for which
  39 exponential time for solving is required without scaling.
  40
  41 Example:
  42
  43 @example
  44 load("klee_minty")$
  45 apply(linear_program, klee_minty(6));
  46 @end example
  47
  48 A better approach:
  49
  50 @example
  51 epsilon_sx : 0$
  52 scale_sx : true$
  53 apply(linear_program, klee_minty(10));
  54 @end example
  55
  56 @subsubsection NETLIB
  57
  58 Some smaller problems from netlib (@url{https://www.netlib.org/lp/data/})
  59 test suite are converted to a format, readable by Maxima. Problems are
  60 @code{adlittle}, @code{afiro}, @code{kb2}, @code{sc50a} and
  61 @code{share2b}. Each problem has three input files in CSV format for
  62 matrix @var{A} and vectors @var{b} and @var{c}.
  63
  64 Example:
  65
  66 @example
  67 A : read_matrix("adlittle_A.csv", 'csv)$
  68 b : read_list("adlittle_b.csv", 'csv)$
  69 c : read_list("adlittle_c.csv", 'csv)$
  70 linear_program(A, b, c)$
  71 %[2];
  72 => 225494.9631623802
  73 @end example
  74
  75 Results:
  76
  77 @c see simplex/Tests/netlib.mac
  78 @example
  79 PROBLEM        MINIMUM                  SCALING
  80 adlittle       +2.2549496316E+05        false
  81 afiro          -4.6475314286E+02        false
  82 kb2            -1.7499001299E+03        true
  83 sc50a          -6.4575077059E+01        false
  84 share2b        -4.1573518187E+02        false
  85 @end example
  86
  87 The Netlib website @url{https://www.netlib.org/lp/data/readme} lists the values as
  88
  89 @example
  90 PROBLEM        MINIMUM
  91 adlittle       +2.2549496316E+05
  92 afiro          -4.6475314286E+02
  93 kb2            -1.7499001299E+03
  94 sc50a          -6.4575077059E+01
  95 share2b        -4.1573224074E+02
  96 @end example
  97
  98 @node Functions and Variables for simplex,  , Introduction to simplex, Package simplex
  99 @section Functions and Variables for simplex
 100
 101 @anchor{epsilon_lp}
 102 @defvr {Option variable} epsilon_lp
 103 Default value: @code{10^-8}
 104
 105 Epsilon used for numerical computations in @code{linear_program}; it is
 106 set to 0 in @code{linear_program} when all inputs are rational.
 107
 108 Example:
 109
 110 @c ===beg===
 111 @c load("simplex")$
 112 @c minimize_lp(-x, [1e-9*x + y <= 1], [x,y]);
 113 @c minimize_lp(-x, [10^-9*x + y <= 1], [x,y]);
 114 @c minimize_lp(-x, [1e-9*x + y <= 1], [x,y]), epsilon_lp=0;
 115 @c ===end===
 116 @example
 117 (%i1) load("simplex")$
 118
 119 (%i2) minimize_lp(-x, [1e-9*x + y <= 1], [x,y]);
 120 Warning: linear_program(A,b,c): non-rat inputs found, epsilon_lp= 1.0e-8
 121 Warning: Solution may be incorrect.
 122 (%o2)                        Problem not bounded!
 123 (%i3) minimize_lp(-x, [10^-9*x + y <= 1], [x,y]);
 124 (%o3)               [- 1000000000, [y = 0, x = 1000000000]]
 125 (%i4) minimize_lp(-x, [1e-9*x + y <= 1], [x,y]), epsilon_lp=0;
 126 (%o4)     [- 9.999999999999999e+8, [y = 0, x = 9.999999999999999e+8]]
 127 @end example
 128
 129 See also: @mref{linear_program}, @mref{ratnump}.
 130
 131 @opencatbox{Categories:}
 132 @category{Package simplex}
 133 @closecatbox
 134
 135 @end defvr
 136
 137 @anchor{linear_program}
 138 @deffn {Function} linear_program (@var{A}, @var{b}, @var{c})
 139
 140 @code{linear_program} is an implementation of the simplex algorithm.
 141 @code{linear_program(A, b, c)} computes a vector @var{x} for which
 142 @code{c.x} is minimum possible among vectors for which @code{A.x = b}
 143 and @code{x >= 0}. Argument @var{A} is a matrix and arguments @var{b}
 144 and @var{c} are lists.
 145
 146 @code{linear_program} returns a list which contains the minimizing
 147 vector @var{x} and the minimum value @code{c.x}. If the problem is not
 148 bounded, it returns "Problem not bounded!" and if the problem is not
 149 feasible, it returns "Problem not feasible!".
 150
 151 To use this function first load the @code{simplex} package with
 152 @code{load("simplex");}.
 153
 154 Example:
 155
 156 @c ===beg===
 157 @c A: matrix([1,1,-1,0], [2,-3,0,-1], [4,-5,0,0])$
 158 @c b: [1,1,6]$
 159 @c c: [1,-2,0,0]$
 160 @c linear_program(A, b, c);
 161 @c ===end===
 162 @example
 163 (%i2) A: matrix([1,1,-1,0], [2,-3,0,-1], [4,-5,0,0])$
 164 (%i3) b: [1,1,6]$
 165 (%i4) c: [1,-2,0,0]$
 166 (%i5) linear_program(A, b, c);
 167                    13     19        3
 168 (%o5)            [[--, 4, --, 0], - -]
 169                    2      2         2
 170 @end example
 171
 172 See also: @mref{minimize_lp}, @mref{scale_lp}, and @mref{epsilon_lp}.
 173
 174 @opencatbox{Categories:}
 175 @category{Package simplex}
 176 @category{Numerical methods}
 177 @closecatbox
 178
 179 @end deffn
 180
 181 @anchor{maximize_lp}
 182 @deffn {Function} maximize_lp (@var{obj}, @var{cond}, [@var{pos}])
 183
 184 Maximizes linear objective function @var{obj} subject to some linear
 185 constraints @var{cond}. See @mref{minimize_lp} for detailed
 186 description of arguments and return value.
 187
 188
 189 See also: @mref{minimize_lp}.
 190
 191 @opencatbox{Categories:}
 192 @category{Package simplex}
 193 @category{Numerical methods}
 194 @closecatbox
 195
 196 @end deffn
 197
 198 @anchor{minimize_lp}
 199 @deffn {Function} minimize_lp (@var{obj}, @var{cond}, [@var{pos}])
 200
 201 Minimizes a linear objective function @var{obj} subject to some linear
 202 constraints @var{cond}. @var{cond} a list of linear equations or
 203 inequalities. In strict inequalities @code{>} is replaced by @code{>=}
 204 and @code{<} by @code{<=}. The optional argument @var{pos} is a list
 205 of decision variables which are assumed to be positive.
 206
 207 If the minimum exists, @code{minimize_lp} returns a list which
 208 contains the minimum value of the objective function and a list of
 209 decision variable values for which the minimum is attained. If the
 210 problem is not bounded, @code{minimize_lp} returns "Problem not
 211 bounded!" and if the problem is not feasible, it returns "Problem not
 212 feasible!".
 213
 214 The decision variables are not assumed to be non-negative by default. If
 215 all decision variables are non-negative, set @code{nonnegative_lp} to
 216 @code{true} or include @code{all} in the optional argument @var{pos}. If
 217 only some of decision variables are positive, list them in the optional
 218 argument @var{pos} (note that this is more efficient than adding
 219 constraints).
 220
 221 @code{minimize_lp} uses the simplex algorithm which is implemented in
 222 maxima @code{linear_program} function.
 223
 224 To use this function first load the @code{simplex} package with
 225 @code{load("simplex");}.
 226
 227 Examples:
 228
 229 @c ===beg===
 230 @c minimize_lp(x+y, [3*x+y=0, x+2*y>2]);
 231 @c minimize_lp(x+y, [3*x+y>0, x+2*y>2]), nonnegative_lp=true;
 232 @c minimize_lp(x+y, [3*x+y>0, x+2*y>2], all);
 233 @c minimize_lp(x+y, [3*x+y=0, x+2*y>2]), nonnegative_lp=true;
 234 @c minimize_lp(x+y, [3*x+y>0]);
 235 @c ===end===
 236 @example
 237 (%i1) minimize_lp(x+y, [3*x+y=0, x+2*y>2]);
 238                       4       6        2
 239 (%o1)                [-, [y = -, x = - -]]
 240                       5       5        5
 241 (%i2) minimize_lp(x+y, [3*x+y>0, x+2*y>2]), nonnegative_lp=true;
 242 (%o2)                [1, [y = 1, x = 0]]
 243 (%i3) minimize_lp(x+y, [3*x+y>0, x+2*y>2], all);
 244 (%o3)                         [1, [y = 1, x = 0]]
 245 (%i4) minimize_lp(x+y, [3*x+y=0, x+2*y>2]), nonnegative_lp=true;
 246 (%o4)                Problem not feasible!
 247 (%i5) minimize_lp(x+y, [3*x+y>0]);
 248 (%o5)                Problem not bounded!
 249
 250 @end example
 251
 252 There is also a limited ability to solve linear programs with symbolic
 253 constants.
 254
 255 @example
 256 (%i1) declare(c,constant)$
 257 (%i2) maximize_lp(x+y, [y<=-x/c+3, y<=-x+4], [x, y]), epsilon_lp=0;
 258 Is (c-1)*c positive, negative or zero?
 259 p;
 260 Is c*(2*c-1) positive, negative or zero?
 261 p;
 262 Is c positive or negative?
 263 p;
 264 Is c-1 positive, negative or zero?
 265 p;
 266 Is 2*c-1 positive, negative or zero?
 267 p;
 268 Is 3*c-4 positive, negative or zero?
 269 p;
 270                                  1                1
 271 (%o2)                 [4, [x = -----, y = 3 - ---------]]
 272                                    1               1
 273                                1 - -          (1 - -) c
 274                                    c               c
 275 @end example
 276
 277 @c ===beg===
 278 @c (assume(c>4/3), declare(c,constant))$
 279 @c maximize_lp(x+y, [y<=-x/c+3, y<=-x+4], [x, y]), epsilon_lp=0;
 280 @c ===end===
 281 @example
 282 (%i1) (assume(c>4/3), declare(c,constant))$
 283 (%i2) maximize_lp(x+y, [y<=-x/c+3, y<=-x+4], [x, y]), epsilon_lp=0;
 284                                  1                1
 285 (%o2)                 [4, [x = -----, y = 3 - ---------]]
 286                                    1               1
 287                                1 - -          (1 - -) c
 288                                    c               c
 289 @end example
 290
 291 See also: @mref{maximize_lp}, @mref{nonnegative_lp}, @mref{epsilon_lp}.
 292
 293 @opencatbox{Categories:}
 294 @category{Package simplex}
 295 @category{Numerical methods}
 296 @closecatbox
 297
 298 @end deffn
 299
 300 @anchor{nonnegative_lp}
 301 @defvr {Option variable} nonnegative_lp
 302 @defvrx {Option variable} nonegative_lp
 303 Default value: @code{false}
 304
 305 If @code{nonnegative_lp} is true all decision variables to
 306 @code{minimize_lp} and @code{maximize_lp} are assumed to be non-negative.
 307 @code{nonegative_lp} is a deprecated alias.
 308
 309 See also: @mref{minimize_lp}.
 310
 311 @opencatbox{Categories:}
 312 @category{Package simplex}
 313 @closecatbox
 314
 315 @end defvr
 316
 317 @anchor{scale_lp}
 318 @defvr {Option variable} scale_lp
 319 Default value: @code{false}
 320
 321 When @code{scale_lp} is @code{true},
 322 @code{linear_program} scales its input so that the maximum absolute value in each row or column is 1.
 323
 324 @opencatbox{Categories:}
 325 @category{Package simplex}
 326 @closecatbox
 327
 328 @end defvr
 329
 330 @anchor{pivot_count_sx}
 331 @defvr {Variable} pivot_count_sx
 332
 333 After @code{linear_program} returns,
 334 @code{pivot_count_sx} is the number of pivots in last computation.
 335
 336 @opencatbox{Categories:}
 337 @category{Package simplex}
 338 @closecatbox
 339
 340 @end defvr
 341
 342 @anchor{pivot_max_sx}
 343 @defvr {Variable} pivot_max_sx
 344
 345 @code{pivot_max_sx} is the maximum number of pivots allowed by @code{linear_program}.
 346
 347 @opencatbox{Categories:}
 348 @category{Package simplex}
 349 @closecatbox
 350
 351 @end defvr
 352