simplex-pkg (Maxima 5.42.455.gc5fa8d39c Manual)

81 simplex

81.1 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

Categories: Numerical methods Optimization Share packages Package simplex

81.1.1 Tests for simplex

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

81.1.1.1 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));

81.1.1.2 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, sc50a and share2b. 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.9631623802

Results:

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

The Netlib website http://www.netlib.org/lp/data/readme lists the values as

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

81.2 Functions and Variables for simplex

Option variable: epsilon_lp

Default value: 10^-8

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

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]]

See also: minimize_lp.

Categories: 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 non-negative by default. If all decision variables are non-negative, set nonnegative_lp to true or include all in the optional argument pos. 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]), 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!

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

(%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

(%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

See also: maximize_lp, nonnegative_lp, epsilon_lp.

Categories: Package simplex Numerical methods

Option variable: nonnegative_lp

Option variable: nonegative_lp

Default value: false

If nonnegative_lp is true all decision variables to minimize_lp and maximize_lp are assumed to be non-negative. nonegative_lp is a deprecated alias.

• Introduction to simplex:
• Functions and Variables for simplex: