solve a linear program in Matrix Form - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Optimization : Optimization Package : Optimization/LPSolveMatrixForm

Optimization[LPSolve](Matrix Form) - solve a linear program in Matrix Form

Calling Sequence

LPSolve(c, lc, bd, opts)

Parameters

c

-

Vector or NoUserValue; linear objective function

lc

-

(optional) list; linear constraints

bd

-

(optional) list; bounds

opts

-

(optional) equation(s) of the form option = value where option is one of assume, binaryvariables, depthlimit, feasibilitytolerance, infinitebound, initialpoint, integertolerance, integervariables, iterationlimit, maximize, method, nodelimit or output; specify options for the LPSolve command

Description

• 

The LPSolve command solves a linear program  (LP), which involves computing the minimum  (or maximum ) of a linear objective function  subject to linear constraints . An LP has the following form.

  

minimize (or maximize) c'x

  

subject to

  

A.xb (linear inequality constraints)

  

Aeq.x=beq (linear equality constraints)

  

b1xbu (bounds)

  

where x is the vector of problem variables; c, b, beq, bl, and bu are vectors; and A and Aeq are matrices.  The relations involving matrices and vectors are element-wise. In the function defined, c' refers to the vector transpose.

• 

Continuous, integer, mixed-integer and binary (or zero-one) LPs can be solved. Throughout this page, the term integer programming  is used to represent all forms of integer programs.  Integer programs are specified using the assume, integervariables or binaryvariables options.  See the following Integer Programming Options section for more information.

• 

This help page describes how to specify the problem in Matrix form. For details about the exact format of the objective function and the constraints, see the Optimization/MatrixForm help page. The algebraic form for specifying an LP is described in the Optimization[LPSolve] help page. The Matrix form is more complex, but leads to more efficient computation.

• 

The first parameter c is usually a Vector of objective function coefficients. The dimension, n, of this Vector is taken to be the number of problem variables. However, if you only need a feasible  point, supply the name NoUserValue as the first parameter c followed by constraints and/or bounds. This parameter is required.

  

The second parameter lc is an optional list of linear constraints. The most general form is A,b,Aeq,beq, where A and Aeq are Matrices, and b and beq are Vectors. This parameter can take other forms if either inequality or equality constraints do not exist.  For a full description of how to specify general linear constraints, refer to the Optimization/MatrixForm help page.

  

The third parameter bd is an optional list bl,bu of lower and upper bounds. In general, bl and bu must be n-dimensional Vectors.  The Optimization/MatrixForm help page describes alternate forms that can be used when either bound does not exist and provides more convenient ways of specifying the Vectors. Non-negativity of the variables is not assumed by default, but can be specified using the assume = nonnegative option. When using the interior point method, all variables must be bounded below.

• 

Maple returns the solution as a list containing the final minimum (or maximum) value and a point (the extremum).  If the output = solutionmodule option is provided, then a module is returned.  See the Optimization/Solution help page for more information.

• 

The Optimization[ImportMPS] command can be used to import MPS(X) data files.  This command returns a combined Matrix and Vector representation of the LP that can be sent to the LPSolve command.

General Options

  

The opts argument can contain one or more of the following options. These options apply to all forms of LPs accepted by the LPSolve command and are described in more detail in the Optimization/Options help page.  See the following Integer Programming Options and Continuous Programming Options sections for additional options that only apply to either integer or continuous programs.

• 

assume = nonnegative -- Assume that all variables are non-negative.

• 

feasibilitytolerance = realcons(positive) -- For the active-set method, set the maximum absolute allowable constraint violation. For the interior point method, set the tolerance for the sum of the relative constraint violation and relative duality gap.

• 

infinitebound = realcons(positive) -- For the active-set method, set any value of a variable greater than the infinitebound value to be equivalent to infinity during the computation. This option is ignored when using the interior point method.

• 

initialpoint = Vector --  Use the provided initial point, which is an n-dimensional Vector of numeric values.

• 

iterationlimit = posint -- Set the maximum number of iterations performed by the active-set or interior point algorithm.

• 

maximize or maximize = truefalse -- Maximize the objective function when equal to true and minimize when equal to false.  The option 'maximize' is equivalent to maximize = true. The default is maximize = false.

• 

output = solutionmodule -- Return a module as described in the Optimization/Solution help page.

Integer Programming Options

  

The opts argument can contain one or more of the following options. These options only apply to integer programs and are described in more detail in the Optimization/Options help page.

• 

assume = binary, integer or nonnegint -- Assume all variables take on binary (0 or 1), integer or non-negative integer values.

• 

binaryvariables = list(posint) or set(posint) -- Specify the positions in the Vector of problem variables that only take the values 0 or 1.

• 

depthlimit = posint -- Set the maximum depth of the branch-and-bound tree.

• 

integertolerance = realcons(positive) -- Specify the maximum acceptable absolute violation in a value for it to be considered an integer.

• 

integervariables = list(posint) or set(posint) -- Specify the positions in the Vector of problem variables that only take integer values.

• 

