Documentation

linopt::maximize

Maximize a linear or mixed-integer program

MuPAD® notebooks will be removed in a future release. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

Syntax

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)

Description

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.

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 Φ subject to the state, and finally the maximal objective function value, which can be either a number, -infinity or a linear function in Φ.

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.

Examples

Example 1

We try to solve the linear program with the linear objective function c1 + 2 c2:

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

Now let's have a look at the linear program 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) 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}))  delete c:

Example 3

The following linear program do not have a solution:

linopt::maximize([{x <= -1, x >= 0}, x]) 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) Example 5

We have a look at the knapsack problem with x1, x2, x3, x4 ∈ {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]) delete c, f:

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.

Return Values

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

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.