Intlinprog function - problem

2 views (last 30 days)
Michal Malec
Michal Malec on 13 Sep 2020
Edited: Matt J on 13 Sep 2020
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+5x2150
8X1+5X2300
0X1+1X220
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.

Accepted Answer

Matt J
Matt J on 13 Sep 2020
Edited: Matt J on 13 Sep 2020
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
  1 Comment
Matt J
Matt J on 13 Sep 2020
Edited: Matt J on 13 Sep 2020
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.

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!