Optimization Toolbox

Linear Programming with Dense Columns in the Equalities

The problem is

and you can load the matrices and vectors Aeq, beq, f, lb, and ub into the MATLAB workspace with

• load densecolumns
  

The problem in densecolumns.mat has 1677 variables and 627 equalities with lower bounds on all the variables, and upper bounds on 399 of the variables. The equality matrix Aeq has dense columns among its first 25 columns, which is easy to see with a spy plot:

• spy(Aeq)
  
  
  

You can use linprog to solve the problem:

• [x,fval,exitflag,output] = ...
    linprog(f,[],[],Aeq,beq,lb,ub,[],optimset('Display','iter'));
  

Because the iterative display was set using optimset, the results displayed are

• Residuals:  Primal      Dual      Upper     Duality     Total
              Infeas     Infeas     Bounds      Gap        Rel
              A*x-b    A'*y+z-w-f  {x}+s-ub   x'*z+s'*w   Error
  ---------------------------------------------------------------
  Iter  0:  1.67e+003  8.11e+002  1.35e+003  5.30e+006  2.92e+001
  Iter  1:  1.37e+002  1.33e+002  1.11e+002  1.27e+006  2.48e+000
  Iter  2:  3.56e+001  2.38e+001  2.89e+001  3.42e+005  1.99e+000
  Iter  3:  4.86e+000  8.88e+000  3.94e+000  1.40e+005  1.89e+000
  Iter  4:  4.24e-001  5.89e-001  3.44e-001  1.91e+004  8.41e-001
  Iter  5:  1.23e-001  2.02e-001  9.97e-002  8.41e+003  5.79e-001
  Iter  6:  3.98e-002  7.91e-002  3.23e-002  4.05e+003  3.52e-001
  Iter  7:  7.25e-003  3.83e-002  5.88e-003  1.85e+003  1.85e-001
  Iter  8:  1.47e-003  1.34e-002  1.19e-003  8.12e+002  8.52e-002
  Iter  9:  2.52e-004  3.39e-003  2.04e-004  2.78e+002  2.99e-002
  Iter 10:  3.46e-005  1.08e-003  2.81e-005  1.09e+002  1.18e-002
  Iter 11:  6.95e-007  1.53e-012  5.64e-007  1.48e+001  1.62e-003
  Iter 12:  1.04e-006  2.26e-012  3.18e-008  8.32e-001  9.09e-005
  Iter 13:  3.08e-006  1.23e-012  3.86e-009  7.26e-002  7.94e-006
  Iter 14:  3.75e-007  1.09e-012  6.53e-012  1.11e-003  1.21e-007
  Iter 15:  5.21e-008  1.30e-012  3.27e-013  8.62e-008  9.15e-010
  
  Optimization terminated successfully.
  

You can see the returned values of exitflag, fval, and output:

• exitflag =
       1
  fval =
    9.1464e+003
  output = 
        iterations: 15
      cgiterations: 225
         algorithm: 'lipsol'
  

This time the number of PCG iterations (in output.cgiterations) is nonzero because the dense columns in Aeq are detected. Instead of using a sparse Cholesky factorization, linprog tries to use the Sherman-Morrison formula to solve a linear system involving Aeq*Aeq'. If the Sherman-Morrison formula does not give a satisfactory residual, a PCG iteration is used. See the Main Algorithm section in Large-Scale Linear Programming.

Linear Programming with Equalities and Inequalities

Default Parameter Settings