linopt::corners
-- return the
feasible corners of a linear programlinopt::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.
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>)
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 |
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. |
a set or a list with 3 elements.
linopt::maximize
,
linopt::minimize
,
linopt::plot_data
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.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.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.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])
[{[5, 2], [4, 6], [7, 6], [4/3, 2/3], [5/3, 1/3]}, 13, [7, 6]]
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 -2x+4y = 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)
[{[1, 0], [5, 2], [-4, 6], [4, 6], [7, 6], [13, 6], [4/3, 2/3], [5/3, 1/3], [10/3, -4/3]}, 19, [13, 6]]
>> delete k:
As one can see the linear program given by the constraints x+y>=-1 and x+y<=3 and the linear objective function x+2y 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)
[{[0, 0], [0, -1], [-1, 0], [0, 3], [3, 0]}, 6, [0, 3]]
>> delete l:
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.