Introduction to simplex
=======================

simplex is a package for linear optimization using the simplex algorithm.

Example:

     (%i1) load("simplex")$
     (%i2) minimize_lp(x+y, [3*x+2*y>2, x+4*y>3]);
                       9        7       1
     (%o2)            [--, [y = --, x = -]]
                       10       10      5

Numerical methods  Optimization Share packages Package simplex

Tests for simplex
-----------------

There are some tests in the directory share/simplex/Tests.

klee_minty
..........

The function klee_minty produces input for linear_program, for which exponential time for solving is required without scaling.

Example:

     load(klee_minty)$
     apply(linear_program, klee_minty(6));

A better approach:

     epsilon_sx : 0$
     scale_sx : true$
     apply(linear_program, klee_minty(10));

NETLIB
......

Some smaller problems from netlib (http://www.netlib.org/lp/data/) test suite are converted to a format, readable by Maxima. Problems are adlittle, afiro, kb2 and sc50a. Each problem has three input files in CSV format for matrix A and vectors B and C.

Example:

     A : read_matrix("adlittle_A.csv", 'csv)$
     b : read_list("adlittle_b.csv", 'csv)$
     c : read_list("adlittle_c.csv", 'csv)$
     linear_program(A, b, c)$
     %[2]
     => 225494.963126615

Results:

     PROBLEM        MINIMUM                SCALING
     adlittle       225494.963126615       no
     afiro          - 464.7531428571429    no
     kb2            - 1749.900129055996    yes
     sc50a          - 64.5750770585645     no

Functions and Variables for simplex
===================================

 -- Option variable: epsilon_lp
     Default value: 10^-8

     Epsilon used for numerical computations in linear_program.

     See also: linear_program.

     Package simplex

 -- Function: linear_program (A, B, C)

     linear_program is an implementation of the simplex algorithm. linear_program(A, b, c) computes a vector X for which c.x is minimum possible among vectors for which A.x = b and x >= 0. Argument A is a matrix and arguments B and C are lists.

     linear_program returns a list which contains the minimizing vector X and the minimum value c.x. If the problem is not bounded, it returns "Problem not bounded!" and if the problem is not feasible, it returns "Problem not feasible!".

     To use this function first load the simplex package with load(simplex);.

     Example:

          (%i2) A: matrix([1,1,-1,0], [2,-3,0,-1], [4,-5,0,0])$
          (%i3) b: [1,1,6]$
          (%i4) c: [1,-2,0,0]$
          (%i5) linear_program(A, b, c);
                             13     19        3
          (%o5)            [[--, 4, --, 0], - -]
                             2      2         2

     See also: minimize_lp, scale_lp, and epsilon_lp.

     Package simplex Numerical methods

 -- Function: maximize_lp (OBJ, COND, [POS])

     Maximizes linear objective function OBJ subject to some linear constraints COND. See minimize_lp for detailed description of arguments and return value.

     See also: minimize_lp.

     Package simplex Numerical methods

 -- Function: minimize_lp (OBJ, COND, [POS])

     Minimizes a linear objective function OBJ subject to some linear constraints COND. COND a list of linear equations or inequalities. In strict inequalities > is replaced by >= and < by <=. The optional argument POS is a list of decision variables which are assumed to be positive.

     If the minimum exists, minimize_lp returns a list which contains the minimum value of the objective function and a list of decision variable values for which the minimum is attained. If the problem is not bounded, minimize_lp returns "Problem not bounded!" and if the problem is not feasible, it returns "Problem not feasible!".

     The decision variables are not assumed to be nonegative by default. If all decision variables are nonegative, set nonegative_lp to true.  If only some of decision variables are positive, list them in the optional argument POS (note that this is more efficient than adding constraints).

     minimize_lp uses the simplex algorithm which is implemented in maxima linear_program function.

     To use this function first load the simplex package with load(simplex);.

     Examples:

          (%i1) minimize_lp(x+y, [3*x+y=0, x+2*y>2]);
                                4       6        2
          (%o1)                [-, [y = -, x = - -]]
                                5       5        5
          (%i2) minimize_lp(x+y, [3*x+y>0, x+2*y>2]), nonegative_lp=true;
          (%o2)                [1, [y = 1, x = 0]]
          (%i3) minimize_lp(x+y, [3*x+y=0, x+2*y>2]), nonegative_lp=true;
          (%o3)                Problem not feasible!
          (%i4) minimize_lp(x+y, [3*x+y>0]);
          (%o4)                Problem not bounded!

     See also: maximize_lp, nonegative_lp, epsilon_lp.

     Package simplex Numerical methods

 -- Option variable: nonegative_lp
     Default value: false

     If nonegative_lp is true all decision variables to minimize_lp and maximize_lp are assumed to be positive.

     See also: minimize_lp.

     Package simplex

 -- Option variable: scale_lp
     Default value: false

     When scale_lp is true, linear_program scales its input so that the maximum absolute value in each row or column is 1.

     Package simplex

 -- Variable: pivot_count_sx

     After linear_program returns, pivot_count_sx is the number of pivots in last computation.

     Package simplex

 -- Variable: pivot_max_sx

     pivot_max_sx is the maximum number of pivots allowed by linear_program.

     Package simplex