Solving Non-convex MINLP - postponed nodes
回答済み
Hi,
I have implemented a branch and cut algorithm where my subproblems are mixed integer program with bilinear objective function. Here is the groubi log of my subproblem:
Gurobi Optimizer version 11.0.3 build v11.0.3rc0 (mac64[x86] - Darwin 20.6.0 20G1427)
CPU model: Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz
Thread count: 4 physical cores, 8 logical processors, using up to 1 threads
Optimize a model with 64 rows, 262 columns and 566 nonzeros
Model fingerprint: 0x41222325
Model has 96 quadratic objective terms
Variable types: 214 continuous, 48 integer (48 binary)
Coefficient statistics:
Matrix range [1e+00, 4e+01]
Objective range [1e+00, 2e+01]
QObjective range [2e+00, 2e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 3e+00]
Found heuristic solution: objective -2.06000e+11
Found heuristic solution: objective -0.0000000
Variable types: 406 continuous, 144 integer (144 binary)
Root relaxation: unbounded, 141 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 postponed 0 -0.00000 - - - 0s
0 0 postponed 0 -0.00000 - - - 0s
0 2 postponed 0 -0.00000 - - - 0s
* 7 7 4 10.0000000 - - 36.9 0s
* 140 48 3 20.0000000 - - 12.2 0s
14365 57 cutoff 55 20.00000 - - 4.2 5s
30410 32 cutoff 45 20.00000 - - 4.0 10s
Explored 36761 nodes (146451 simplex iterations) in 11.96 seconds (4.86 work units)
Thread count was 1 (of 8 available processors)
Solution count 4: 20 10 -0 -2.06e+11
Optimal solution found (tolerance 1.00e-04)
Best objective 2.000000000000e+01, best bound 2.000000000000e+01, gap 0.0000%
As you can see, many nodes are postponed and the solver cannot find the best objective bound which massively reduce the computational performance. Do you know how can I resolve this issue? to me the problem is not hard and with proper branching on the binary variable, I expect a good bound. I tried to set priority branching but for the binary variable but it did not help.
I alternatively linearized the objective function (bilinear term is multiplication of binary and continuous variable) by introducing binary variables and bigM constraint. Which improve the performance but have a weak relaxation. I am hoping to resolve the postponed node issue in the original formulation.
Thanks
-
Hi Seyedkianoush,
a postponed node is a node that Gurobi was not able to solve for whatever reason. It may be that a node is unbounded when it shouldn't or some numerical trouble were encountered.
For nonlinear models, a postponed node almost always indicates that some nonlinear term is unbounded and Gurobi was not able to deduce tight finite bound for variables participating in such nonlinear term.
Looking at the coefficient statistics of your model, you can see the line
Bounds range [1e+00, 1e+00]
which should indicate that all variables are free variables, i.e., they have no lower and upper bounds. Since Gurobi is a global solver, tight finite lower and upper bounds for all variables participating in nonlinear terms are necessary for a proof of optimality. In your particular case, it means that you should try to provide tight finite upper and lower bounds for every variable occurring in a quadratic term.
If this does not help, then you might want to consider sharing the model such that we have a close look. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
You should also try upgrading to Gurobi version 12.
Best regards,
Jaromił1
サインインしてコメントを残してください。
コメント
1件のコメント