function [flag,x,y,C,E]=verlinprogg(A,b,c) % refers to AT
%    VERLINPROGG       Verified linear programming.
%    This is an INTLAB file. It requires to have INTLAB installed under
%    MATLAB to function properly.
%    For a real matrix A (full or sparse) and matching real vectors b, c,
%        [flag,x,y,C,E]=verlinprogg(A,b,c)
%    either computes verified optimal solution x, verified dual optimal solution y
%    and verified optimal value C.h of the linear programming problem
%        min c'*x   subject to   A*x=b, x>=0,
%    or verifies (in)feasibility, or verifies unboundedness, or yields no
%    verified result. The respective outcome is always described verbally
%    in the variable flag.
%    Possible outputs:
%    flag='verified optimum   ' : x is verified to enclose a primal optimal solution,
%                                 y is verified to enclose a dual optimal solution,
%                                 C.h is verified to enclose the optimal value,
%                                 C.B is the set of indices of the basic variables,
%                                 C.N is the set of indices of the nonbasic variables,
%                                 C.crit is the final criterial row,
%    flag='verified unbounded ' : x is verified to enclose a primal feasible solution xo, and
%                                 y is verified to enclose a vector yo such that the objective
%                                   tends to -Inf along the feasible half-line {xo+t*yo | t>=0},
%                                 C fields consist of NaN's,
%    flag='verified feasible  ' : x is verified to enclose a primal feasible solution
%                                   (optimality nor unboundedness could be verified),
%                                 y and C are of NaN's,
%    flag='verified infeasible' : y is verified to enclose a Farkas vector yo satisfying A'*yo>=0, b'*yo<0
%                                   (whose existence proves primal infeasibility),
%                                 x and C are of NaN's,
%    flag='no verified result ' : x, y and C are all of NaN's
%                                   (no verified result could be found),
%    flag='sizes do not match ' : x, y and C are all of NaN's
%                                   (sizes of A, b, c do not match).
%    The structured array E explains reasons for NaN output. It has three fields:
%    E.error, E.where, E.value.

%    Copyright 2007-2008 Jiri Rohn
%    A part of this work (nondegenerate solutions) was supported by the
%    Czech Republic National Research Program "Information Society",
%    project 1ET400300415. The second part (degenerate solutions) was done
%    during author's employment at the Anglo-American University in Prague,
%    Czech Republic.
%    Because the program is licensed free of charge, there is
%    no warranty for the program, to the extent permitted by applicable
%    law. Except when otherwise stated in writing the copyright holder
%    and/or other parties provide the program "as is" without warranty
%    of any kind, either expressed or implied, including, but not
%    limited to, the implied warranties of merchantability and fitness
%    for a particular purpose. The entire risk as to the quality and
%    performance of the program is with you. Should the program prove
%    defective, you assume the cost of all necessary servicing, repair
%    or correction.
%    History
%    2007, Spring first working version created
%    2007-05-31   first posted as VERLINPROG; handles nondegenerate solutions only
%    2008-09-10   started again
%    2008-09-11   degenerate solutions handled via new VEROPT using VERSOL
%    2008-10-08   output structured array C created, Xopt added into it (subfunction optsolset)
%    2008-10-11   optsolset included into main file
%    2008-11-08   output of C.Xopt suppressed
%    2008-11-09   C's fields explained in the help
%    2008-11-28   input variable d and all the messages added
%    2008-11-29   AT called by vverlinprog; AT p-coded
%    2008-12-16   d dropped; renamed as verlinprogg; final version (html)
[flag,x,y,C,E]=at(A,b,c); % computation done by AT