Linprog gives a solution but one constraint is not satisfied (no notification)

Hi!

I am trying to solve a linear programming problem with LinProg where I try to maximize x1 and (in another application) maximize the sum of a vector, subject to some constraints. Now my problem is that the software provides a solution but when I check this with the constraint, in both applications the first constraint is not satisfied. I checked that I didn't write any negatives when there should be a positive or the other way around but the constraint seems fine. It has the same structure as the others and comes from the same data set so there should be no problem here.

Does anyone know what could be the problem here?

Thank you in advance!!!

[JT]

Thank you all for your help!

Answer 1

[Torsten]

I get

x3(1) = 387,2108

x3(3) = 7,5211

x3(9) = 4,8920

x3(10) = 0.3761

and x3(i) = 0 for all other components.

And this vector is feasible as you can see when you print out

constraints3*x3-b3

eq'*x3-400

Answer 2

[John D'Errico]

Not possible to know, since you don't actually show us the code you wrote. You may have done something wrong.

Or it may just be your understanding of what it means to satisfy a constraint, in terms of floating point arithmetic and the constraint tolerance. That is, is the constraint satisfied WITHIN the constraint tolerance?

Beyond that, my crystal ball tells me only that you may soon come into a large sum of money. Or maybe it is telling me that your relatives may soon inherit a large sum of money from you. It is very unclear. These darned crystal balls. ;-)

Seriously, if you want a better answer, you need to show code we can look at and verify to know where you are going wrong.

[Matt J]

JT's reply moved here:

Hi John!

First of thank you for the nice prophecy! Let's hope it proves to be true... :-).

This is my first time really working with matlab and this website so I am not familiar with a lot of these functions and the way people ask questions here, so sorry if I am a bit unclear. I will copy-paste my code below, with some added comments:

optx1 = VectorzerosS2 %this is an excel file that I created with a vector (1,0,0,0,...)' to make sure that the problem optimizes x1

f3 = -optx1' %I want to maximize x1 but linprog minimizes, so therefore I multiply it with -1

constraints3 = -transpose(W3) %This is a matrix with the constraints. I want every column of the matrix W3 to be bigger than or equal to the corresponding entry in z3. So the columns of W3 contain the coefficients, so that W(1,1)x1+W(2,1)x2+...+W(31,1)x31 >= z3

b3 = -transpose(z3) %z3 is the vector for the rhs of the constraints

lb3 = VectorzerosS1 %this is a vector of zeros so that every x is at least zero

eq = VectorzerosS5 %this is a vector of ones to make sure that all entries of x sum up to 400

x3 = linprog(f3,constraints3,b3,eq',400,lb3)

Hopefully this makes it more clear for you!

[Torsten]

Just supply executable MATLAB code so that we can reproduce the "error".

[JT]

W3 = Wmatrix %as send with this question
z3 = zmatrix %as send with this question

lb3 = zeros(31,1) %vector with only zeros of size 31x1
eq = ones(31,1) %vector with only ones of size 31x1
optx1 = [1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0] %vector with entry 1 being 1 and all other entries 0 of size 31x1

f3 = -optx1'
constraints3 = -transpose(W3)
b3 = -transpose(z3)

x3 = linprog(f3,constraints3,b3,eq',400,lb3)

[JT]

Do you mean like this? Does this help/work?

[Matt J]

Your zmatrix has only 23 elements in it, instead of 31. It would be easiest if you simply attached f3, constraints, and b3 in a .mat file directly.

One suggestion I can make though is not to express your constraint data in units of milligrams and micrograms. Express them in kilograms so that you won't have such huge numbers.

[Torsten]

Your zmatrix has only 23 elements in it, instead of 31.

W3' is 23x31, x3 is 31x1, b3' is 23x1.

Answer 3

[Matt J]

load data

defaultOptions=optimoptions('linprog');

[x3,fval,exitflag,output] = linprog(f3,constraints3,b3,eq',400,lb3,[], defaultOptions);

Optimal solution found.

The constraint violation is quite small, certainly smaller than the default tolerance, although I don't know if that's supposed to be an absolute or relative tolerance.

output.constrviolation

ans = 2.9802e-08

defaultOptions.ConstraintTolerance

ans = 1.0000e-04

It is also insignificant compared to the typical magnitudes of your constraints:

min(b3-constraints3*x3)

ans = -2.9802e-08

median(b3-constraints3*x3)

ans = 1.5049e+08