Unexpected numerical issues when running an LP file?
回答済み
Hi everyone,
this is my first post so I apologize in advance for my ignorance. I am running a very large LP problem in Gurobi 9.5 with constant (zero) objective function that arises from a complex combinatorial tiling problem. The LP problem has 1,372,296 binary variables and 7733 constraints. All coefficient values and right hand side values of the undetermined linear system are binary, so I don't understand why I appear to be getting numerical issues. Gurobi gave me the following warning and is running very slowly:
Warning: Markowitz tolerance tightened to 0.03125
The current output is given below. Thank you for any advice you can provide.
Marcus Garvie.
mgarvie@MacBook-Pro-3 LPfiles % gurobi_cl ResultFile=subregion6gurobi.sol subregion6gurobi.lp
Set parameter Username
Set parameter LogFile to value "gurobi.log"
Academic license - for non-commercial use only - expires 2022-02-07
Using license file /Users/mgarvie/gurobi.lic
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (mac64[x86])
Copyright (c) 2021, Gurobi Optimization, LLC
Read LP format model from file subregion6gurobi.lp
Reading time = 15.56 seconds
Obj: 7733 rows, 1372296 columns, 50774952 nonzeros
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 7733 rows, 1372296 columns and 50774952 nonzeros
Model fingerprint: 0x94f1cd71
Variable types: 0 continuous, 1372296 integer (1372296 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [0e+00, 0e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Presolve removed 0 rows and 0 columns (presolve time = 6s) ...
Presolve removed 96 rows and 0 columns (presolve time = 10s) ...
[...]
Presolve removed 504 rows and 97704 columns (presolve time = 100s) ...
Presolve removed 504 rows and 97704 columns
Presolve time: 103.22s
Presolved: 7229 rows, 1274592 columns, 46970412 nonzeros
Variable types: 0 continuous, 1274592 integer (1274592 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 -0.0000000e+00 7.229000e+03 0.000000e+00 120s
1541 -5.5351619e-05 3.464948e+04 0.000000e+00 126s
1871 -6.0660453e-05 3.407856e+04 0.000000e+00 131s
[...]
10554 -2.6172979e-04 1.176195e+04 0.000000e+00 428s
10644 -2.6355113e-04 1.387729e+04 0.000000e+00 432s
Warning: Markowitz tolerance tightened to 0.03125
10724 -2.6529616e-04 1.562320e+05 0.000000e+00 436s
10884 -2.6869428e-04 6.648229e+04 0.000000e+00 444s
[...]
62104 -5.3255785e-04 4.134470e-01 0.000000e+00 3878s
62242 -5.3255951e-04 0.000000e+00 0.000000e+00 3888s
Root relaxation: objective -0.000000e+00, 62242 iterations, 3771.19 seconds (5423.56 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -0.00000 0 4897 - -0.00000 - - 23481s
0 0 -0.00000 0 4922 - -0.00000 - - 27275s
0 0 -0.00000 0 4921 - -0.00000 - - 29847s
0 0 -0.00000 0 4909 - -0.00000 - - 50537s
0 0 -0.00000 0 4900 - -0.00000 - - 51781s
0 0 -0.00000 0 4914 - -0.00000 - - 72026s
0 0 -0.00000 0 4914 - -0.00000 - - 73221s
0 0 -0.00000 0 4912 - -0.00000 - - 93342s
0 0 -0.00000 0 4921 - -0.00000 - - 94421s
0 0 -0.00000 0 4916 - -0.00000 - - 114623s
0 0 -0.00000 0 4926 - -0.00000 - - 115712s
0 0 -0.00000 0 4919 - -0.00000 - - 136047s
0 0 -0.00000 0 4919 - -0.00000 - - 154445s
0 2 -0.00000 0 4919 - -0.00000 - - 254498s
1 4 -0.00000 1 4901 - -0.00000 - 305446 254926s
3 8 -0.00000 2 4978 - -0.00000 - 104212 256352s
-
正式なコメント
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Marcus,
I just edited your post, so people don't hurt their fingers scrolling all the way down - please try editing your posts instead of just copy-pasting everything without any formatting.
This is a pretty hard optimization problem. There are 6.5k variables in each constraint on average and simply forming this sum can introduce significant elimination effects and introduce numerical issues. Just because all our coefficients are within a small range does not guarantee the absence of numerical issues. Also, the message about the reduced Markowitz threshold is not necessarily critical - you do end up solving the root node within one hour. You may want to try some other parameters to improve the performance (e.g. Method, Presolve, etc.)
Cheers,
Matthias0 -
投稿コメントは受け付けていません。
コメント
2件のコメント