How to solve b≤Cx≤z with linear programming?

Hello,

I'd like to calculate the following. For example:

There is a Matrix C m*n(5x4), vector b (b1,b2,b3,b4,b5) and vector z (z1,z2,z3,z4,z5), their values are given. I need to find such vector x (x1,x2,x3,x4,x5) that:

*my calculation:

b1<= Cm1n1*x1 + Cm2n1*x2 + Cm3n1*x3 + Cm4n1*x4 + Cm5n1*x5 < z1
.
.
.
b5<= Cm1n5*x1 + Cm2n5*x2 + Cm3n5*x3 + Cm4n5*x4 + Cm5n5*x5 < z5

Also, the vector x must have positive values.

I was adviced to resolve it by linear programmning. So I have had a look at LINPROG. As I was not sure what to put instead of "f" (Linear objective function vector) I set it to a vector of 0's as I also did that for vector of lower bounds.

x = linprog(f,C,b,[],[],lb)

The vector x which was calculated gave me positive values. Then I have used these x-values for *my calculation (see above please), which gave me results which are far bellow the vector b values.

Does anybody know what I am doing wrong? How to get x above d but below z?

Many thanks. LZ

[Sean de Wolski]

Could you provide us with the f,C,b matrices you're using please?

[Zdenek]

Hello, thank you for response. Actually, I am testing it on a 40x13 Matrix which does not fit here, so I reduced it to 40x7. Here it goes:

Matrix C

3.3845 1.5 5.94 9.8239 14.88 1.46 11.59

0.0009 0.0003 0.0009 0.0006 0.0018 0.0002 0

0.0007 0.0021 0.0125 0.0046 0.005 0.0016 0.0061

0.014 0.029 0 0.0527 0 0.039 0.093

0.1804 0.088 0.008 0.5049 0.015 0.082 0.665

0.0257 8.16 2.08 0 2.14 0 1.99

0 0 0.0175 0 0.0024 0 0

0.0011 0.0055 0.018 0.0055 0.0062 0.027 0.04

0.1847 0.132 0.003 0.0388 0 0 0

0.0006 0.0004 0.0007 0.0022 0.0004 0 0

0.0006 0.0003 0.0045 0.0006 0.0033 0.0034 0.0006

0.0206 0.011 0.0305 0.0053 0.0794 0.0025 0.0303

0.0037 0.0028 0.016 0.0043 0.0053 0 0.007

0.002 0.0012 0.0012 0.0015 0.0009 0.002 0.0017

0.0046 0.034 0.25 0 0.015 0 0.01

0.3574 0.63 0.21 0.1514 0.07 0 0.14

0 0 0.02 0 0.016 0 0

0.2699 0.0701 0 0 0 0 0.01

0.0899 0.246 0.4 0.0892 11.8 3.25 0.675

0.0006 0.0004 0.0007 0.0014 0.0003 0 0.0027

0.0068 0.008 0.0047 0.0006 0.003 0 0.8

0.2687 0.03 0.21 0.2259 0.138 0.1 0.034

0.0113 0.0024 0.02 0.006 0.0082 0.04 0.06

0.2469 0.096 0.13 0.2465 0.44 0 0.41

0.0024 0.0036 0.0005 0.0077 0.0006 0 0.0024

0.5532 0.331 2.1 0.857 9.3 0 0.657

4.1092 2.86 1.3 1.4749 0.92 0 10.26

0.0028 0.001 0.233 0.0095 0.11 0 0.022

5.5183 0.66 1.4 4.8095 9.98 0 0.21

0.003 0.0019 0.014 0.0088 0.0275 0 0.002

0.019 0.007 0.126 0.0647 0.336 0.018 0.029

0.7018 0.2 7.5 1.5144 18 0.54 0.79

1.0883 0.26 11 3.6214 31 0.76 1.4

1.0872 0.24 9.9 1.3827 27 0.73 1.2

0.4145 0.07 7 0.7243 10.7 0.22 0.2

1.1282 0.27 12.7 4.1481 35 0.72 1.15

0.643 0.18 6 1.7778 12 0.48 0.65

0.2865 0.06 1.8 0.7243 4.6 0.15 0.14

1.0865 0.3 9.5 2.107 23 0.87 1.2

0.3363 0.08 3.2 0.9218 9.5 0.27 0.44

vector b:

9356.77980000000

1.60000000000000

