TOMLAB OPTIMIZATION ENVIRONMENT: lpSolve
|
TOMLAB OPTIMIZATION ENVIRONMENT: lpSolve |
|
lpSolve
Purpose
For solving general linear programming problems.
Syntax
Result = lpSolve(Prob);
Description
Active set strategy (Simplex method) for Linear Programming.
Problem
min c' * x. x in R^n
x
s/t x_L <= x <= x_U
b_L <= A x <= b_U
Equality equations: Set b_L(i)==b_U(i), for the ith equation
Fixed variables: Set x_L(i)==x_U(i), for the ith variable
Solves Phase 1 problem (find feasible point) if c is empty
Input Parameters
Fields in Prob:
c: The vector c in c'x. If isempty(c), only solve Phase1 problem,
finding a feasible point for the constraints
A: The linear constraint matrix
b_L: The lower bounds for the linear constraints
b_U: The upper bounds for the linear constraints
x_L: Lower bounds on x. If empty assumed to be 0.
x_U: Upper bounds on x. If empty assumed to be Inf.
b_L, b_U, x_L, x_U must either be empty or of full length
x_0: Starting point x
PriLevOpt Printing level:
=0 No output; >0 Convergence results;
>1 Output every iteration of function value
>2 Output every iteration of change of basis
>3 Output every iteration of more information (scalar values)
>4 Output every iteration of more information including vectors
QP.B: Active set B_0 at start.
2 = Fixed variables x(i)
1 = Include variable x(i) is in basic set.
0 = Variable x(i) is set on its lower bound
-1 = Variable x(i) is set on its upper bound
If EMPTY, lpSolve finds the active set.
Warm Start basis variables:
Prob.QP.UseHot If > 0, Uses a warm start basis, either from file or from
the structure Prob
Prob.QP.HotFile If nonempty, a warm start basis are read from this file
If Prob.QP.HotFileis empty, read warm start basis from structure Prob:
x = Prob.QP.Hot.x; B = Prob.QP.Hot.B;
Q = Prob.QP.Hot.Q; R = Prob.QP.Hot.R; E = Prob.QP.Hot.E;
Prob.QP.HotFreq If > 0, a basis are saved, on a file
HotLPxxx. xxx is a number (modulo counter).
Prob.QP.HotN The number of warm start basis files, xxx=mod(Freq,HotN),
where xxx is a number from 0 to HotN-1
----------------------------------------------
Prob.Solver.Alg Rule to select new variables:
= 0 Minimum Reduced Cost, sort variables increasing. (DEFAULT)
= 1 Bland's Anti-cycling Rule
= 2 Minimum Reduced Cost, Dantzig's rule
Fields used in Prob.optParam:
wait Wait flag, pause each iteration if set true MaxIter Maximal number of iterations. max(10*dim(x),100) is DEFAULT. eps_f Tolerance used to test convergence on the reduced costs eps_Rank Rank tolerance used to test convergence on the reduced costs xTol Tolerance to judge if x-values are close bTol Feasibility tolerance for linear constraints
Output Parameters
Structure Result. Fields used:
Iter Number of iterations
ExitFlag Exit flag
== 0 => OK
== 1 => Maximal number of iterations reached. No bfs found.
== 2 => Unbounded feasible region.
== 3 => Rank problems (NOT USED)
== 4 => No feasible point found with Phase1
== 10 => Errors in input parameters
ExitTest Text string giving ExitFlag and Inform information
Inform Not used, always empty
x_k Solution
v_k Lagrange parameters.
First n values corresponds to either lower or upper bounds.
The rest of the values corresponds to the linear constraints
QP.B B Optimal set. B(i)==0, include variable x(i) in basic set.
sum(B==0)==length(b_U) holds. See QP.B as input.
p_dx Search steps in x
alphaV Step lengths for each search step
f_k Function value c'*x
g_k Gradient, = c
Solver lpSolve
SolverAlgorithm Description of method used
x_0 Starting point x_0
xState State variable: Free==0; On lower == 1; On upper == 2; Fixed == 3;
|
L1Solve | lsei | |