TOMLAB OPTIMIZATION ENVIRONMENT: DualSolve

DualSolve

Purpose

For solving linear programming problems when a dual feasible solution is available.

Syntax

   Result = DualSolve(Prob);

Description

Given LP on the standard form, but with general lower and upper bounds:

        min c' * x , A x = b_U, x_L <= x <= x_U

Solve dual LP:

        max  b'*y, subject to  A'*y <= c, y urs

Upper bounds (not Inf) are added as extra linear constraints in A.
Lower bounds (not zero) are added as extra linear constraints in A.
Fixed variables are treated explicitely.

Note that the TOMLAB routine cpTransf.m can be used to rewrite an LP problem on another form to this standard form

Implementation of algorithm Dual simplex method, Handbooks in Operations Research and Management Science, ChapterII: Goldfarb and Todd: Linear Programming, pages 105-106

Generalized with QR factorization, and numerical safeguarding

Input Parameters

In the Prob structure use:

 x_L  Lower bound on x. 
           Assumed to be 0, if not Prob.x_L(i) == Prob.x_U(i) (fixed vars)
 x_U  Upper bound on x. 

 b_L  Lower bound on linear constraints. Not used.
 b_U  Upper bounds, Assume equality constraints Ax == b_U

 A,b_U,c   A in R^(m x n). b_U in R^m. x in R^n.

 x_0  Starting value x_0

 QP.B Active set B at start. 
           1  = Include variable x(i) is in basic set.
           0  = Variable x(i) is set on its lower bound 0
           -1 = Variable x(i) is set on its upper bound (NOT ALLOWED)

 QP.y Dual variables y (Lagrange multipliers for linear constraints)

 Starting value set {x_0,B,y} is given in the following three ways:

 {x_0,B,y} All defined

 {x_0,B}   Estimate y from A(:,iB)'y=c(iB), where basis iB=find(B==1)

 {B}       x_0 is estimated from A(:,iB) x = b_U. y from A(:,iB)'y=c(iB)

 Prob.Solver.Alg  Rule to select new variables:
           = 0 Minimum Reduced Cost (DEFAULT), sort variables increasing. 
           = 1 Bland's Anti-cycling Rule     
           = 2 Minimum Reduced Cost, Dantzig's rule 

 PriLevOpt Printing level:
           =0 No output; >0 Convergence results; 
           >1 Output every iteration  >2 Output each step in the simplex alg

 Fields used in Prob.optParam
 
 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 
 xTol      Tolerance to judge if x-values are close
 bTol      Tolerance for linear constraints
 wait      Wait flag, pause each iteration if set true

Output Parameters

Result structure with the following fields defined:

 Field Internal 
 name  name
 x_k    x     Primal solution x
 y_k    y     Dual solution y. Lagrangian multipliers for the linear constraints
 QP.B   B     Optimal set. See QP.B as INPUT.
 QP.DualLimit Limit value for b'*y. If b'y >= QP.DualLimit, Stop.
 ExitFlag     Exit flag 
              == 0  => OK
              == 1  => Maximal number of iterations reached. No bfs found. 
              == 2  => Infeasible dual problem
              == 5  => Too many active variables in initial point given.
              == 6  => No dual feasible starting point found.
              == 7  => Illegal step length due to numerical difficulties.
                       Should not occur.
              == 8  => Convergence when f_k >= QP.DualLimit. No further
                       progress is wanted. Used by MIP codes.
              == 9  => x_L(i) > x_U(i) + xTol for some i. No solution exists
 ExitTest     Text string giving ExitFlag and Inform information
             
              Some reduced cost is negative.
 f_k          f_hat=b'y at optimum y (or last iterate y if no convergence)
 A            Matrix A in standard LP formulation. 
 b            Vector b in standard LP formulation. 
 c            Vector c in standard LP formulation. 

cutplane

expSolve