17

38

130

900

5

15

120

1.20000000000000

1.30000000000000

16

5

1.30000000000000

30

400

2.40000000000000

125

1000

0.900000000000000

35

150

48.9600000000000

420

2.30000000000000

700

4700

55

1500

11

104.800000000000

2489

5502

4978

2489

4323

2620

655

3144

1834

f:

0

0

0

0

0

0

0

Thanks a lot for your help.

z

[Sean de Wolski]

Rereading: So your f vector is set to zeros? This is likely the source of the error, anything multiplied by zeros will be more zeros.

[Zdenek]

So, to what number shall I set it? If it was possible, I would like to omit this f.

[Sean de Wolski]

Your question isn't clear to me. If you look at the doc for linsolve, you'll see that you're trying to find an optimal x that minimizes f'x. If f is all zeros, you can pick any x you want that meets your above constraints and it will lie on the hyperplane defining the minimum of f'x, i.e. zeros in all n-dimensions.

[Zdenek]

Well, when you look at the data I have: Matrix C, vector b, and vector z, what would be the best function for me to find vector x, such that:

b1<= Cm1n1*x1 + Cm2n1*x2 + Cm3n1*x3 + Cm4n1*x4 + Cm5n1*x5 < z1

.

.

.

b5<= Cm1n5*x1 + Cm2n5*x2 + Cm3n5*x3 + Cm4n5*x4 + Cm5n5*x5 < z5

Do you have an idea please?

Many thanks

z

Answer 1

[Teja Muppirala]

You can solve this with LINPROG, but I think you need help in understanding how to formulate your constraints properly.

Constraint 1: C*x < z

This is fine as it is.

Constraint 2: C*x > b

Multiply this equation by -1 and rewrite it as

-C*x < -b

Now, we will need to combine both of these constraints into a single matrix.

[C; -C]*x < [z; -b]

This inequality is saying the exact same thing as the two inequalities above. It is just using matrix multiplication. Now LINPROG can accept the [C; -C] and [z; -b] as its inputs to define the constraint.

As a concrete example:

C =[  -1.3617    1.0655    0.0909   -0.5503
  -0.6411   -0.2132   -2.1390    0.9111
  -0.0097   -0.2970    0.2654   -0.7814
   0.5465    0.4400   -0.2322   -0.7191
   0.3432   -0.4943    0.4786   -0.3528];

b = [-1; -2; -3; -4; -5];
z = [2; 3; 4; 5; 6];

lowerbound_on_x = zeros(size(C,2),1);
f = zeros(size(C,2),1);

x = linprog(f,[-C;C],[-b;z],[],[],lowerbound_on_x)

This gives me:

x =

    1.9958
    4.2650
    0.3293
    2.3048

You can then confirm C*x

ans =

    0.5883
   -0.7932
   -2.9996
    1.2334
   -2.0788

This satisfies b < C*x < z and x > 0

[Zdenek]

Hello, thank you very much for your response. I have ran the code with a larger dataset multiple times with different settings, but I am having some issues.

The smaller "z" is set the higher "Cx" is calculated it implies

the smaller "z" is set the more "b" values is reached, but there are always some "Cx" values which are below "b" values. I thought that if "z" is sufficiently high, every "Cx" would be above "b" but it obviously is not the case. Well I am getting hopeless.Any ideas? Many thanks.z

[Zdenek]

Well, I have mixed your code with the one from Sean de Wolski so now I am having:

x = linprog(f,[C;-C],[z;-b],[],[],lowerbound_on_x)

and I am having pretty results. I will play a bit more with it and come back.

Answer 2

[Sean de Wolski]

%Cx<z
%Cx>b
C = rand(5);
b = (1:5)';
z = (11:15)';
x = [C;C]\[z; b]

constraintsMet = all(C*x>=b)&&all(C*x<z)

Maybe?

[Zdenek]

Alright, now I need to figure out, how to make all x positive. Also, I had a look at your profile and I see you are one of the few magician men in MATLAB ;-). So could you please explain me why in:

x = [C;C]\[z; b] are C;C and z;b separated with semicolon and why are there two of them? In what relation they are to each other? Does it mean the first C gets divided by z and then also by b, the same valid for second C? Or first C is divided by z and second C is divided by b? And then what I do with its results? And how do I get those x positive? :-)

Thank you very much for your time. I am just a begging beginer :-}}