Problem with SCIP solver for MINLP
114 views
Skip to first unread message
Jane
Jul 22, 2020, 4:02:19 PM7/22/20
to YALMIP
Dear Johan,
I hope you are doing well.
I need to solve a mixed integer non linear program with linear constraints and a non-linear objective function.
I am trying to solve it with SCIP. However, it takes so much time and does not end.
It should be mentioned that without the binary variable (assuming it is a parameter and initialized beforehand), I had to use ipopt instead of fmincon because fmincon had problems with the model while ipopt could solve it easily.
Any help would be appreciated.
Here is my code:
CF = [0.063,0.063,0.125,0.125,0.175,0.175;0.0865,0.0865,0.457,0.457,0.0457,0.0457;0.191,0.191,0.197,0.197,0.0353,0.0353;0.127,0.127,0.186,0.186,0.066,0.066;0.269,0.269,0.066,0.066,0.086,0.086;0.059,0.059,0.044,0.044,0.67,0.67];
CC = [12.09,5.11,23.19,20.56,44.84,27.506;1.565,1.84,0.92,1.029,0.95,2.49];
z = [0,1,0,0;0,1,0,0;0,0,1,0;0,0,1,0;0,0,0,1;0,0,0,1];
%-------Variables------------
x_1 = sdpvar(6,6,'full');
y_1 = binvar(6,6,'full');
x_2 = sdpvar(2,6,'full');
%-----------Constraint1--------------
F = [x_1<=40*y_1];
F = [F, x_1>=0];
%-----------Constraint2--------------
F = [F, x_2<=40];
F = [F, x_2>=0];
%-----------Constraint3--------------
F = [F, sum(y_1,2)==ones(6,1)];
F = [F, sum(y_1,1)<=ones(1,6)];
%----------Constraint4----------------
for n = 2:4
leftP = 0;
for u = 1:6
for l = 1:6
if z(l,n) == 1
leftP = leftP + y_1(u,l)*x_1(u,l);
end
end
end
for u = 1 : 2
for l = 1:6
if z(l,n) == 1
leftP = leftP + x_2(u,l);
end
end
end
F = [F, leftP <= 40];
end
%--------------Constraint5--------------------
for l=1:6
for u=1:6
sp = 0;
for i=1:2
sp = sp + x_2(i,l);
end
F = [F, CC(2,l)* (y_1(u,l)*x_1(u,l) - sp) >= (0.0011 - (1-y_1(u,l))*10)];
end
end
%--------------Constraint6--------------------
for l=1:6
F = [F, CC(1,l)* (x_2(2,l) - x_2(1,l)) >= 0.0011];
end
%--------------Constraint7------------------------
for u=1:2
for l=1:6
Num = x_2(u,l)*CC(u,l);
Den = 0.0000001;
for kk = 1 : (u-1)
Den = Den + x_2(kk,l)*CC(u,l);
end
F = [F, Num>=3*Den];
end
end
%-------------------Objective Function-------------
obj=0;
for u=1:6
for l=1:6
Num = x_1(u,l)*CF(u,l);
Den = 0.0000001;
for kk = 1 : 2
Den = Den + x_2(kk,l)*CF(u,l);
end
temp1 = Num+Den;
temp2 = Den;
obj = obj + y_1(u,l)*(log2(temp1)-log2(temp2));
end
end
opts = sdpsettings('solver','SCIP','scip.maxnodes',20000000, 'scip.maxtime', 200000);
optimize(F,-1*obj,opts);
CC = [12.09,5.11,23.19,20.56,44.84,27.506;1.565,1.84,0.92,1.029,0.95,2.49];
z = [0,1,0,0;0,1,0,0;0,0,1,0;0,0,1,0;0,0,0,1;0,0,0,1];
%-------Variables------------
x_1 = sdpvar(6,6,'full');
y_1 = binvar(6,6,'full');
x_2 = sdpvar(2,6,'full');
%-----------Constraint1--------------
F = [x_1<=40*y_1];
F = [F, x_1>=0];
%-----------Constraint2--------------
F = [F, x_2<=40];
F = [F, x_2>=0];
%-----------Constraint3--------------
F = [F, sum(y_1,2)==ones(6,1)];
F = [F, sum(y_1,1)<=ones(1,6)];
%----------Constraint4----------------
for n = 2:4
leftP = 0;
for u = 1:6
for l = 1:6
if z(l,n) == 1
leftP = leftP + y_1(u,l)*x_1(u,l);
end
end
end
for u = 1 : 2
for l = 1:6
if z(l,n) == 1
leftP = leftP + x_2(u,l);
end
end
end
F = [F, leftP <= 40];
end
%--------------Constraint5--------------------
for l=1:6
for u=1:6
sp = 0;
for i=1:2
sp = sp + x_2(i,l);
end
F = [F, CC(2,l)* (y_1(u,l)*x_1(u,l) - sp) >= (0.0011 - (1-y_1(u,l))*10)];
end
end
%--------------Constraint6--------------------
for l=1:6
F = [F, CC(1,l)* (x_2(2,l) - x_2(1,l)) >= 0.0011];
end
%--------------Constraint7------------------------
for u=1:2
for l=1:6
Num = x_2(u,l)*CC(u,l);
Den = 0.0000001;
for kk = 1 : (u-1)
Den = Den + x_2(kk,l)*CC(u,l);
end
F = [F, Num>=3*Den];
end
end
%-------------------Objective Function-------------
obj=0;
for u=1:6
for l=1:6
Num = x_1(u,l)*CF(u,l);
Den = 0.0000001;
for kk = 1 : 2
Den = Den + x_2(kk,l)*CF(u,l);
end
temp1 = Num+Den;
temp2 = Den;
obj = obj + y_1(u,l)*(log2(temp1)-log2(temp2));
end
end
opts = sdpsettings('solver','SCIP','scip.maxnodes',20000000, 'scip.maxtime', 200000);
optimize(F,-1*obj,opts);
Johan Löfberg
Jul 23, 2020, 2:22:59 AM7/23/20
to YALMIP
Your question is a bit weird as you mix fmincon (a local nonlinear solver) with scip (a global nonlinear mixed-integer solver). Those are incomparable and would never be discussed in the same context.
However, as far as I can tell, the majority of nonlinearities in your model are due to bad modelling. You have a lot of binary*continuous, which you should eliminate through llinearizing logic models
Jane
Jul 23, 2020, 8:40:44 AM7/23/20
to YALMIP
Thank you for your reply.
I mentioned the fmincon problem because I wanted to point out that this model with just real variables, even "without the binary variable" (assuming it is fixed), had some issues. I thought it may be due to the logarithmic objective function ( log2(1+Num/Den) ) and I guessed it is now making a problem for SCIP to solve this model "with the binary variables".
ipopt could solve the model with just the real variables easily. Now, I am having problem with solving the same model with additional binary variables.
As you suggested, I linearized the constraints. I eliminated y_1(u,l) in constraints 4 and 5 since I had constraints 1 which implies "if y_1(u,l)=0, then x_1(u,l)=0" .
I also changed the objective function to eliminate the product of y_1 * log2(1+Num/Den) (by introducing a new variable "t").
However, SCIP still has problem with it and it takes so much time.
I would be grateful if you could let me know where I might have made a mistake or suggest me any other solver.
Here is my code:
CF = [0.063,0.063,0.125,0.125,0.175,0.175;0.0865,0.0865,0.457,0.457,0.0457,0.0457;0.191,0.191,0.197,0.197,0.0353,0.0353;0.127,0.127,0.186,0.186,0.066,0.066;0.269,0.269,0.066,0.066,0.086,0.086;0.059,0.059,0.044,0.044,0.67,0.67];
CC = [12.09,5.11,23.19,20.56,44.84,27.506;1.565,1.84,0.92,1.029,0.95,2.49];
z = [0,1,0,0;0,1,0,0;0,0,1,0;0,0,1,0;0,0,0,1;0,0,0,1];
%-------Variables------------
x_1 = sdpvar(6,6,'full');
y_1 = binvar(6,6,'full');
x_2 = sdpvar(2,6,'full');
CC = [12.09,5.11,23.19,20.56,44.84,27.506;1.565,1.84,0.92,1.029,0.95,2.49];
z = [0,1,0,0;0,1,0,0;0,0,1,0;0,0,1,0;0,0,0,1;0,0,0,1];
%-------Variables------------
x_1 = sdpvar(6,6,'full');
y_1 = binvar(6,6,'full');
x_2 = sdpvar(2,6,'full');
t = sdpvar(6,6,'full');
%-----------Constraint1--------------
F = [x_1<=40*y_1];
F = [F, x_1>=0];
%-----------Constraint2--------------
F = [F, x_2<=40];
F = [F, x_2>=0];
%-----------Constraint3--------------
F = [F, sum(y_1,2)==ones(6,1)];
F = [F, sum(y_1,1)<=ones(1,6)];
%----------Constraint4----------------
for n = 2:4
leftP = 0;
for u = 1:6
for l = 1:6
if z(l,n) == 1
leftP = leftP + x_1(u,l);
end
end
end
for u = 1 : 2
for l = 1:6
if z(l,n) == 1
leftP = leftP + x_2(u,l);
end
end
end
F = [F, leftP <= 40];
end
%--------------Constraint5--------------------
for l=1:6
for u=1:6
sp = 0;
for i=1:2
sp = sp + x_2(i,l);
end
F = [F, CC(2,l)* (x_1(u,l) - sp) >= (0.0011 - (1-y_1(u,l))*10)];
end
end
%--------------Constraint6--------------------
for l=1:6
F = [F, CC(1,l)* (x_2(2,l) - x_2(1,l)) >= 0.0011];
end
%--------------Constraint7------------------------
for u=1:2
for l=1:6
Num = x_2(u,l)*CC(u,l);
Den = 0.0000001;
for kk = 1 : (u-1)
Den = Den + x_2(kk,l)*CC(u,l);
end
F = [F, Num>=3*Den];
end
end
%-------------------Constraint 8-------------
obj=0;
for u=1:6
for l=1:6
Num = x_1(u,l)*CF(u,l);
Den = 0.0000001;
for kk = 1 : 2
Den = Den + x_2(kk,l)*CF(u,l);
end
temp1 = Num+Den;
temp2 = Den;
F = [F, t(u,l) <= (log2(temp1)-log2(temp2))];
F = [F, t(u,l) >= (log2(temp1)-log2(temp2)) - 20*(1-y_1(u,l))];
F = [F, t(u,l) <= y_1(u,l)*20];
F = [F, t(u,l) >= 0];
F = [F, t(u,l) >= (log2(temp1)-log2(temp2)) - 20*(1-y_1(u,l))];
F = [F, t(u,l) <= y_1(u,l)*20];
F = [F, t(u,l) >= 0];
end
end
%-------------------Objective Function-------------
obj=0;
for u=1:6
for l=1:6
obj = obj + t(u,l);
Johan Löfberg
Jul 23, 2020, 9:54:39 AM7/23/20
to YALMIP
You have 72 binary variables which funnily matches perfectly with the discussion here https://yalmip.github.io/slowmilp
Have you tried starting with a trivial size, and then working your way up?
Message has been deleted
Jane
Jul 29, 2020, 5:27:59 AM7/29/20
to YALMIP
Thank you for your reply.
I have 36 binary variables, not 72.
As you suggested, I tried a trivial size with 12 binary variables. Again, it still takes so much time and it is interrupted at last because "node limit reaches" even with 20000000 nodes.
For small problem (12 binary variables), I even implemented the exhaustive search method which, for every feasible combination of the binary variables, solves the problem for other real variables (using ipopt), then selects the best answer among all the combinations. It was solved in half an hour. I was expecting the solver to provide a solution sooner than this or in the "worst case" check every possible combination like the exhaustive search.
My other observation was that the found solution after one hour (I interrupted the solver myself) is the same as the found solution after 20000000 nodes (multiple hours) for the large problem. Both solutions are the same and infeasible (right hand side is violated by 4.8e-005)
Any help would be appreciated.
Here is my code for 12 binary variables:
CF =
[0.152,0.152,0.086,0.086;0.065,0.065,0.1633,0.1633;0.095,0.0953,0.0963,0.0963];
CC = [67.5824,19.277,67.2773,8.66;0.988,3.29,3.11,8.594];
z = [0,1,0;0,1,0;0,0,1;0,0,1];
%-------Variables------------
x_1 = sdpvar(3,4,'full');
y_1 = binvar(3,4,'full');
x_2 = sdpvar(2,4,'full');
t = sdpvar(3,4,'full');
%-----------Constraint1--------------
F = [x_1<=40*y_1];
F = [F, x_1>=0];
%-----------Constraint2--------------
F = [F, x_2<=40];
F = [F, x_2>=0];
%-----------Constraint3--------------
F = [F, sum(y_1,2)==ones(3,1)];
F = [F, sum(y_1,1)<=ones(1,4)];
%----------Constraint4----------------
for n = 2:3
leftP = 0;
for u = 1:3
for l = 1:4
if z(l,n) ==
1
leftP = leftP + x_1(u,l);
end
end
end
for u = 1 : 2
for l = 1:4
if z(l,n) ==
1
leftP = leftP + x_2(u,l);
end
end
end
F = [F, leftP <= 40];
end
%--------------Constraint5--------------------
for l=1:4
for u=1:3
sp = 0;
for i=1:2
sp = sp +
x_2(i,l);
end
F = [F, CC(2,l)* (x_1(u,l) - sp)
>= (0.0011 - (1-y_1(u,l))*10)];
end
end
%--------------Constraint6--------------------
for l=1:4
F = [F, CC(1,l)* (x_2(2,l) - x_2(1,l)) >= 0.0011];
end
%--------------Constraint7------------------------
for u=1:2
for l=1:4
Num = x_2(u,l)*CC(u,l);
Den = 0.0000001;
for kk = 1 : (u-1)
Den =
Den + x_2(kk,l)*CC(u,l);
end
F = [F, Num>=3*Den];
end
end
%-------------------Constraint 8-------------
obj=0;
for u=1:3
for l=1:4
Num =
x_1(u,l)*CF(u,l);
Den = 0.0000001;
for kk = 1 : 2
Den =
Den + x_2(kk,l)*CF(u,l);
end
temp1 = Num+Den;
temp2 = Den;
F = [F, t(u,l) <=
(log2(temp1)-log2(temp2))];
F = [F, t(u,l) >=
(log2(temp1)-log2(temp2)) - 40*(1-y_1(u,l))];
F = [F, t(u,l) <= y_1(u,l)*40];
F = [F, t(u,l) >= 0];
end
end
%-------------------Objective Function-------------
obj=0;
for u=1:3
for l=1:4
Johan Löfberg
Jul 29, 2020, 7:08:10 AM7/29/20
to YALMIP
A MILP with 12 binary variables is easy, but you don't have a MILP, you have a non-convex MINLP which you try to solve globally. Hence it can be almost arbitrarily hard to solve
Baron solves the problem in 1s though
Johan Löfberg
Jul 29, 2020, 7:24:09 AM7/29/20
to YALMIP
YALMIPs built-in global solver struggles but finds a reasonably good solution in a couple of minutes
>> optimize(F,-1*obj,sdpsettings('solver','bmibnb','bmibnb.upper','ipopt'))* Starting YALMIP global branch & bound.* Upper solver : ipopt* Lower solver : GUROBI* LP solver : GUROBI* -Extracting bounds from model* -Perfoming root-node bound propagation* -Calling upper solver (no solution found)* -Branch-variables : 24* -More root-node bound-propagation* -Performing LP-based bound-propagation * -And some more root-node bound-propagation* Starting the b&b process Node Upper Gap(%) Lower Open Time 1 : Inf NaN -5.905E+01 2 5s 2 : Inf NaN -5.905E+01 3 6s 3 : Inf NaN -5.905E+01 4 8s 4 : Inf NaN -5.905E+01 5 11s 5 : Inf NaN -5.905E+01 6 12s 6 : Inf NaN -5.905E+01 7 17s 7 : Inf NaN -5.905E+01 8 19s 8 : Inf NaN -5.905E+01 9 20s 9 : Inf NaN -5.905E+01 10 23s 10 : Inf NaN -5.905E+01 11 25s 11 : Inf NaN -5.904E+01 12 26s 12 : Inf NaN -5.904E+01 13 28s 13 : Inf NaN -5.904E+01 14 29s 14 : Inf NaN -5.904E+01 15 31s 15 : Inf NaN -5.904E+01 16 33s 16 : Inf NaN -5.904E+01 17 37s 17 : Inf NaN -5.904E+01 18 42s 18 : Inf NaN -5.904E+01 19 46s 19 : Inf NaN -5.904E+01 20 49s 20 : Inf NaN -5.904E+01 21 53s 21 : Inf NaN -5.903E+01 22 58s 22 : Inf NaN -5.903E+01 23 60s 23 : Inf NaN -5.873E+01 24 61s 24 : Inf NaN -5.873E+01 25 75s 25 : Inf NaN -5.873E+01 26 76s 26 : Inf NaN -5.873E+01 27 79s 27 : Inf NaN -5.873E+01 28 80s 28 : Inf NaN -5.873E+01 29 82s 29 : Inf NaN -5.873E+01 30 83s 30 : Inf NaN -5.873E+01 31 86s 31 : Inf NaN -5.872E+01 32 88s 32 : Inf NaN -5.872E+01 33 90s 33 : Inf NaN -5.872E+01 34 92s 34 : Inf NaN -5.872E+01 35 93s 35 : Inf NaN -5.872E+01 36 96s 36 : Inf NaN -5.872E+01 37 98s 37 : Inf NaN -5.872E+01 38 106s 38 : Inf NaN -5.872E+01 39 107s 39 : Inf NaN -5.872E+01 40 112s 40 : Inf NaN -5.872E+01 41 116s 41 : Inf NaN -5.872E+01 42 120s 42 : Inf NaN -5.872E+01 43 127s 43 : Inf NaN -5.862E+01 44 131s 44 : Inf NaN -5.862E+01 45 138s 45 : Inf NaN -5.860E+01 46 140s 46 : Inf NaN -5.860E+01 47 141s 47 : Inf NaN -5.860E+01 48 144s 48 : Inf NaN -5.860E+01 49 147s 49 : Inf NaN -5.860E+01 50 150s 50 : Inf NaN -5.860E+01 51 156s 51 : Inf NaN -5.860E+01 52 164s 52 : Inf NaN -5.860E+01 53 166s 53 : Inf NaN -5.860E+01 54 168s 54 : Inf NaN -5.860E+01 55 169s 55 : -4.085E+01 35.01 -5.860E+01 56 170s Improved solution found by heuristics 56 : -4.085E+01 35.01 -5.860E+01 57 171s 57 : -5.784E+01 1.29 -5.860E+01 46 173s Improved solution found by heuristics | Pruned stack based on new upper bound 58 : -5.784E+01 1.29 -5.860E+01 45 174s Infeasible in node bound-propagation 59 : -5.784E+01 1.28 -5.859E+01 46 177s 60 : -5.784E+01 1.28 -5.859E+01 47 179s 61 : -5.784E+01 1.28 -5.859E+01 48 184s 62 : -5.784E+01 1.28 -5.859E+01 49 186s 63 : -5.784E+01 1.27 -5.859E+01 50 189s 64 : -5.784E+01 1.27 -5.859E+01 51 189s 65 : -5.784E+01 1.24 -5.857E+01 52 190s 66 : -5.784E+01 1.24 -5.857E+01 53 192s 67 : -5.784E+01 1.24 -5.857E+01 54 194s 68 : -5.784E+01 1.24 -5.857E+01 55 195s 69 : -5.784E+01 1.24 -5.857E+01 56 196s 70 : -5.784E+01 1.24 -5.857E+01 57 196s 71 : -5.784E+01 1.23 -5.856E+01 58 197s 72 : -5.784E+01 1.23 -5.856E+01 59 198s 73 : -5.784E+01 1.23 -5.856E+01 60 199s 74 : -5.784E+01 1.23 -5.856E+01 61 200s 75 : -5.784E+01 1.23 -5.856E+01 62 200s 76 : -5.784E+01 1.23 -5.856E+01 63 204s 77 : -5.784E+01 1.23 -5.856E+01 64 206s 78 : -5.784E+01 1.23 -5.856E+01 65 208s 79 : -5.784E+01 1.21 -5.856E+01 66 208s 80 : -5.784E+01 1.21 -5.856E+01 67 209s 81 : -5.784E+01 1.21 -5.856E+01 68 211s 82 : -5.784E+01 1.21 -5.856E+01 69 211s 83 : -5.784E+01 1.21 -5.856E+01 70 212s 84 : -5.784E+01 1.21 -5.856E+01 71 215s 85 : -5.784E+01 1.21 -5.856E+01 72 216s 86 : -5.784E+01 1.21 -5.856E+01 73 217s 87 : -5.784E+01 1.21 -5.856E+01 74 217s 88 : -5.784E+01 1.21 -5.856E+01 75 218s 89 : -5.784E+01 1.21 -5.856E+01 76 218s 90 : -5.784E+01 1.21 -5.856E+01 77 220s 91 : -5.784E+01 1.21 -5.856E+01 78 225s 92 : -5.784E+01 1.21 -5.856E+01 79 225s 93 : -5.784E+01 1.21 -5.856E+01 80 226s 94 : -5.784E+01 1.21 -5.856E+01 81 226s Restoration phase is called at point that is almost feasible, with constraint violation 5.737015e-11. Abort. 95 : -5.784E+01 1.21 -5.855E+01 82 227s 96 : -5.784E+01 1.21 -5.855E+01 83 231s 97 : -5.784E+01 1.21 -5.855E+01 84 233s 98 : -5.784E+01 1.21 -5.855E+01 85 238s 99 : -5.784E+01 1.20 -5.855E+01 86 240s 100 : -5.784E+01 1.20 -5.855E+01 87 242s * Finished. Cost: -57.838 Gap: 1.2%* Termination due to iteration limit * Timing: 75% spent in upper solver (100 problems solved)* 1% spent in lower solver (99 problems solved)* 20% spent in LP-based domain reduction (10621 problems solved)* 4% spent in upper heuristics (5374 candidates tried)ans = Johan Löfberg
Jul 29, 2020, 7:25:56 AM7/29/20
to YALMIP
and scip finds a similiar solution in just a couple of seconds. Sure it terminates after 20 seconds or so with iteration limit, but it has found a solution within 1% global optimality
Jane
Jul 31, 2020, 3:04:47 PM7/31/20
to YALMIP
Thank you very much for your explanation.
Well, it seems that baron is not free. I want to use it at my university for academic purposes.
When I use 'bmibnb' solver, I get the following message and the solver is not started. I checked to see if it is installed and it was.
I do not have
GUROBI installed, and I was wondering if that is the reason. I changed 'bmibnb.lowersolver' and 'bmibnb.lpsolver' to ipopt and still have the same problem.
* Timing: 0% spent in upper solver (0 problems solved)
* 0% spent in lower solver (1 problems solved)
* 0% spent in LP-based domain reduction (0 problems solved)
* 0% spent in lower solver (1 problems solved)
* 0% spent in LP-based domain reduction (0 problems solved)
Johan Löfberg
Jul 31, 2020, 3:44:07 PM7/31/20
to YALMIP
To use bmibnb, you must have a fast LP solver (gurobi/cplex/mosek, maybe scip)
It looks like something crashed, but you haven't showed everything displayed, nor have you shown what is returned with diagnostic codes etc
When I run the original model, it starts with a 2% gap or so (using the develop branch, so might be different as it has been improved)
optimize(F,-obj,sdpsettings('solver','bmibnb'))* Starting YALMIP global branch & bound.* Upper solver : fmincon* Lower solver : GUROBI* LP solver : GUROBI* -Extracting bounds from model* -Perfoming root-node bound propagation* -Calling upper solver (no solution found)* -Branch-variables : 144* -More root-node bound-propagation* -Performing LP-based bound-propagation * -And some more root-node bound-propagation* Starting the b&b process Node Upper Gap(%) Lower Open Time 1 : -1.099E+02 1.89 -1.121E+02 2 58s Improved solution found by upper solver
optimize(F,-obj,sdpsettings('solver','bmibnb','bmibnb.upper','fmincon'))* Starting YALMIP global branch & bound.* Upper solver : fmincon* Lower solver : GUROBI* LP solver : GUROBI* -Extracting bounds from model* -Perfoming root-node bound propagation* -Calling upper solver (no solution found)* -Branch-variables : 72* -More root-node bound-propagation* -Performing LP-based bound-propagation * -And some more root-node bound-propagation* Starting the b&b process Node Upper Gap(%) Lower Open Time 1 : Inf NaN -1.116E+02 2 48s 2 : Inf NaN -1.116E+02 3 112s both models are awfylly slow though with fmincon which is default. ipopt is faster in solving the upper bound problems. still struggles in finding feasible solution (perhaps not too surprising as there will be a lot of nonlinear constraints with empty interior when the binaries are fixed in the nonlinear upper bound ptroblems, sounds plausible that many solvers will struggle with that)
optimize(F,-obj,sdpsettings('solver','bmibnb','bmibnb.upper','ipopt'))* Starting YALMIP global branch & bound.* Upper solver : ipopt* Lower solver : GUROBI* LP solver : GUROBI* -Extracting bounds from model* -Perfoming root-node bound propagation* -Calling upper solver (no solution found)* -Branch-variables : 72* -More root-node bound-propagation* -Performing LP-based bound-propagation * -And some more root-node bound-propagation* Starting the b&b process Node Upper Gap(%) Lower Open Time 1 : Inf NaN -1.116E+02 2 3s 2 : Inf NaN -1.116E+02 3 7s 3 : Inf NaN -1.116E+02 4 11s 4 : Inf NaN -1.116E+02 5 15s 5 : Inf NaN -1.116E+02 6 19s
You will have to spend a lot of though on creating better models. One thing I would try would be to linearize f = y*(log(a)-log(b)) not by the MILP you have but by introducing new variables c and d, and then have f = log(c)-log(d) and then use big-M to represent that if y = 1 then (c=a, d=b) if y == 0 then (c ==1, d == 1). That way, the big-M model will not introduce any nonlinearities in the constraints. or some variant where log(a+b)-log(b) is written as log(1+q), q*b == a instead, trading a difference of two logs with a bilinear term instead.
Some quick playing with these things indicates to me that this is a pretty hard problem
Reply all
Reply to author
Forward
0 new messages