linprog not giving all possible solutions

I have the following issue with linear programming specific to biological data.

The specific method requires the maximization and minimization of all values subject to one specific value.

for example I have 5 variables v,w,x,y,z, I need to maximize v, and when this is performed what are the values of w,x,y,z. This is then repeated where w is maximized and the optimal values of v,x,y and z are required.

I have been using the linprog function to determine the value, the following constraints and equalities are set:

v + w + x + y = 100

v + y <= 60

w + x <= 40

x + z <= 30

v + x <= 70

w + y <= 30

y + z <= 20

v,w,x,y,z >= 0

v,w,x,y,z <=100

I'm assuming my problem is the setup of the objective function, currently what I have been trying with moderate success is to set the objective function specific to the value that needs to be optimized eg. 1v + 0w + 0x + 0y + 0z

my code is as follows:

f = [1;0;0;0;0]
A = [1 0 0 1 0; 0 1 1 0 0; 0 0 1 0 1; 1 0 1 0 0; 0 1 0 1 0; 0 0 0 1 1]
b = [60;40;30;70;30;20]
 Aeq = [1 1 1 1 0]
beq = 100
lb =[0;0;0;0;0]
ub = [100;100;100;100;100]

When I perform the linprog I get the following values for when v is minimized:

>> x = linprog(f,A,b,Aeq,beq,lb,ub)
Optimal solution found.
x =
    40
    10
    30
    20
     0

which according to my notes is correct, however when I maximize v:

>> x = linprog(-f,A,b,Aeq,beq,lb,ub)

Optimal solution found.
x =
    60
    30
    10
     0
     0

where the expected solution should have been:

x = 
     60
     30
     10
     0
     20

This pattern repeats with every variable where either all the values are correct or the last value is incorect (usually displaying zero when it is not). Is this an issue as to how I approaced the objective function? Is there a better way to solve these types of issues? Any assistance would be greatly appreciated.

Answer 1

[Alan Weiss]

You might want to try the problem-based approach, which makes formulating and analyzing your problem easier.

v = optimvar('v','LowerBound',0,'UpperBound',100);
w = optimvar('w','LowerBound',0,'UpperBound',100);
x = optimvar('x','LowerBound',0,'UpperBound',100);
y = optimvar('y','LowerBound',0,'UpperBound',100);
z = optimvar('z','LowerBound',0,'UpperBound',100);
prob = optimproblem('Objective',v,'ObjectiveSense','maximize');
prob.Constraints.c1 = v + w + x + y  == 100;
prob.Constraints.c2 = v + y <= 60;
prob.Constraints.c3 = w + x <= 40;
prob.Constraints.c4 = x + z <= 30;
prob.Constraints.c5 = v + x <= 70;
prob.Constraints.c6 = w + y <= 30;
prob.Constraints.c7 = y + z <= 20;

[sol,fval] = solve(prob)

Solving problem using linprog.

Optimal solution found.

sol =

struct with fields:

v: 60

w: 30

x: 10

y: 0

z: 0

fval =

60

You can tweak the objective slightly to get the solution you prefer.

prob.Objective = v + 1e-10*(w+x+y+z); % Prefer higher variable values
[sol,fval] = solve(prob)

Solving problem using linprog.

Optimal solution found.

sol =

struct with fields:

v: 60

w: 30

x: 10

y: 0

z: 20

fval =

60.0000

Using the problem-based approach you can easily change the objective sense and other problem attributes.

Alan Weiss

MATLAB mathematical toolbox documentation

[Wynand van Losenoord]

This is perfect, thank you so much

Would you mind elaborating why the following:

prob.Objective = v + 1e-10*(w+x+y+z); % Prefer higher variable values

[sol,fval] = solve(prob)

prevents the 0 value from being reported?

[Alan Weiss]

I changed the objectve function to increase slightly when any variables increase. Therefore, the maximum value, if nonunique, is attained at larger variable values. Your problem has a nonunique solution, so this slight change makes the reported solution nonzero where possible. The change is so slight that it does not affect the resulting objective value to display precision.

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[green_ananas]

Hey,

Maybe you didn't copy the equations correctly. The way you stated it, z doesn't appear in the top equation. Therefore, as long as all constraints are met and x is maximum, the value of z doesn't matter and you just obtain one of all local solutions as expected.

[Wynand van Losenoord]

Thanks for the response, are you referring to the following equality constraint:

v + w + x + y = 100

in this specific constrain, z does not partake only the sym of v,w,x and y must equal 100.

if you look at the other constraints, just calculating it basically if v,w,x and y are 60,30,10 and 0 as indicated by the linprog then according to the constraints:

x + z <= 30

and

y + z <= 20

then z can equal 20 and still comply.

This is how I undersatnd it.

[green_ananas]

Exactly, and as you can see, every value of is compatible with your constraints. If you wanted to obtain the maximum z of all solutions, you would need to reformulate your objective function which you are minimizing. The way it is formulated now, linprog only looks for the maximum value of v, and doesn't care about the other values as long as they don't violate the constraints.

[Wynand van Losenoord]

I understand, so the valaues are true, they are however not the maximum values for all. Basically what I want to achieve is to determine the maximum/minimum of the other variables if the variable in question was running at its maximum/minimum. I'm guessing there is no simple way to do this with the linprog function?