DualSolve
Purpose
Solve linear programming problems when a dual feasible solution is available.
DualSolve solves problems of the form
where , , and .
Finite upper bounds on x are added as extra inequality constraints. Finite nonzero lower bounds on x are added as extra inequality constraints. Fixed variables are treated explicitly. Adding slack variables and making necessary sign changes gives the problem in the standard form
and the following dual problem is solved,
with , and .
Calling Syntax
[Result] = DualSolve(Prob)
Description of 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, must be dual feasible. | |
y_0 | Dual parameters (Lagrangian multipliers) at x _0. | |
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. | |
Solver.Alg | Variable selection rule to be used:
0: Minimum reduced cost (default). 1: Bland's anti-cycling rule. 2: Minimum reduced cost. Dantzig's rule. | |
PriLevOpt | Print Level. | |
optParam | Structure with special fields for optimization parameters, see TOMLAB Appendix A.
Fields used are: MaxIter, wait, eps_f, eps_Rank and xTol. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
---|---|---|
x_k | Optimal primal solution x. | |
f_k | Function value at optimum. | |
v_k | Optimal dual parameters. Lagrange multipliers for linear constraints. | |
x_0 | Starting point. | |
Iter | Number of iterations. | |
QP.B | Optimal active set. | |
ExitFlag | Exit flag:
0: Optimal solution found. 1: Maximal number of iterations reached. No primal feasible solution found. 2: Infeasible Dual problem. 4: Illegal step length due to numerical difficulties. Should not occur. 6: No dual feasible starting point found. 7: Illegal step length due to numerical difficulties. 8: Convergence because fk >= QP.DualLimit. 9: xL(i) > xU(i) + xTol for some i. No solution exists. | |
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
c | Constant vector in standard form formulation. | |
A | Constraint matrix for linear constraints in standard form. | |
b | Right hand side in standard form. |
Description
When a dual feasible solution is available, the dual simplex method is possible to use. There are three rules available for variable selection. Bland's cycling prevention rule is the choice if fear of cycling exist. The other two are variants of minimum reduced cost variable selection, the original Dantzig's rule and one which sorts the variables in increasing order in each step (the default choice).
M-files Used
cpTransf.m