### 83.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

#### 83.1.1 Tests for simplex

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

#### 83.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));

#### 83.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