Solver stopped prematurely. No integer feasible point found

Solver stopped prematurely. No integer feasible point found (exitflag=0)

Problem description: There are value ranges of N units respectively, and their sum is required to be fixed, and the value of unit should be 0 as far as possible. Where, the sum of the units is the input value of the function, and the value ranges are the operation result of the previous code. The integer variable is the state variable of whether the unit has a value of 0.

Using intlinprog function: Put it into the optimization algorithm, there will be problems (Solver stopped prematurely. No integer feasible point found) if the number of iterations is too long. But it worked fine again when I ran only the outermost part of the code that reported the error. In theory, integer variables can all be 1 or 0, and that situation (No integer feasible point found) won't happen. So i don't kown why?

Code (MATLAB R2020a): n=9

f=[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1];%objective

aeq=[1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0];

beq= -1.1918e+03;%change

A=[-1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0 0 0 0;1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0 0 0 0;0 -1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0 0 0;0 1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0 0 0;0 0 -1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0 0;0 0 1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0 0;0 0 0 -1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0;0 0 0 1 0 0 0 0 0 0 0 0 8000 0 0 0 0 0;0 0 0 0 -1 0 0 0 0 0 0 0 0 8000 0 0 0 0;0 0 0 0 1 0 0 0 0 0 0 0 0 8000 0 0 0 0;0 0 0 0 0 -1 0 0 0 0 0 0 0 0 8000 0 0 0;0 0 0 0 0 1 0 0 0 0 0 0 0 0 8000 0 0 0;0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 8000 0 0;0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 8000 0 0;0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 8000 0;0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 8000 0;0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 8000;0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 8000];

B=[8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000];

intcon=[10 11 12 13 14 15 16 17 18];

lp=[-108.1824 -274.4183 -336.4196 -124.7959 -74.1171 -45.8906 -307.1947 -307.1947 -293.3694 0 0 0 0 0 0 0 0 0];%number1-9 change

up=[3.7743 0 0 -15.7397 34.9391 63.1656 0 0 13.8253 1 1 1 1 1 1 1 1 1];%number1-9 change

options = optimoptions('intlinprog','Display','off');

[jz1,fval,exitflag,output]=intlinprog(-f,intcon,A,B,aeq,beq,lp,up,options);

Answer 1

[Torsten]

I get the following solution

0.

- 159.2453

0.

- 124.7959

0.

0.

- 307.1947

- 307.1947

- 293.3694

1.

0.

1.

0.

1.

1.

0.

0.

0.

with a value of -4 (since you maximize f, +4) of the objective function.

[梦娇 何]

why did i get another solution ?

jz1 =

0

0

-336.4196

-124.7959

0

0

-307.1947

-307.1947

-116.1951

1.0000

1.0000

0

0

1.0000

1.0000

0

0

0

fval =

-4.0000

exitflag =

1

output =

包含以下字段的 struct:

relativegap: 0

absolutegap: 0

numfeaspoints: 2

numnodes: 0

constrviolation: 0

message: 'Optimal solution found.↵↵Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).'

[梦娇 何]

Torsten, does this code have an optimal solution as long as beq is within the total range of all units?

Thank you very much.

[Torsten]

why did i get another solution ?

Solutions can be different - as long as "fval" is the same.

Torsten, does this code have an optimal solution as long as beq is within the total range of all units?

I don't know what you mean.

[梦娇 何]

1、Oh, thanks. This is because the optimal solution is not unique, right?

2、I don't know whether it's "beq" that's confusing you. "beq" is the right-hand side of the equality constraint.

I want to ask you a question about "intlinprog". As the code example in my very first question, the variate ("beq" ) can change, and the variates ("lp(1-9)" and "up(1-9)") also can change,and the integer variates can only be 0 or 1("lp(10-18)" and "up(10-18)"). 0 and 1 is the unit's condition (Is unit's adjustable output equal to 0 ?)

• What would cause mixed linear prgraming solver stopped prematuely and no interge feasible point found (exitFlag =0)?
• when appling "intlinprog", "beq" always in the interval [sum(lp(1:9)), sum(up(1:9))]. It is guaranteed by other code. In this situations, will the mixed linear prgraming report an error especially "exitflag=0" ?

Look forward to your reply

[Torsten]

What would cause mixed linear prgraming solver stopped prematuely and no interge feasible point found (exitFlag =0)?

If intlinprog does not find an integer point for which your constraints are satisfied.

when appling "intlinprog", "beq" always in the interval [sum(lp(1:9)), sum(up(1:9))]. It is guaranteed by other code. In this situations, will the mixed linear prgraming report an error especially "exitflag=0" ?

I can't imagine that this can happen as long as lp and ub permit -8000 <= x(i) <= 8000 for 1 <= i <= 9.

[梦娇 何]

Torsten, thanks a lot .

1、I know your mean. In theory, integer variables in my code represent only one state and cannot be anything other than integers. They can all be 0 or 1 and part of them are 0 or 1. It is impossible not to find an integer point for which my constraints are satisfied, right ?

2、8000 is bigger than lp and up. It's M when we introduce an intermediate variable. -M(1-y)<=x<=M(1-y), when y=1, x=0; when y=0, -M<=x<=M, this constraint should not impact the actual problem. I have 18 variates, x1 x2 x3 x4 x5 x6 x7 x8 x9 -units' adjust outpower; y1 y2 y3 y4 y5 y6 y7 y8 y9 is units' state, integer variates.

[梦娇 何]

Could it be that the decimal point (1.0000! = 1 or others) causes no integer feasible point found?

[Torsten]

Up to now, you didn't show a setup for which intlinprog failed.

So just post the case and I'll try to find out the reason.

[梦娇 何]

Torsten, I changed the version from 2020a to 2021b and the problem wouldn't happen.

Thanks a lot.