linopt::corners

Return the feasible corners of a linear 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::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>)

Description

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.

[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.

Examples

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])

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 - 2 x + 4 y = 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)

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 + 2 y 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)

delete l:

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.

Return Values

Set or a list with 3 elements.

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.