Problem is unbounded with linprog

the code is

x=optimvar('x','LowerBound',0);
y=optimvar('y','LowerBound',0);
z=optimvar('z','LowerBound',0);
w=optimvar('w','LowerBound',0);
prob = optimproblem('Objective',4*x-3*y-1*z-6*w,'ObjectiveSense','max');
prob.Constraints.c1 = 2*x-4*y+1*z+2*w <= 8;
prob.Constraints.c2 = 2*x-2*y-1*z-w <= 4;
problem = prob2struct(prob);
[sol,fmax] = linprog(problem)

and the result i get is

Problem is unbounded.

sol =

[]

fmax =

[]

is there a way to fix this or is there no solution???

Answer 1

[Walter Roberson]

Consider an objective of 2*x - y with constraint x-y <= 4 . Let x = y = 10^N . Then with x and y being the same, x-y is 0 which is <= 4. But 2*x - y under y = x would be x = 10^N which can grow without bound.

prob = optimproblem('Objective',4*x-3*y-1*z-6*w,'ObjectiveSense','max');

let z and w be their lower bounds, 0, then the objective simplifies to 4*x - 3*y

prob.Constraints.c1 = 2*x-4*y+1*z+2*w <= 8;

Still with z and w = 0 this would be 2*x - 4*y <= 8 . Suppose y >= x/2 then the result would be 0 or negative which would be <= 8

prob.Constraints.c2 = 2*x-2*y-1*z-w <= 4;

still with z and w = 0 this would be 2*x - 2*y <= 4 . Suppose y >= x then the result would be 0 or negative which would be <= 4

So.. if we let y = x then 4*x - 3*y grows without bound as x increases, and the constraints are satisfied.

or is there no solution???

No solution.

Answer 2

[Matt J]

Another way to verify that there is no solution is to look at the dual linear program.

min. 8*u+4*v
s.t.
     2*u    +2*v >= +4
    -4*u    -2*v >= -3
     1*u    -1*v >= -1
     2*u    -1*v >= -6
     u,v>=0

We can show that this dual LP is infeasible by adding together the first two inequality constraints, leading to u <= -0.5. This contradicts the positivity constraint u>=0. Therefore, the dual constraints are infeasible, which implies that the primal is unbounded.