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 (me + md) x n) (If no constraints are given, you can set C = [])
• b : RHS column vector (dimension (me + md)) (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))
• 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 + me + md components and lagr(1:n) is the Lagrange vector associated with the bound constraints and lagr (n+1 : n + me + md) 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 me + md components.

Description

Minimize p'*x under the constraints C*x <= b

Minimize p'*x under the constraints C*x <= b , ci <= x <= cs

Minimize p'*x under the constraints

 C(j,:) x = b(j),  j=1,...,me
 C(j,:) x <= b(j), j=me+1,...,me+md
 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  

Author

E. Casas, C. Pola Mendez;