## `linopt::Transparent::clean_basis` -- delete all slack variables of the first phase from the basis

#### Introduction

`linopt::Transparent::clean_basis(`tableau`)` removes the additional slack variables of the phase one of the simplex algorithm from the optimal basic (described by `tableau`) calculated by `linopt::Transparent::phaseI_tableau` and `linopt::Transparent::simplex`.

#### Call(s)

`linopt::Transparent::clean_basis(tableau)`

#### Parameters

`tableau` | - | a simplex tableau of domain type `linopt::Transparent`

#### Returns

a simplex tableau of domain type `linopt::Transparent`.

#### Related Functions

`linopt::Transparent`, `linopt::Transparent::autostep`, `linopt::Transparent::convert`, `linopt::Transparent::dual_prices`, `linopt::Transparent::phaseII_tableau`, `linopt::Transparent::result`, `linopt::Transparent::simplex`, `linopt::Transparent::suggest`, `linopt::Transparent::userstep`

#### Details

- At the end of the phase one of the 2-phase simplex algorithm, explicitly started by using `linopt::Transparent::phaseI_tableau`, it is necessary to eliminate all artificial variables from the optimal basis before phase two can be started by using `linopt::Transparent::phaseII_tableau`. `linopt::Transparent::clean_basis` performs some pivot steps until all phase one slack variables do not occur in the basis any longer.

#### Example 1

In this example we first compute an optimal basis for the first phase of the simplex algorithm:

    >> t := linopt::Transparent([[x <= 1,y <= 1,x + y >= 2],
                                 0,NonNegative]):
       t := linopt::Transparent::phaseI_tableau(t):
       t := linopt::Transparent::simplex(t)

                               array(1..5, 1..10,
                                 (1, 1) = "linopt",
                                 (1, 2) = "restr",
                                 (1, 3) = slk[4],
                                 (1, 4) = slk[5],
                                 (1, 5) = slk[6],
                                 (1, 6) = slk[1],
                                 (1, 7) = slk[2],
                                 (1, 8) = slk[3],
                                 (1, 9) = x,
                                 (1, 10) = y,
                                 (2, 1) = "obj",
                                 (2, 2) = 0,
                                        .
                                        .
                                 (4, 10) = 1,
                                 (5, 1) = slk[6],
                                 (5, 2) = 0,
                                 (5, 3) = -1,
                                 (5, 4) = -1,
                                 (5, 5) = 1,
                                 (5, 6) = -1,
                                 (5, 7) = -1,
                                 (5, 8) = -1,
                                 (5, 9) = 0,
                                 (5, 10) = 0
                               )

As we can see the artificial slack variable slk[6] is an element of the optimal basis. An error message is returned if we apply `linopt::Transparent::phaseII_tableau` or `linopt::Transparent::simplex` to this simplex tableau:

    >> linopt::Transparent::phaseII_tableau(t);

          Error:  Clean the basis from phase I slack variables first! [l\
          inopt::Transparent::phaseII_tableau]

So we have to use `linopt::Transparent::clean_basis` before continuing with the appropriate function. To get a smarter output in this example one should use at least a `TEXTWIDTH` of 80:

    >> t := linopt::Transparent::clean_basis(t);
       linopt::Transparent::phaseII_tableau(t)

                               array(1..5, 1..10,
                                 (1, 1) = "linopt",
                                 (1, 2) = "restr",
                                 (1, 3) = slk[4],
                                 (1, 4) = slk[5],
                                 (1, 5) = slk[6],
                                 (1, 6) = slk[1],
                                 (1, 7) = slk[2],
                                 (1, 8) = slk[3],
                                 (1, 9) = x,
                                 (1, 10) = y,
                                 (2, 1) = "obj",
                                 (2, 2) = 0,
                                        .
                                        .
                                 (4, 10) = 1,
                                 (5, 1) = slk[1],
                                 (5, 2) = 0,
                                 (5, 3) = 1,
                                 (5, 4) = 1,
                                 (5, 5) = -1,
                                 (5, 6) = 1,
                                 (5, 7) = 1,
                                 (5, 8) = 1,
                                 (5, 9) = 0,
                                 (5, 10) = 0
                               )

               +-                                                 -+
               |  "linopt", "restr", slk[1], slk[2], slk[3], x, y  |
               |                                                   |
               |    "obj",     0,       0,      0,      0,   0, 0  |
               |                                                   |
               |      x,       1,       0,     -1,     -1,   1, 0  |
               |                                                   |
               |      y,       1,       0,      1,      0,   0, 1  |
               |                                                   |
               |   slk[1],     0,       1,      1,      1,   0, 0  |
               +-                                                 -+

    >> delete t:

#### Background

- References:

  Papadimitriou, Christos H; Steiglitz, Kenneth: Combinatorial Optimization; Algorithms and Complexity. Prentice-Hall, 1982.

  Nemhauser, George L; Wolsey, Laurence A: Integer and Combinatorial Optimization. New York, Wiley, 1988.

  Salkin, Harvey M; Mathur, Kamlesh: Foundations of Integer Programming. North-Holland, 1989.

  Neumann, Klaus; Morlock, Martin: Operations-Research. Munich, Hanser, 1993.

  Duerr, Walter; Kleibohm, Klaus: Operations Research; Lineare Modelle und ihre Anwendungen. Munich, Hanser, 1992.

  Suhl, Uwe H: MOPS - Mathematical OPtimization System. European Journal of Operational Research 72(1994)312-322. North-Holland, 1994.

  Suhl, Uwe H; Szymanski, Ralf: Supernode Processing of Mixed Integer Models. Boston, Kluwer Academic Publishers, 1994.

#### Changes

- new function
- The linopt library was completely rewritten in MuPAD version 2.0.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000