nodelimit = nonnegint -- Set the maximum number of nodes searched in the branch-and-bound tree.  A value of 0 means all nodes are investigated.

Continuous Programming Options

  

The opts argument can contain one or more of the following options. These options only apply to continuous programs and are described in more detail in the Optimization/Options help page.

• 

method = activeset, interiorpoint -- Specify whether to use the active-set or interior point algorithms. If neither method is requested, a heuristic is used to choose the method. In general, the interior point method will be more efficient for large, sparse problems. See the notes below for further details on each algorithm. If the input is given in Matrix form and the constraint matrices have the storage=sparse option set, the interior point method will be used. Otherwise, the heuristic is based on the number of variables, constraints, and the density of the constraint coefficient matrices.

Notes

• 

For continuous programs, the LPSolve command uses one of two methods. The first method is an iterative active-set method implemented in a built-in library provided by the Numerical Algorithms Group (NAG). The second method is a sparse iterative interior point method developed by Dr. H. Wolkowicz at the University of Waterloo and colleagues, based on the following paper:

  

M. Gonzalez-Lima, H. Wei, H. Wolkowicz. "A stable primal-dual approach for linear programming under nondegeneracy assumptions." Computational Optimization and Applications. Vol. 44. (2009): 213-247.

  

For both methods, an initial point can be provided using the initialpoint option. Otherwise, a default point is used.

• 

Integer programs are solved using a branch-and-bound  strategy in which a tree of nodes is created.  Each node corresponds to a continuous LP subproblem which is solved using the active-set method.

• 

The computation is performed in floating-point. Therefore, all data provided must have type realcons and all returned solutions are floating-point, even if the problem is specified with exact values.  For best performance, Vectors and Matrices should be constructed with the datatype = float option, and when using the interior point method, Matrices should also be constructed with the storage = sparse option. For more information about numeric computation in the Optimization package and suggestions on how to obtain the best performance using the Matrix form of input, see the Optimization/Computation help page.

• 

Although parameters lc and bd are optional, LPSolve returns an error if it does not detect at least one constraint (in the form of a general constraint), a bound, or the assume = nonnegative option.

• 

LPSolve returns an error if the problem is infeasible .  If the problem appears to be unbounded , LPSolve issues a warning and returns the last computed result. This result may be meaningless.

• 

Although the assume option is accepted, general assumptions are not supported by commands in the Optimization package.

Examples

withOptimization:

Use LPSolve to minimize a linear function of two variables, subject to 4 inequality constraints.  Aeq and beq can be omitted from the second parameter when there are no equality constraints.

c:=Vector2,1,datatype=float:

A:=Matrix1,1,1,1,1,0,0,1,datatype=float:

b:=Vector3,5,0,0,datatype=float:

LPSolvec,A,b

10.,5.1.1125369292536010-307

(1)

You can use the assume = nonnegative option instead of including non-negative constraints explicitly.

c:=Vector1,1,datatype=float:

A:=Matrix3,1,5,1,datatype=float:

b:=Vector12,2,datatype=float:

LPSolvec,A,b,assume=nonnegative

1.25000000000000,0.1875000000000001.06250000000000

(2)

Bounds can be added separately.  In the following example, there are no other constraints.

c:=Vector2,5,3,datatype=float:

bl:=Vector2,3,1,datatype=float:

bu:=Vector6,10,3.5,datatype=float:

LPSolvec,,bl,bu

7.50000000000000,6.3.3.50000000000000

(3)

Replace A and b in the second parameter by the name NoUserValue when there are only equality constraints.

c:=Vector4,5,datatype=float:

Aeq:=Matrix1,1.5,3,2,datatype=float:

beq:=Vector2,3,datatype=float:

LPSolvec,NoUserValue,NoUserValue,Aeq,beq

5.20000000000000,0.2000000000000001.20000000000000

(4)

Use the maximize option to maximize the objective function.

c:=Vector4,5,datatype=float:

A:=Matrix3,1,5,1,datatype=float:

b:=Vector12,2,datatype=float:

bl:=2.5:

bu:=2.5:

LPSolvec,A,b,bl,bu,maximize

6.06250000000000,0.1875000000000001.06250000000000

(5)

For integer programming problems, you can use the assume = integer option.

c:=Vector1,1,datatype=float:

A:=Matrix1,3,1,0,datatype=float:

b:=Vector1,1,datatype=float:

Optimization[LPSolve]c,A,b,assume=integer

1.,1.0.

(6)

The integervariables option can be used to specify mixed-integer problems.

c:=Vector2,3,5,datatype=float:

A:=Matrix5,4,5,2,5,7,2,3,4,datatype=float:

b:=Vector3,1,2,datatype=float:

Optimization[LPSolve]c,A,b,integervariables=1,3

4.75000000000000,1.0.7500000000000001.

(7)

See Also

examples/OptimizationLPSolve, Optimization, Optimization/AlgebraicForm, Optimization/Computation, Optimization/MatrixForm, Optimization/Options, Optimization/Solution, Optimization[ImportMPS], Optimization[LPSolve], realcons


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam