Scilab Function
Last update : 18/05/2014
linpro - linear programming solver
Calling Sequence
- [x,lagr,f]=linpro(p,C,b [,x0])
- [x,lagr,f]=linpro(p,C,b,ci,cs [,x0])
- [x,lagr,f]=linpro(p,C,b,ci,cs,me [,x0])
- [x,lagr,f]=linpro(p,C,b,ci,cs,me,x0 [,imp])
Parameters
-
p: real column vector (dimension n)
-
C: real matrix (dimension m x n)
(If no constraints are given, you can set C =
[])
-
b: RHS column vector (dimension m)
(If no constraints are given, you can set b =
[])
-
ci: column vector of lower-bounds (dimension
n). If there are no lower bound constraints, put
ci = []. If some components of x
are bounded from below, set the other (unconstrained) values
of ci to a very large negative number
(e.g. ci(j) = -number_properties('huge').
-
cs: column vector of upper-bounds. (Same remarks as above).
-
me: number of equality constraints (i.e. C(1:me,:)*x = b(1:me)) with me <=m.
-
x0: either an initial guess for x or one of
the character strings 'v' or
'g'. If x0='v' the calculated
initial feasible point is a vertex. If x0='g'
the calculated initial feasible point is arbitrary.
-
imp: verbose option (optional parameter) (Try
imp=7,8,...) warning the message are output in
the window where scilab has been started.
-
x: optimal solution found.
-
f: optimal value of the cost function (i.e. f=p'*x).
-
lagr: vector of Lagrange multipliers. If lower and
upper-bounds ci,cs are provided,
lagr has n + m components and
lagr(1:n) is the Lagrange vector associated
with the bound constraints and lagr (n+1 : n +
m) is the Lagrange vector associated with the linear
constraints. (If an upper-bound (resp. lower-bound)
constraint i is active lagr(i) is
> 0 (resp. <0). If no bounds are provided,
lagr has only m components.
Description
[x,lagr,f]=linpro(p,C,b [,x0]) Minimize
p'*x under the constraints C*x <=
b
[x,lagr,f]=linpro(p,C,b,ci,cs [,x0]) Minimize
p'*x under the constraints C*x <= b,
ci <= x <= cs
[x,lagr,f]=linpro(p,C,b,ci,cs,me [,x0]) Minimize
p'*x under the constraints
C(j,:) x = b(j), j=1,...,me
C(j,:) x <= b(j), j=me+1,...,m
ci <= x <= cs
If no initial point is given the
program computes a feasible initial point
which is a vertex of the region of feasible points if
x0='v'.
If x0='g', the program computes a feasible initial
point which is not necessarily a vertex. This mode is
advisable when the quadratic form is positive
definite and there are a few constraints in
the problem or when there are large bounds
on the variables that are security bounds and
very likely not active at the optimal solution.
Examples
//Find x in R^6 such that:
// C1*x = b1 (3 equality constraints i.e me=3)
C1= [1,-1,1,0,3,1;
-1,0,-3,-4,5,6;
2,5,3,0,1,0];
b1=[1;2;3];
//C2*x <= b2 (2 inequality constraints)
C2=[0,1,0,1,2,-1;
-1,0,2,1,1,0];
b2=[-1;2.5];
//with x between ci and cs:
ci=[-1000;-10000;0;-1000;-1000;-1000];cs=[10000;100;1.5;100;100;1000];
//and minimize p'*x with
p=[1;2;3;4;5;6]
//No initial point is given: x0='v';
C=[C1;C2]; b=[b1;b2] ; me=3; x0='v';
[x,lagr,f]=linpro(p,C,b,ci,cs,me,x0)
// Lower bound constraints 3 and 4 are active and upper bound
// constraint 5 is active --> lagr(3:4) < 0 and lagr(5) > 0.
// Linear (equality) constraints 1 to 3 are active --> lagr(7:9) <> 0
See Also
quapro,
Authors
-
Eduardo Casas Renteria, Universidad de Cantabria,
-
Cecilia Pola Mendez , Universidad de Cantabria
Bibliography
E. Casas and C. Pola, An algorithm for indefinite quadratic
programming based on a partial Cholesky factorization, RAIRO-Recherche
Opérationnelle/Operations Research, 27 (1993), 401-426. Used Function
in routines/optim directory (authors E.Casas, C. Pola Mendez):
anfm01.f anfm03.f anfm05.f anrs01.f auxo01.f dimp03.f dnrm0.f optr03.f pasr03.f zthz.f
anfm02.f anfm04.f anfm06.f anrs02.f desr03.f dipvtf.f optr01.f
opvf03.f plcbas.f
From BLAS library
daxpy.f dcopy.f ddot.f dnrm2.f dscal.f dswap.f idamax.f
in routines/calelm directory (authors INRIA):
add.f ddif.f dmmul.f
From LAPACK library : dlamch.f