Next: , Previous: , Up: simplex   [Contents][Index]

86.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 ·

86.1.1 Tests for simplex

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

86.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));

86.1.1.2 NETLIB

Some smaller problems from netlib (https://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 https://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

Next: , Previous: , Up: simplex   [Contents][Index]