## `linopt::corners` -- return the feasible corners of a linear program

#### Introduction

`linopt::corners(`[constr, obj], vars`)` returns all valid corners of the linear program.

`linopt::corners(`[constr, obj], vars, All`)` returns all corners of the linear program.

#### Call(s)

`linopt::corners([constr, obj], vars <, All> <, Logic>)`
`linopt::corners([constr, obj <, NonNegative> <, seti>], vars <, All> <, Logic>)`
`linopt::corners([constr, obj <, NonNegative> <, All>], vars <, All> <, Logic>)`
`linopt::corners([constr, obj <, setn> <, seti>], vars <, All> <, Logic>)`
`linopt::corners([constr, obj <, setn> <, All>], vars <, All> <, Logic>)`

#### Parameters

`constr` | - | a set or list of linear constraints
`obj` | - | a linear expression
`seti` | - | a set which contains identifiers interpreted as indeterminants
`setn` | - | a set which contains identifiers interpreted as indeterminants
`vars` | - | a list containing the variables of the linear program described by `constr` and `obj` and the existing options

#### Options

`All` | - | This option can appear at two different places in the call of `linopt::corners`. If it is part of the linear program it means that all variables are constrained to be integers. If it appears as the third or forth argument of the call it means that all corners, not only the valid ones should be computed by `linopt::corners`.
`NonNegative` | - | all variables are constrained to be nonnegative
`Logic` | - | This allows the algorithm to search for corners in planes like x=0 too, although x>=0 is not part of the linear program.

#### Returns

a set or a list with 3 elements.

#### Related Functions

`linopt::maximize`, `linopt::minimize`, `linopt::plot_data`

#### Details

- [`constr`, `obj`] is a linear program of the same structure like in `linopt::maximize`. The second parameter `vars` specifies the order in which the components of the corners found are printed; if e.g. {x=1, y=2}is a corner and [x,y] was entered, [1,2] will be returned.
- As options, for finding the corners, one may use `All` and/or `Logic`. `All` causes the output of non-feasible corners, too, `Logic` allows the algorithm to search for corners in planes like x=0, too, although x>=0 is not part of the input. This guarantees that for all non-empty feasible regions a corner will be found.
- As the result of `linopt::corners` a triple consisting of the set of corners, the maximal objective function value found and the corner associated to it is returned. If there is no feasible corner found, only the empty set is returned.

#### Example 1

We compute all valid corners of a small linear program:

    >> k := [[4 <= 2*x + 2*y, -2 <= 4*y - 2*x, -8 <= y - 2*x,
              y - 2*x <= -2, y <= 6], x + y]:
       linopt::corners(k, [x, y])

          [{[5, 2], [4, 6], [7, 6], [4/3, 2/3], [5/3, 1/3]}, 13, [7, 6]]

Now we compute all corners, also the ones which are not valid. We see that we now get e.g. also the corner which is given by the cut of -2x+4y = 2 and -2*x+y<=-2 . Here we see that the invalid corner (13,6) has the maximal objective function value 19:

    >> k := [[4 <= 2*x + 2*y, -2 <= 4*y - 2*x, -8 <= y - 2*x,
              y - 2*x <= -2, y <= 6], x + y]:
       linopt::corners(k, [x, y], All)

          [{[1, 0], [5, 2], [-4, 6], [4, 6], [7, 6], [13, 6],

             [4/3, 2/3], [5/3, 1/3], [10/3, -4/3]}, 19, [13, 6]]

    >> delete k:

#### Example 2

As one can see the linear program given by the constraints x+y>=-1 and x+y<=3 and the linear objective function x+2y has no corners:

    >> l := [[-1 <= x + y, x + y <= 3], x + 2*y]:
       linopt::corners(l,[x,y]), linopt::corners(l,[x,y], All)

                                      {}, {}

If one also assumes a cut with a coordinate plane as a corner, some corners exist. One can use `linopt::plot_data` to visualize this problem:

    >> linopt::corners(l, [x,y], Logic)

              [{[0, 0], [0, -1], [-1, 0], [0, 3], [3, 0]}, 6, [0, 3]]

    >> delete l:

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