Problem is unbounded with linprong

f=[8 4 -2 6 12]

f = 1×5

8 4 -2 6 12

b=[6;8;12;24;40]

b = 5×1

6 8 12 24 40

A=[6 4 -1 8 -24;-4 8 6 -2 12;30 9 -12 16 -36;16 -3 2 4 6;24 6 3 2 -12]

A = 5×5

6 4 -1 8 -24 -4 8 6 -2 12 30 9 -12 16 -36 16 -3 2 4 6 24 6 3 2 -12

linprog(f,A,b)

Problem is unbounded.


ans =

     []

[Torsten]

If linprog reports your problem is unbounded, I believe in the software.

[Sukapak]

How to solve it

Answer 1

[Torsten]

You solved it - f can be made as small as you like. That's what "Problem is unbounded" means.

Answer 2

[John D'Errico]

Unbounded means what it sounds like. We can move in SOME direction, making the objective as small as we wish. I.e., as close to minus infinity as you wish to go. Even though you provide inequality constraints, you can still move without constraint in some direction. Can we identify what such a direction might be?

f=[8 4 -2 6 12]

f = 1×5

8 4 -2 6 12

b=[6;8;12;24;40]

b = 5×1

6 8 12 24 40

A=[6 4 -1 8 -24;-4 8 6 -2 12;30 9 -12 16 -36;16 -3 2 4 6;24 6 3 2 -12]

A = 5×5

6 4 -1 8 -24 -4 8 6 -2 12 30 9 -12 16 -36 16 -3 2 4 6 24 6 3 2 -12

linprog(f,A,b)

Problem is unbounded.


ans =

     []

A even has full rank. But that does not mean the mere inequality constraints are sufficient to bound the problem. You have no bound constraints at all.

rank(A)

ans = 5

Can we find a direction, in which the LP is unbounded? Yes. I'll just generate a large set of random vectors, all of which cause a decrease in the objective. (This is a very lazy method.)

X = randn(5,1000);
X = X.*sign(-f*X); % Force them all to point in a direction that will decrease the objective
ind = find(all(A*X<b,1)); % find all such vectors that are feasible
X = mean(X(:,ind),2) % and then take the mean

X = 5×1

-0.6085 -0.7355 -0.1298 -0.5920 -0.0813

A*(1000*X) <= b

ans = 5×1 logical array
   1
   1
   1
   1
   1

format long g
f*[X,1000*X,1e6*X]

ans = 1×3

1.0e+00 * -12.0781671033879 -12078.1671033879 -12078167.1033879

So I can go as far out in that direction as I wish, making the objective as close to -inf as I wish.

Again, this is an extremely lazy method. No thought was required at all.

Answer 3

[Walter Roberson]

The constraints are used as A*x <= b. The boundary condition would be A*x = b which you could solve with A\b.

But if A*x <= b then can we solve the boundary A*x = b-[0;100;0;0;0]? for example if A(2,:)*x = -92 then that would satisfy A(2,:)*x <= 8 right? Can we get a consistent solution with the modified boundary conditions? If course we can, we just use A\modified b to get the modified x. Then we ask, f*unmodified < f*modified? That is, are the original boundaries the ones that give minimal output? No, the modified boundary gives a more minimal output. And since the system is linear, we can reduce the output arbitrarily.

[Walter Roberson]

syms c [5 1]
out = f*(A\(b-c))

You will get

(11806*c1)/27307 - (3295*c2)/3901 - (16032*c3)/27307 - (21072*c4)/27307 + (18190*c5)/27307 + 12028/3901

which tells us that by making c2 or c3 or c4 arbitrary positive values the outcome can be reduced arbitrarily. Making them positive corresponds to reducing the b value in the corresponding position, making it in some sense more difficult to satisfy... but in so doing the outcome decreases so the optimization is unbounded.

[Walter Roberson]

Now if you require nonnegative x there might be a solution.

[Walter Roberson]

Unfortunately the details of how it determines the problem is unbounded are hidden in toolbox/optim/+optim/+algorithm/LinprogDualSimplex.p