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

#### Introduction

`linopt::maximize(`[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 maximized.

#### Call(s)

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

#### Parameters

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

#### Options

`All` | - | all variables are constrained to be integers
`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-triple.

#### 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::minimize`, `linopt::plot_data`, `linopt::corners`

#### Details

- The expression `obj` is the linear objective function to be maximized subject to the linear constraints `constr`. The function `linopt::maximize` 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 maximal 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::maximize` 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::maximize` 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

    2*c1 <= 1, 2*c2 <= 1

with the linear objective function c1 + 2*c2:

    >> linopt::maximize([{2*c1 <= 1, 2*c2 <= 1}, c1 + 2*c2])

                       [OPTIMAL, {c1 = 1/2, c2 = 1/2}, 3/2]

#### 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::maximize(c)

          --            {                       7 PHI1         }
          |  UNBOUNDED, { y = 0, x = -PHI1, z = ------ + 30/11 },
          --            {                         11           }

             25 PHI1         --
             ------- + 60/11  |
               11            --

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::maximize(append(c, NonNegative));
       linopt::maximize(append(c, {x, y}))

                    [OPTIMAL, {x = 0, z = 1/2, y = 49/8}, 57/8]

                    [OPTIMAL, {x = 0, z = 1/2, y = 49/8}, 57/8]

    >> delete c:

#### Example 3

The following linear program do not have a solution:

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

                              [EMPTY, {}, -infinity]

#### Example 4

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

    >> linopt::maximize([{2*c1 <= 1, 2*c2 <= 1},c1 + 2*c2],
                        DualPrices)

          [OPTIMAL, {c1 = 1/2, c2 = 1/2}, 3/2],

             {[c1 <= 1/2, 1], [c2 <= 1/2, 2]}

#### Example 5

We have a look at the knapsack problem with x1, x2, x3, x4 elements of 0, 1:

    >> c := {20*x1 + 15*x2 + 20*x3 + 5*x4 <= 25}:
       c := c union {x1 <= 1, x2 <= 1, x3 <= 1, x4 <= 1}:
       f := 10*x1 + 15*x2 + 16*x3 + x4:
       linopt::maximize([c, f, NonNegative, All])

                  [OPTIMAL, {x1 = 0, x2 = 0, x3 = 1, x4 = 1}, 17]

    >> delete c, f:

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