BestBd NaN for MILP and When will BestBd be NaN?
Answered
Hello
When I run gurobi for a MILP problem, the BestBd recorded in the log file are NaN when I set the time limit to be 1 hour. Below is a part of the logfile.
Might I know in what situation the BestBd will be NaN what is the meaning of BestBd.
When I search the meaning of BestBd (https://www.gurobi.com/documentation/9.1/refman/mip_logging.html) said "The Objective Bounds section provides information on the best known objective value for a feasible solution (i.e., the objective value of the current incumbent), and the current objective bound provided by leaf nodes of the search tree. The optimal objective value is always between these two values. The third column in this section (Gap) shows the relative gap between the two objective bounds. When this gap is smaller than the MIPGap parameter, optimization terminates."
I am still a little bit confused about the meaning of BestBd. I previously understood the BestBd as the best lower bound for a minimization problem, if that's the case, a relaxed LP version of MILP could already provide a lower bound, so a lower bound should always exist.
So might I know in what situation the BestBd will not exist for the log file?
Thanks for reading and any message or feedback would be highly appreciated.
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 2 postponed 0 0.00000 - - - 0s
* 617 501 190 -119.2999202 - - 45.8 0s
* 631 705 40 -378.6330079 - - 46.5 0s
* 688 705 38 -677.3824816 - - 48.1 0s
* 749 705 38 -726.2572184 - - 52.5 0s
* 7783 4126 156 -731.9009681 - - 23.2 4s
9223 5300 postponed 47 -731.90097 - - 20.3 5s
23317 8743 postponed 166 -731.90097 - - 14.8 10s
*30545 9583 156 -734.7042110 - - 14.9 13s
35912 10093 postponed 162 -734.70421 - - 15.0 15s
*37122 10093 153 -760.3527702 - - 15.0 15s
*40540 10568 155 -767.9548254 - - 15.2 17s
47042 11255 postponed 179 -767.95483 - - 15.4 20s
-
In the first line of the B&B log you see a "postponed" for the objective. This means numerical troubles were encountered during the solution of the relaxation, see also the post What are postponed nodes?
Could you share the first lines of the log file about the model size and statistics?
Which Gurobi Version are you using? You shared a link for version 9.1. This is quite old and there were some improvements w.r.t. numerics in the recent Gurobi versions.0 -
Hello Marika
Thanks for your patient and also thanks for your answer. It's very helpful, and below is the first few lines and last few line of the log file, and the version I am using is 9.5.2.
Thanks for you help
Yin Can
Set parameter TimeLimit to value 3600
Set parameter Presolve to value 0
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (win64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 1301 rows, 965 columns and 4132 nonzeros
Model fingerprint: 0x197aaa26
Model has 216 quadratic objective terms
Variable types: 716 continuous, 249 integer (249 binary)
Coefficient statistics:
Matrix range [1e-01, 1e+02]
Objective range [4e-01, 4e+01]
QObjective range [4e+00, 4e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+02]
Found heuristic solution: objective 360.0003600
Variable types: 718 continuous, 895 integer (465 binary)
Found heuristic solution: objective 0.0000000
8709650 16835 postponed 150 -767.95483 - - 19.1 3565s
8721306 16731 postponed 151 -767.95483 - - 19.1 3570s
8733280 16690 infeasible 150 -767.95483 - - 19.1 3575s
8745310 16622 postponed 151 -767.95483 - - 19.1 3580s
8757355 16544 postponed 157 -767.95483 - - 19.1 3585s
8767040 16488 cutoff 156 -767.95483 - - 19.1 3590s
8779153 16393 cutoff 157 -767.95483 - - 19.1 3595s
8791459 16320 infeasible 155 -767.95483 - - 19.1 3600s0 -
Hello Marika
Sorry for the late reply and again thank you for your help, I really appreciate it.
Might I know whether you mean the lp file, code, the log file, or something else?
Thanks for reading and again thanks for your help
Yin
0 -
Hello Marika
I just upload the file with Filemail(https://www.filemail.com/d/dsuhpqpbdasornc), inside have the code, and the log file. And sorry that I new to the filemail, so please let me know that if there is any trouble with it.
Thanks for reading and thanks for your help
Yin Can
0 -
Hi Yin Can,
Thanks, I could access the files. (The lp file would have been sufficient.)
Your problem can be solved within 1 second without any issues with the default parameter setting.
You have set Presolve=0. What is the reason for this?
Your model does not contain upper bounds for all non-binary variables. The bounds are implicitly defined by the constraints. But if you turn presolve off, the implied bounds are not detected by Gurobi. The root relaxation is considered as unbounded due to the 216 quadratic terms in the objective. A bound cannot be computed.
You should turn presolve on again or you need to set at least the upper bounds for the variables.Best regards,
Marika0 -
Hello Marika
Thank you very much, that helps a lot, at the beginning I want to set Presolve = 0 is want to compare solving time before and after removing the Presolve to see how different it would be.
Might I know if some of the bounds are defined by the constraints rather than the variable definition? Will this always be the case?
Thanks for reading and again thank you very much
Yin Can
0 -
Hi Yin Can,
I am not sure whether I understand your question.
You created the model, so hopefully you know which variable values are reasonable and which are not.
The quadratic terms involve the x and the epsilon variables. All x-variables are binary and hence have an upper bound. Each epsilon variable has the default lower bound of 0 and is part of a constraint you named 16b:epsilon_kit[0,0,0] + epsilon_kit[0,0,1] + epsilon_kit[0,0,2]
+ epsilon_kit[0,0,3] + epsilon_kit[0,1,0] + epsilon_kit[0,1,1]
+ epsilon_kit[0,1,2] + epsilon_kit[0,1,3] + epsilon_kit[0,2,0]
+ epsilon_kit[0,2,1] + epsilon_kit[0,2,2] + epsilon_kit[0,2,3]
+ epsilon_kit[0,3,0] + epsilon_kit[0,3,1] + epsilon_kit[0,3,2]
+ epsilon_kit[0,3,3] + epsilon_kit[0,4,0] + epsilon_kit[0,4,1]
+ epsilon_kit[0,4,2] + epsilon_kit[0,4,3] + epsilon_kit[0,5,0]
+ epsilon_kit[0,5,1] + epsilon_kit[0,5,2] + epsilon_kit[0,5,3] <= 100Hence, we have an upper bound of 100 for each epsilon variable which you can set when adding the variables to the model.
It is sufficient to define the bounds only for the epsilon variables to get a root relaxation and hence a dual bound. But I would recommend to use presolve and not to set the Presolve parameter to 0.Best regards,
Marika0 -
Hello Marika
Thank you very much, your answer is very helpful, I really appreciate it.
Thanks for reading and again thanks for your help
Yin Can
0
Please sign in to leave a comment.
Comments
9 comments