Linear Programming Examples

On this page…
Example: Linear Programming with Equalities and Inequalities Example: Linear Programming with Dense Columns in the Equalities

Example: Linear Programming with Equalities and Inequalities

The problem is

You can load the matrices and vectors A, Aeq, b, beq, f, and the lower bounds lb into the MATLAB workspace with

load sc50b

This problem in sc50b.mat has 48 variables, 30 inequalities, and 20 equalities.

You can use linprog to solve the problem:

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

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

  Residuals:   Primal     Dual     Duality    Total
               Infeas    Infeas      Gap       Rel
               A*x-b    A'*y+z-f    x'*z      Error
  ---------------------------------------------------
  Iter    0:  1.50e+003 2.19e+001 1.91e+004 1.00e+002
  Iter    1:  1.15e+002 2.37e-015 3.62e+003 9.90e-001
  Iter    2:  1.61e-012 2.62e-015 4.32e+002 9.48e-001
  Iter    3:  3.11e-012 4.26e-015 7.78e+001 6.88e-001
  Iter    4:  4.75e-011 6.01e-016 2.38e+001 2.69e-001
  Iter    5:  3.65e-010 4.97e-016 5.05e+000 6.89e-002
  Iter    6:  3.09e-011 2.18e-016 1.64e-001 2.34e-003
  Iter    7:  1.77e-012 1.56e-016 1.09e-005 1.55e-007
  Iter    8:  1.30e-012 1.50e-016 1.09e-011 1.55e-013
Optimization terminated.

For this problem, the large-scale linear programming algorithm quickly reduces the scaled residuals below the default tolerance of 1e-08.

The exitflag value is positive, telling you linprog converged. You can also get the final function value in fval and the number of iterations in output.iterations:

exitflag =
     1
fval =
 -70.0000
output = 
         iterations: 8
          algorithm: 'large-scale: interior point'
       cgiterations: 0
            message: 'Optimization terminated.'
    constrviolation: 6.8212e-013
      firstorderopt: 2.7908e-013

Back to Top

Example: Linear Programming with Dense Columns in the Equalities

The problem is

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.96e-007 3.00e-012 5.64e-007 1.48e+001 1.62e-003
  Iter   12:  7.00e-007 2.44e-012 3.18e-008 8.32e-001 9.09e-005
  Iter   13:  8.50e-008 1.07e-012 3.86e-009 7.26e-002 7.94e-006
  Iter   14:  1.44e-010 1.25e-012 6.53e-012 1.11e-003 1.21e-007
  Iter   15:  7.59e-014 2.50e-012 3.72e-013 8.62e-008 9.42e-012
Optimization terminated.

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

exitflag,fval,output

exitflag =
     1

fval =
  9.1464e+003

output = 
         iterations: 15
          algorithm: 'large-scale: interior point'
       cgiterations: 0
            message: 'Optimization terminated.'
    constrviolation: 4.4587e-013
      firstorderopt: 5.0368e-009

This time the algorithm detects dense columns in Aeq. Therefore, 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, the algorithm uses a solution process based on LDL factorization. See Main Algorithm.

Back to Top

Linear Programming Algorithms

Quadratic Programming Algorithms

© 1984-2012- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS