Intlinprog function - problem

I want to solve a math problem that give me a minimal value of a function. The function of the objective is:

min 64x1+40x2

The invariants are:

3x1+5x2≤150
8X1+5X2≤300
0X1+1X2≤20

I wrote the code in Matlab:

f=-[64;40]; intcon = [1;2]; A=[3,5;8,5;0,1]; B=[150;300;20];
[x,fval] = intlinprog(f,intcon,A,B,[],[],lb)

When I run this code, I get the results:

 x =
 30.0000
 12.0000
 
 fval =
  -2.4000e+03

And this results are ok, but when I changes the value of the objective function from 64 to 64.01, I get the strongly changed values of X:

  x =
  35.0000
  4.0000
  
  fval =
  -2.4003e+03

I would like to know why the value of x varies so much.

Answer 1

[Matt J]

The optimal solution of a linear program can be discontinuous as a function of the problem data, particular when you have integer constraints. Here is an example where it is easier to understand how integer constraints can induce this behavior.

>> LB=[0,0]; x=intlinprog([1,1],1:2,[],[],[],[],LB).'

x =

     0     0

One sees here that the optimum is achieved at the boundaries specified by LB. Clearly therefore, if I increase the lower bounds by even a small amount, the optimal x(i) must jump to the next integer:

>> x=intlinprog([1,1],1:2,[],[],[],[],LB+0.00002).'


x =

     1     1

[Matt J]

Even in non-integer problems, the solution can jump strongly with a small perturbation in the problem data. Consider this example, where the feasible region is the unit square.

f=[0,1];

delta_f=1e-10*[1,0];%A very small perturbation 

x=intlinprog(f+delta_f,[],[],[],[],[],[0,0],[1,1]).', %optimum=[0,0]

x=intlinprog(f-delta_f,[],[],[],[],[],[0,0],[1,1]).', %optimum=[1,0]

Despite the small difference by 2*delta_f in the objective coefficients, the optimal x(1) solution changes a lot. This happens because the objective, when viewed as a 2D line, is very nearly parallel to one of the faces of the unit square, so a small tipping in its slope will cause the optimum to occur at a different vertex.