@menu
* Introduction to simplex::
* Functions and Variables for simplex::
@end menu

@node Introduction to simplex, Functions and Variables for simplex, simplex-pkg, simplex-pkg
@section Introduction to simplex

@code{simplex} is a package for linear optimization using the simplex algorithm.

Example:

@c ===beg===
@c load("simplex")$
@c minimize_lp(x+y, [3*x+2*y>2, x+4*y>3]);
@c ===end===
@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
@end example

@opencatbox{Categories:}
@category{Numerical methods} 
@category{Optimization}
@category{Share packages}
@category{Package simplex}
@closecatbox

@subsection Tests for simplex

There are some tests in the directory @code{share/simplex/Tests}.

@subsubsection klee_minty

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

Example:

@example
load("klee_minty")$
apply(linear_program, klee_minty(6));
@end example

A better approach:

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

@subsubsection NETLIB

Some smaller problems from netlib (@url{https://www.netlib.org/lp/data/})
test suite are converted to a format, readable by Maxima. Problems are
@code{adlittle}, @code{afiro}, @code{kb2}, @code{sc50a} and
@code{share2b}. Each problem has three input files in CSV format for
matrix @var{A} and vectors @var{b} and @var{c}.

Example:

@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.9631623802
@end example

Results:

@c see simplex/Tests/netlib.mac
@example
PROBLEM        MINIMUM                  SCALING
adlittle       +2.2549496316E+05        false
afiro          -4.6475314286E+02        false
kb2            -1.7499001299E+03        true
sc50a          -6.4575077059E+01        false
share2b        -4.1573518187E+02        false
@end example

The Netlib website @url{https://www.netlib.org/lp/data/readme} lists the values as

@example
PROBLEM        MINIMUM
adlittle       +2.2549496316E+05
afiro          -4.6475314286E+02
kb2            -1.7499001299E+03
sc50a          -6.4575077059E+01
share2b        -4.1573224074E+02
@end example

@node Functions and Variables for simplex,  , Introduction to simplex, simplex-pkg
@section Functions and Variables for simplex

@anchor{epsilon_lp}
@defvr {Option variable} epsilon_lp
Default value: @code{10^-8}

Epsilon used for numerical computations in @code{linear_program}; it is
set to 0 in @code{linear_program} when all inputs are rational.

Example:

@c ===beg===
@c load("simplex")$
@c minimize_lp(-x, [1e-9*x + y <= 1], [x,y]);
@c minimize_lp(-x, [10^-9*x + y <= 1], [x,y]);
@c minimize_lp(-x, [1e-9*x + y <= 1], [x,y]), epsilon_lp=0;
@c ===end===
@example
(%i1) load("simplex")$

(%i2) minimize_lp(-x, [1e-9*x + y <= 1], [x,y]);
Warning: linear_program(A,b,c): non-rat inputs found, epsilon_lp= 1.0e-8
Warning: Solution may be incorrect.
(%o2)                        Problem not bounded!
(%i3) minimize_lp(-x, [10^-9*x + y <= 1], [x,y]);
(%o3)               [- 1000000000, [y = 0, x = 1000000000]]
(%i4) minimize_lp(-x, [1e-9*x + y <= 1], [x,y]), epsilon_lp=0;
(%o4)     [- 9.999999999999999e+8, [y = 0, x = 9.999999999999999e+8]]
@end example

See also: @mref{linear_program}, @mref{ratnump}.

@opencatbox{Categories:}
@category{Package simplex}
@closecatbox

@end defvr

@anchor{linear_program}
@deffn {Function} linear_program (@var{A}, @var{b}, @var{c})

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

@code{linear_program} returns a list which contains the minimizing
vector @var{x} and the minimum value @code{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 @code{simplex} package with
@code{load("simplex");}.

Example:

@c ===beg===
@c A: matrix([1,1,-1,0], [2,-3,0,-1], [4,-5,0,0])$
@c b: [1,1,6]$
@c c: [1,-2,0,0]$
@c linear_program(A, b, c);
@c ===end===
@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
@end example

See also: @mref{minimize_lp}, @mref{scale_lp}, and @mref{epsilon_lp}.

@opencatbox{Categories:}
@category{Package simplex}
@category{Numerical methods}
@closecatbox

@end deffn

@anchor{maximize_lp}
@deffn {Function} maximize_lp (@var{obj}, @var{cond}, [@var{pos}])

Maximizes linear objective function @var{obj} subject to some linear
constraints @var{cond}. See @mref{minimize_lp} for detailed
description of arguments and return value.


See also: @mref{minimize_lp}.

@opencatbox{Categories:}
@category{Package simplex}
@category{Numerical methods}
@closecatbox

@end deffn

@anchor{minimize_lp}
@deffn {Function} minimize_lp (@var{obj}, @var{cond}, [@var{pos}])

Minimizes a linear objective function @var{obj} subject to some linear
constraints @var{cond}. @var{cond} a list of linear equations or
inequalities. In strict inequalities @code{>} is replaced by @code{>=}
and @code{<} by @code{<=}. The optional argument @var{pos} is a list
of decision variables which are assumed to be positive.

If the minimum exists, @code{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, @code{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 non-negative by default. If
all decision variables are non-negative, set @code{nonnegative_lp} to
@code{true} or include @code{all} in the optional argument @var{pos}. If
only some of decision variables are positive, list them in the optional
argument @var{pos} (note that this is more efficient than adding
constraints).

@code{minimize_lp} uses the simplex algorithm which is implemented in
maxima @code{linear_program} function.

To use this function first load the @code{simplex} package with
@code{load("simplex");}.

Examples:

@c ===beg===
@c minimize_lp(x+y, [3*x+y=0, x+2*y>2]);
@c minimize_lp(x+y, [3*x+y>0, x+2*y>2]), nonnegative_lp=true;
@c minimize_lp(x+y, [3*x+y>0, x+2*y>2], all);
@c minimize_lp(x+y, [3*x+y=0, x+2*y>2]), nonnegative_lp=true;
@c minimize_lp(x+y, [3*x+y>0]);
@c ===end===
@example
(%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]), nonnegative_lp=true;
(%o2)                [1, [y = 1, x = 0]]
(%i3) minimize_lp(x+y, [3*x+y>0, x+2*y>2], all);
(%o3)                         [1, [y = 1, x = 0]]
(%i4) minimize_lp(x+y, [3*x+y=0, x+2*y>2]), nonnegative_lp=true;
(%o4)                Problem not feasible!
(%i5) minimize_lp(x+y, [3*x+y>0]);
(%o5)                Problem not bounded!

@end example

There is also a limited ability to solve linear programs with symbolic
constants.

@example
(%i1) declare(c,constant)$
(%i2) maximize_lp(x+y, [y<=-x/c+3, y<=-x+4], [x, y]), epsilon_lp=0;
Is (c-1)*c positive, negative or zero?
p;
Is c*(2*c-1) positive, negative or zero?
p;
Is c positive or negative?
p;
Is c-1 positive, negative or zero?
p;
Is 2*c-1 positive, negative or zero?
p;
Is 3*c-4 positive, negative or zero?
p;
                                 1                1
(%o2)                 [4, [x = -----, y = 3 - ---------]]
                                   1               1
                               1 - -          (1 - -) c
                                   c               c
@end example

@c ===beg===
@c (assume(c>4/3), declare(c,constant))$
@c maximize_lp(x+y, [y<=-x/c+3, y<=-x+4], [x, y]), epsilon_lp=0;
@c ===end===
@example
(%i1) (assume(c>4/3), declare(c,constant))$
(%i2) maximize_lp(x+y, [y<=-x/c+3, y<=-x+4], [x, y]), epsilon_lp=0;
                                 1                1
(%o2)                 [4, [x = -----, y = 3 - ---------]]
                                   1               1
                               1 - -          (1 - -) c
                                   c               c
@end example

See also: @mref{maximize_lp}, @mref{nonnegative_lp}, @mref{epsilon_lp}.

@opencatbox{Categories:}
@category{Package simplex}
@category{Numerical methods}
@closecatbox

@end deffn

@anchor{nonnegative_lp}
@defvr {Option variable} nonnegative_lp
@defvrx {Option variable} nonegative_lp
Default value: @code{false}

If @code{nonnegative_lp} is true all decision variables to
@code{minimize_lp} and @code{maximize_lp} are assumed to be non-negative.
@code{nonegative_lp} is a deprecated alias.
                   
See also: @mref{minimize_lp}.

@opencatbox{Categories:}
@category{Package simplex}
@closecatbox

@end defvr

@anchor{scale_lp}
@defvr {Option variable} scale_lp
Default value: @code{false}

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

@opencatbox{Categories:}
@category{Package simplex}
@closecatbox

@end defvr

@anchor{pivot_count_sx}
@defvr {Variable} pivot_count_sx

After @code{linear_program} returns,
@code{pivot_count_sx} is the number of pivots in last computation.

@opencatbox{Categories:}
@category{Package simplex}
@closecatbox

@end defvr

@anchor{pivot_max_sx}
@defvr {Variable} pivot_max_sx

@code{pivot_max_sx} is the maximum number of pivots allowed by @code{linear_program}.

@opencatbox{Categories:}
@category{Package simplex}
@closecatbox

@end defvr