Previous Page Next Page Contents

linopt::minimize -- minimize a linear or mixed-integer program

Introduction

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.

Call(s)

linopt::minimize([constr, obj])
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)

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.

Returns

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

Related Functions

linopt::maximize, linopt::plot_data, linopt::corners

Details

Example 1

We try to solve the linear program

c1 + c2 <= 3, c2 <= 9

with the linear objective function c1 + c2:

>> linopt::minimize([{c1 + c2 <= 3, c2 <= 9}, -c1 - c2])
                     [OPTIMAL, {c1 = -6, c2 = 9}, -3]

Example 2

Now let's have a look at the linear program

3*x + 4*y - 3*z <= 23, 5*x - 4*y - 3*z <= 10, 7*x + 4*y + 11*z <= 30

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)                                        
      --            {
      |  UNBOUNDED, { y = -PHI1, x = - 4 PHI1 - 13/2,
      --            {
      
               16 PHI1        }    23 PHI1         --
         z = - ------- - 85/6 }, - ------- - 131/6  |
                  3           }       3            --

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}))    
                   [OPTIMAL, {y = 0, z = 0, x = 2}, -2]
      
              [OPTIMAL, {x = 0, z = -11/2, y = 13/8}, -75/8]
>> delete c:
     

Example 3

The following linear program do not have a solution:

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

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)
      [OPTIMAL, {c1 = -6, c2 = 9}, -3],
      
         {[c2 <= 9, 0], [c1 + c2 <= 3, 1]}

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000