Finding vertices of (large) linear program feasible region

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!

[Matt J]

Are you sure the min/maximal points are unique on each axis? What if the feasible region is the positive orthant? The maximizing points along x would then be the entire positive y-axis and vice versa.

[Daniel]

Thanks, Matt, I should have been clearer: I know that the feasible region I am considering is bounded. Yes, it is possible that one of the constraints is parallel to an axis so that a maximal value along that axis is achieved along the entire boundary between two vertices, so that uniqueness is not given. However, having the two vertices would also tell me what this value is, and that's sufficient for me.

Answer 1

[Teja Muppirala]

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.