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:
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!
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.