Next Page Contents

linopt::corners -- return the feasible corners of a linear program

Introduction

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.

Call(s)

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

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.

Returns

a set or a list with 3 elements.

Related Functions

linopt::maximize, linopt::minimize, linopt::plot_data

Details

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])                       
      [{[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:
     

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+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:
     

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000