## `linopt::minimize` -- minimize a linear or mixed-integer program

#### Introduction

`linopt::minimize(`[constr, obj]`)` returns the solution of the linear or mixed-integer program given by the constraints `constr` and the linear objective function `obj` which should be minimized.

#### Call(s)

`linopt::minimize([constr, obj])`
`linopt::minimize([constr, obj], DualPrices)`
`linopt::minimize([constr, obj <, NonNegative> <, seti>])`
`linopt::minimize([constr, obj <, NonNegative> <, All>])`
`linopt::minimize([constr, obj <, setn> <, seti>])`
`linopt::minimize([constr, obj <, setn> <, All>])`
`linopt::minimize([constr, obj <, NonNegative>], DualPrices)`
`linopt::minimize([constr, obj <, set>], DualPrices)`

#### Parameters

`constr` | - | a set or list of linear constraints
`obj` | - | a linear expression
`seti` | - | s set which contains identifiers interpreted as indeterminates
`setn` | - | a set which contains identifiers interpreted as indeterminates

#### Options

`All` | - | all variables are constrained to be integer
`NonNegative` | - | all variables are constrained to be nonnegative
`DualPrices` | - | This option is only available in the linear case. It causes the output of the dual-prices in addition to the solution-tripel.

#### Returns

a list or a sequence of a list and a set containing the solution of the linear or mixed-integer program.

#### Related Functions

`linopt::maximize`, `linopt::plot_data`, `linopt::corners`

#### Details

- The expression `obj` is the linear objective function to be minimized subject to the linear constraints `constr`. The function `linopt::minimize` returns a triple consisting of the state of the output, `OPTIMAL`, `EMPTY` or `UNBOUNDED`, a set of equations which describes the optimal solution of the specified linear program, which is empty or depends on a free variable PHI subject to the state, and finally the minimal objective function value, which can be either a number, `infinity` or a linear function in Phi.
- The states `OPTIMAL`, `EMPTY` or `UNBOUNDED` have the following meanings. `OPTIMAL` means an optimal solution for the linear program was found. If the state is `EMPTY` no optimal solution was found and if it is `UNBOUNDED` then the solution has no upper bound.
- If the option NonNegative is used all variables are constrained to be nonnegative. If instead of NonNegative a set `setn` is given then only the variables from `setn` are constrained to be nonnegative.
- If the option All is used all variables are constrained to be integers. If instead of All a set `seti` is given, then only the variables from `seti` are constrained to be integers.
- As a second parameter for `linopt::minimize` the option DualPrices is provided for the linear case (the first parameter therefore must not have more than three elements). This option causes the output of the dual-prices in addition to the solution-tripel. In this case the result of `linopt::minimize` is a sequence of a list containing the solution-tripel and a set containing the dual prices. See example 4.

#### Example 1

We try to solve the linear program

    c1 + c2 <= 3, c2 <= 9

with the linear objective function c1 + c2:

    >> linopt::minimize([{c1 + c2 <= 3, c2 <= 9}, -c1 - c2])

                         [OPTIMAL, {c1 = -6, c2 = 9}, -3]

#### Example 2

Now let's have a look at the linear program

    3*x + 4*y - 3*z <= 23, 5*x - 4*y - 3*z <= 10, 7*x + 4*y + 11*z <= 30

with the linear objective function -x + y + 2*z. If we make no restriction to the variables the result is unbounded:

    >> c := [{3*x + 4*y - 3*z <= 23, 5*x - 4*y - 3*z <= 10,
              7*x + 4*y + 11*z <= 30}, -x + y + 2*z]:
       linopt::minimize(c)

          --            {
          |  UNBOUNDED, { y = -PHI1, x = - 4 PHI1 - 13/2,
          --            {

                   16 PHI1        }    23 PHI1         --
             z = - ------- - 85/6 }, - ------- - 131/6  |
                      3           }       3            --

But if all variables are constrained to be nonnegative, we get a result. That's also the case if only x and y are constrained to be nonnegative:

    >> linopt::minimize(append(c, NonNegative));
       linopt::minimize(append(c, {x, y}))

                       [OPTIMAL, {y = 0, z = 0, x = 2}, -2]

                  [OPTIMAL, {x = 0, z = -11/2, y = 13/8}, -75/8]

    >> delete c:

#### Example 3

The following linear program do not have a solution:

    >> linopt::minimize([{x <= -1, x >= 0}, x])

                               [EMPTY, {}, infinity]

#### Example 4

The output of the dual prices can be enforced with the option DualPrices:

    >> linopt::minimize([{c1 + c2 <= 3, c2 <= 9}, -c1 - c2],
                        DualPrices)

          [OPTIMAL, {c1 = -6, c2 = 9}, -3],

             {[c2 <= 9, 0], [c1 + c2 <= 3, 1]}

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

- The order of the parameters changed. It's now also possible to solve a linear integer program.

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