LpSimplex: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
[[Category:Solvers]] | [[Category:Solvers]] | ||
==Purpose== | ==Purpose== | ||
Line 20: | Line 18: | ||
==Calling Syntax== | ==Calling Syntax== | ||
<syntaxhighlight lang="matlab"> | |||
Result = lpSimplex(Prob) or | Result = lpSimplex(Prob) or | ||
Result = tomRun('lpSimplex', Prob, 1); | Result = tomRun('lpSimplex', Prob, 1); | ||
</syntaxhighlight> | |||
== | ==Inputs== | ||
{| | {| class="wikitable" | ||
|''Prob''||colspan="2"|Problem description structure. The following fields are used: | |''Prob''||colspan="2"|Problem description structure. The following fields are used: | ||
|- | |- | ||
Line 42: | Line 41: | ||
|- | |- | ||
|||''x_0''||Starting point. | |||''x_0''||Starting point. | ||
|- | |-valign="top" | ||
|||''Solver.Alg''||Variable selection rule to be used: | |||''Solver.Alg''||Variable selection rule to be used: | ||
0: Minimum reduced cost. | |||
1: Bland's rule (default). | |||
2: Minimum reduced cost. Dantzig's rule. | |||
|- | |-valign="top" | ||
|||''QP.B''||Active set ''B 0 ''at start: | |||''QP.B''||Active set ''B 0 ''at start: | ||
''B''(''i'') = 1: Include variable ''x''(''i'') is in basic set. | |||
''B''(''i'') = 0: Variable ''x''(''i'') is set on its lower bound. | |||
''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on its upper bound. | |||
|-valign="top" | |-valign="top" | ||
|||||Fields used are: ''MaxIter'', ''PriLev'', ''wait'', ''eps_f'', ''eps_Rank'', ''xTol ''and ''bTol''. | |||''optParam''||Structure with special fields for optimization parameters, see [[TOMLAB Appendix A]]. | ||
Fields used are: ''MaxIter'', ''PriLev'', ''wait'', ''eps_f'', ''eps_Rank'', ''xTol ''and ''bTol''. | |||
|} | |} | ||
== | ==Outputs== | ||
{| | {| class="wikitable" | ||
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed: | |''Result''||colspan="2"|Structure with result from optimization. The following fields are changed: | ||
|- | |- | ||
Line 82: | Line 81: | ||
|- | |- | ||
|||''xState''||State of each variable, described in Table 150. | |||''xState''||State of each variable, described in Table 150. | ||
|- | |-valign="top" | ||
|||''ExitFlag''||0: Optimal solution found. | |||''ExitFlag''||0: Optimal solution found. | ||
1: Maximal number of iterations reached. | |||
2: Unbounded feasible region. | |||
5: Too many active variables in given initial point. | |||
6: No feasible point found with Phase 1. | |||
10: Errors in input parameters. | |||
11: Illegal initial x as input. | |||
|- | |- | ||
|||''Inform''||If ''ExitF lag > ''0, ''Inform ''= ''ExitF lag''. | |||
|||''Inform''||If ''ExitF lag > ''0, '' | |||
|- | |- | ||
|||''QP.B''||Optimal active set. See input variable ''QP.B''. | |||''QP.B''||Optimal active set. See input variable ''QP.B''. | ||
Line 107: | Line 106: | ||
|||''Iter''||Number of iterations. | |||''Iter''||Number of iterations. | ||
|-valign="top" | |-valign="top" | ||
|||''FuncEv''||Number of function evaluations. Equal to ''Iter''. ''ConstrEv ''Number of constraint evaluations. Equal to ''Iter''. | |||''FuncEv''||Number of function evaluations. Equal to ''Iter''. | ||
|- | |||
|''ConstrEv''||Number of constraint evaluations. Equal to ''Iter''. | |||
|- | |- | ||
|||''Prob''||Problem structure used. | |||''Prob''||Problem structure used. |
Revision as of 09:37, 20 July 2011
Purpose
Solve general linear programming problems.
lpSimplex solves problems of the form
where Failed to parse (unknown function "\MATHSET"): {\displaystyle x,x_{L},x_{U}\in \MATHSET{R} ^{n}}
, Failed to parse (unknown function "\MATHSET"): {\displaystyle c \in \MATHSET{R}^{n}}
, Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\in \MATHSET{R}^{m\times n}}
and Failed to parse (unknown function "\MATHSET"): {\displaystyle $b_{L},b_{U} \in \MATHSET{R}^{m}$}
.
Calling Syntax
Result = lpSimplex(Prob) or
Result = tomRun('lpSimplex', Prob, 1);
Inputs
Prob | Problem description structure. The following fields are used: | |
QP.c | Constant vector. | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. | |
b_U | Upper bounds on the linear constraints. | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
Solver.Alg | Variable selection rule to be used:
0: Minimum reduced cost. 1: Bland's rule (default). 2: Minimum reduced cost. Dantzig's rule. | |
QP.B | Active set B 0 at start:
B(i) = 1: Include variable x(i) is in basic set. B(i) = 0: Variable x(i) is set on its lower bound. B(i) = -1: Variable x(i) is set on its upper bound. | |
optParam | Structure with special fields for optimization parameters, see TOMLAB Appendix A.
Fields used are: MaxIter, PriLev, wait, eps_f, eps_Rank, xTol and bTol. |
Outputs
Result | Structure with result from optimization. The following fields are changed: | |
x_k | Optimal point. | |
f_k | Function value at optimum. | |
g_k | Gradient value at optimum, c. | |
v_k | Lagrange multipliers. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
xState | State of each variable, described in Table 150. | |
ExitFlag | 0: Optimal solution found.
1: Maximal number of iterations reached. 2: Unbounded feasible region. 5: Too many active variables in given initial point. 6: No feasible point found with Phase 1. 10: Errors in input parameters. 11: Illegal initial x as input. | |
Inform | If ExitF lag > 0, Inform = ExitF lag. | |
QP.B | Optimal active set. See input variable QP.B. | |
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Iter | Number of iterations. | |
FuncEv | Number of function evaluations. Equal to Iter. | |
ConstrEv | Number of constraint evaluations. Equal to Iter. | |
Prob | Problem structure used. |
Description
The routine lpSimplex implements an active set strategy (Simplex method) for Linear Programming using an additional set of slack variables for the linear constraints. If the given starting point is not feasible then a Phase I objective is used until a feasible point is found.
M-files Used
ResultDef.m