## `linopt::Transparent::convert` -- transform the given tableau into a structure printable on screen

#### Introduction

`linopt::Transparent::convert(`tableau`)` converts the simplex tableau, into a two dimensional array.

#### Call(s)

`linopt::Transparent::convert(tableau)`

#### Parameters

`tableau` | - | a simplex tableau of domain type

#### Returns

a two dimensional array, representing the given simplex tableau `tableau`.

#### Related Functions

`linopt::Transparent`, `linopt::Transparent::autostep`, `linopt::Transparent::phaseI_tableau`, `linopt::Transparent::phaseII_tableau`, `linopt::Transparent::suggest`, `linopt::Transparent::userstep`

#### Details

- Internally the given `tableau` of domain type `linopt::Transparent` contains a lot of more information than the simplex tableau which is printed by some functions of the `linopt` library, e.g. `linopt::Transparent::simplex`, and which is visible on the screen. Furthermore it is not possible to access the element in the i-th row and j-th column of `tableau` to get the corresponding element from the simplex tableau which is visible on the screen.

  `linopt::Transparent::convert` converts `tableau` into a two dimensional array which corresponds with the screen-tableau. One can now access the element in the i-th row and j-th column of the simplex tableau by accessing the corresponding element of the array.

  While the internal structure of `tableau` is not known the structure of the two dimensional array is well defined. So it can be easily used in own procedures. See example 2.

#### Example 1

We convert a simplex tableau of domain type `linopt::Transparent` into a two dimensional array:

    >> k := [[x + y >= 2], x, NonNegative]:
       t := linopt::Transparent(k):
       a := linopt::Transparent::convert(t):
       t, domtype(t);
       a, domtype(a)

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

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

    >> delete a, k, t:

#### Example 2

We will write another simplex routine `mysimplex` for solving a linear program. For this we define the function `eigenpivot` for finding the pivot element of a given simplex tableau. `eigenpivot` assumes that the simplex tableau is given as a two dimensional array.

Here is the procedure `eigenpivot`, which is not coded in every detail, e.g., the error checking isn't implemented completely:

    >> eigenpivot := proc(T: DOM_ARRAY)
          local i,j,m,n,k,l,mini;
          begin
            m := op(T,[0,2,2]):
            n := op(T,[0,3,2]):
            k := 0:
            l := 0:
            mini := unbesetzt:

            for j from 3 to n do
              if T[2,j] < 0 then
                l := j:
                break
              end_if:
            end_for:
            if l=0 then return(OPTIMAL) end_if:
            for i from 3 to m do
              if T[i,l] > 0 and (mini=unbesetzt or T[i,2]/T[i,l] < mini) then
                k := i:
                mini := T[k,2]/T[k,l]
              end_if
            end_for:
            if k=0 then return(UNBOUNDED) end_if:
            return(T[k,1],T[1,l]):
       end_proc:

This is the new simplex algorithm `mysimplex` which uses `eigenpivot` and some function from the `linopt` library:

    >> mysimplex := proc(P)
          local T;
          begin
            T := linopt::Transparent(P):
            T := linopt::Transparent::phaseI_tableau(T):
            piv := eigenpivot(linopt::Transparent::convert(T)):
            while piv <> OPTIMAL and piv <> UNBOUNDED do
              T := linopt::Transparent::userstep(T,piv):
              piv := eigenpivot(linopt::Transparent::convert(T))
            end_while:

            if piv = UNBOUNDED then
              error(" Phase I unbounded ?!?")
            end_if:
            if T[2,2] <> 0
               then return(EMPTY)
            end_if:
            T := linopt::Transparent::clean_basis(T):

            T := linopt::Transparent::phaseII_tableau(T):
            piv := eigenpivot(linopt::Transparent::convert(T)):
            while piv <> OPTIMAL and piv <> UNBOUNDED do
              T := linopt::Transparent::userstep(T,piv):
              piv := eigenpivot(linopt::Transparent::convert(T))
            end_while:

            if piv = OPTIMAL
              then return(linopt::Transparent::result(T))
              else return(UNBOUNDED)
            end_if
       end_proc:

We now apply `mysimplex` to a linear program:

    >> k := [[2*x + 2*y >= 4, -2*x + 4*y >= -2, -2*x + y>= -8,
              -2*x + y <= -2, y <= 6], -x - y]:
       k := append(k, NonNegative):
       mysimplex(k);

                                  {x = 7, y = 6}

    >> delete k, eigenpivot, mysimplex:

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