linopt::minimize

Minimize a linear or mixed-integer program

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

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)

Description

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.

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 Φ subject to the state, and finally the minimal 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::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.

Examples

Example 1

We try to solve the linear program

with the linear objective function - c1 - c2:

linopt::minimize([{c1 + c2 <= 3, c2 <= 9}, -c1 - 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::minimize(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::minimize(append(c, NonNegative));
linopt::minimize(append(c, {x, y}))

delete c:

Example 3

The following linear program does not have a solution:

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

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)

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.

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.

Was this topic helpful?