BestBd NaN for MILP and When will BestBd be NaN?
AnsweredHello
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 [1e01, 1e+02]
Objective range [4e01, 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 nonbinary 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 xvariables 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