MATLAB: Finding vertices of (large) linear program feasible region

cornersextreme pointsfeasible regionlcon2vertlinear programlinoptlinprogpolyhedralsparsitySymbolic Math Toolboxvertices

I have a linear program with equality and inequality constraints, which I solve using linprog. I am interested in the feasible region.
How do I find the minimal and maximal points of an LP feasible region along each axis?
Finding instead the corners/vertices/extreme points of the feasible region — as stated in the title — would also be fine, since I can get the minimal/maximal points from this. This would amount to finding all basic feasible solutions of the LP.
linopt::corners in the symbolic toolbox does this, but all constraints need to be entered by hand, and I have potentially hundreds (or thousands) of them, which are, however, sparse. Is there a good tool which allows me to enter the constraints the same way as in linprog?
One option is to use, for each axis, a linear program with the same constraints and then use as objective function the value of the variable corresponding to that axis. This would not necessarily get me all the vertices, but the minimal/maximal points I am interested in directly. However, doing this separately for each axis is slow, and there may be faster ways that save on the overhead.
I have thus far found Matt J's command lcon2vert:
http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities/content/lcon2vert.m
I wonder, however, whether there are faster options if I'm not interested in the vertices per se, but rather the minimal/maximal points of the feasible region along each axis.
Thanks in advance for any suggestions!

Best Answer

For the k-th direction, the set of possible edge points is b./A(:,k) along with +/-Inf. So test each one in order to see if it is feasible.
Nc = 30; %Number of constraints
Nd = 10; %Number of variables
rng(0)
A = randn(Nc,Nd); %Making random data
b = rand(Nc,1);
tol = 1e-12;
nvars = size(A,2);
xminmax = nan(nvars,2);
for k = 1:size(A,2)
    thisA = A(:,k);
      xc = [-inf; inf; b./thisA];
      % Remove NaNs (0/0) and sort it in ascending order.
      xc = sort(xc(~isnan(xc)));
      xmin = nan;
      for n = 1:numel(xc)
          Ax = thisA*xc(n);
          Ax(isnan(Ax)) = 0;
          if all(Ax - b < tol)
              xmin = xc(n);
              break
          end;
      end;
      xmax = nan;
      xc = xc(end:-1:1);
      for n = 1:numel(xc)
          Ax = thisA*xc(n);
          Ax(isnan(Ax)) = 0;
          if all(Ax - b < tol);
              isgood = 1;
              xmax = xc(n);
              break;
          end;
      end;
      xminmax(k,:) = [xmin xmax];
  end
  xminmax %<-- The minimum and maximum values for each axis.
Just for a sanity check, verify what you get with what you would get by doing it using LINPROG.
xminmaxLP = zeros(nvars,2);
for k = 1:nvars
xminmaxLP(k,:) = [linprog(1,A(:,k),b) linprog(-1,A(:,k),b)];
end
xminmaxLP
Indeed, you get the same thing.
Related Question