Unexpected improvements to an LP file with zero objective function
AnsweredHi everyone,
I've been trying to solve a very large undetermined binary linear system in LP format. So the objective function is zero (or constant). Thus I'm really just looking for a feasible solution. Up to this point Gurobi has really struggled to search for a solution (I don't have a solution yet). I even tried tuning a smaller related problem and using those parameters. It occurred to me that when the objective function is zero that maybe Gurobi is running 'blind', so I tried to think about a way of artificially adding an objective function. Now for my problem I happen to know that when a feasible solution is found then the sum of all the variables is equal to some number N. So I edited the objective function to maximize (or minimize) the sum of all the variables. When I make this change on the smaller problem (with N = 66) the solution is found very fast (and the objective value is of course = 66). I'm currently trying this approach on the bigger problem. So my question is as follows: why does such a simple change to the objective function lead to reduced solution time? I called this change 'artificial' because the equality constraints actually imply this condition, so I'm not actually telling Gurobi anything new.
Thank you, Marcus.
-
Hi Marcus,
why does such a simple change to the objective function lead to reduced solution time?
Gurobi is able to use the direction of the objective function to better "steer" through the search space and find feasible solution more easily. Thus providing a non-trivial objective function often helps when one actually only wants to find a feasible point.
Since you are looking for feasible points only, you might want to try the "No Relaxation heuristic" by setting the parameter NoRelHeurTime and experimenting with the MIPFocus, Heuristics, and RINS parameters. You might also be interested in having a look at Constraint Programming.
Best regards,
Jaromił0 -
Hi Jaromił,
thank you for your reply. I'm not very knowledgeable about Gurobi so I was wondering if you could expand a little on some possible values for the parameters you mention.
First a little context in case it helps. As I mentioned in my last post, I'm solving a pure binary LP problem. There are 1,572,516 variables and 7,733 equality constraints (and no objective function, unless I decide to add one as described before). All variables are binary.
You suggest setting the NoRelHeurTime parameter. The documentation doesn't say a lot about that parameter. Googling prior posts I found one post that suggested setting that to 2 hours to try and get a feasible solution. I'm running my problem with that right now. (Should I stick with the zero objective function or use the 'artificial' one that gave me speedup on the smaller problem?) I'm also using MIPFocus=1 as that seems to be the setting for "finding a good quality feasible solution". I'm not sure about the other parameters, although I am using Method=3 because someone else suggested that as my problem doesn't seem to benefit from adding more threads?
The issue I have with choosing good parameter settings is that it takes Gurobi a long time to get going on my problem. It is very slow after getting to 'Root relaxation' and then spends a long time at the zero node. I've tried various setting and got no solution after a week of runtime.
Any advice would be appreciated.
Thank you,
Marcus.
0 -
Hi Marcus,
First a little context in case it helps. As I mentioned in my last post, I'm solving a pure binary LP problem. There are 1,572,516 variables and 7,733 equality constraints (and no objective function, unless I decide to add one as described before). All variables are binary.
This is a very large problem. Thus, it is not surprising that finding a feasible solution point may take a long time. Could you share the first ~20 lines of the LOG file?
Since you are interested in a feasible solution only, you should set the parameter SolutionLimit=1 which will make Gurobi terminate as soon as a first feasible solution is found.
You suggest setting the NoRelHeurTime parameter. The documentation doesn't say a lot about that parameter. Googling prior posts I found one post that suggested setting that to 2 hours to try and get a feasible solution. I'm running my problem with that right now. (Should I stick with the zero objective function or use the 'artificial' one that gave me speedup on the smaller problem?)
The No Relaxation heuristic searches for feasible points before solving the root node relaxation. It often performs well if the root relaxation is expensive to solve. The first phase of the heuristic shows how "far" the relaxation is from becoming feasible, while the second phase then lists feasible solutions that are found. The parameter NoRelHeurTime sets the number of seconds one is willing to spend in this heuristic. Since you have observed that providing an objective function benefits performance, I would stick to this approach and provide a non-trivial objective function.
I'm also using MIPFocus=1 as that seems to be the setting for "finding a good quality feasible solution".
Setting MIPFocus=1 should be the correct choice, because you are interested in a feasible solution only. Nevertheless, sometimes it might be better to set MIPFocus=2 or 3 but this has to be tested.
I'm not sure about the other parameters, although I am using Method=3 because someone else suggested that as my problem doesn't seem to benefit from adding more threads?
Method=3 makes Gurobi use the primal and dual Simplex and the Barrier algorithm in parallel when solving the root node relaxation. If your root node relaxation is solved quickly, then usually the parameter can be ignored. For MIPs, more threads usually help more if the B&B tree is large.
The Heuristics parameter controls time spent for feasible point heuristics. In your case, you could try setting it to 1 to make Gurobi spend maximum effort for finding feasible points.
The issue I have with choosing good parameter settings is that it takes Gurobi a long time to get going on my problem. It is very slow after getting to 'Root relaxation' and then spends a long time at the zero node. I've tried various setting and got no solution after a week of runtime.
Any advice would be appreciated.
You should try formulating a smaller version of your model and working with this smaller version first. You could then use Gurobi's automatic parameter tuning tool to find suitable parameters for the smaller version. Given the complexity and size of the tuned model, it might be necessary to run the tuning tool for a couple of days to find good parameters.
Best regards,
Jaromił0 -
Hi Jaromił,
gosh, there is a lot to try. I do have a smaller problem but it seems to be solved vey quickly and doesn't suffer from the same delays at the root node. I did try tuning the smaller model (not 2 days though) but I'm not sure how well those parameters will also work for the big problem. I will try some of your suggestions, thank you. I have attached the log for the last 3 days runtime of my big problem ...
Thank you,
Marcus.
marcusgarvie@Marcuss-MacBook-Pro LPfiles % gurobi_cl ResultFile=subregion6_alt.sol Method=3 subregion6_alt.lpGurobi Optimizer version 9.5.0 build v9.5.0rc5 (mac64[arm])Obj: 7733 rows, 1372296 columns, 50774952 nonzerosThread count: 10 physical cores, 10 logical processors, using up to 10 threadsOptimize a model with 7733 rows, 1372296 columns and 50774952 nonzerosVariable types: 0 continuous, 1372296 integer (1372296 binary)Presolve removed 96 rows and 0 columns (presolve time = 6s) ...Presolve removed 96 rows and 97704 columns (presolve time = 10s) ...Presolve removed 96 rows and 97704 columns (presolve time = 15s) ...Presolve removed 96 rows and 97704 columns (presolve time = 20s) ...Presolve removed 96 rows and 97704 columns (presolve time = 25s) ...Presolve removed 504 rows and 97704 columns (presolve time = 30s) ...Presolve removed 504 rows and 97704 columns (presolve time = 35s) ...Presolve removed 504 rows and 97704 columns (presolve time = 40s) ...Presolve removed 504 rows and 97704 columns (presolve time = 45s) ...Presolve removed 504 rows and 97704 columns (presolve time = 51s) ...Presolve removed 504 rows and 97704 columnsPresolve time: 52.23sPresolved: 7229 rows, 1274592 columns, 46970412 nonzerosVariable types: 0 continuous, 1274592 integer (1274592 binary)Concurrent LP optimizer: primal simplex, dual simplex, and barrierShowing barrier log only...Root barrier log...Ordering time: 0.03sBarrier statistics:AA' NZ : 1.412e+06Factor NZ : 3.275e+06 (roughly 500 MB of memory)Factor Ops : 2.402e+09 (less than 1 second per iteration)Threads : 8Objective ResidualIter Primal Dual Primal Dual Compl Time0 8.56184000e+04 2.09000000e+02 7.52e+02 7.52e-14 2.50e-03 85s1 9.91639026e+02 2.19176780e+02 6.89e+00 8.88e-16 2.68e-05 85s2 2.47693217e+02 2.16687891e+02 3.41e-01 9.58e-16 3.97e-06 86s3 2.09000000e+02 2.09747374e+02 6.33e-14 8.88e-16 2.93e-07 86s4 2.09000000e+02 2.09000747e+02 5.71e-14 8.88e-16 2.93e-10 87s5 2.09000000e+02 2.09000000e+02 1.67e-13 8.88e-16 2.95e-16 87sBarrier solved model in 5 iterations and 87.37 seconds (196.13 work units)Optimal objective 2.09000000e+02Building initial crossover basis 97sBuilding initial crossover basis 100sBuilding initial crossover basis 105sBuilding initial crossover basis 110sRoot crossover log...1350 variables added to crossover basis 115s4140 variables added to crossover basis 120s289 DPushes remaining with DInf 0.0000000e+00 122s0 DPushes remaining with DInf 0.0000000e+00 123s1 PPushes remaining with PInf 0.0000000e+00 123s0 PPushes remaining with PInf 0.0000000e+00 123sPush phase complete: Pinf 0.0000000e+00, Dinf 2.9062210e-09 123sRoot simplex log...Iteration Objective Primal Inf. Dual Inf. Time128 2.0900000e+02 0.000000e+00 0.000000e+00 123s128 2.0900000e+02 0.000000e+00 0.000000e+00 124sSolved with barrierRoot relaxation: objective 2.090000e+02, 128 iterations, 58.47 seconds (97.70 work units)Nodes | Current Node | Objective Bounds | WorkExpl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 209.00000 0 4736 - 209.00000 - - 416s0 0 209.00000 0 4924 - 209.00000 - - 2605s0 0 209.00000 0 4924 - 209.00000 - - 3232s0 0 209.00000 0 4921 - 209.00000 - - 5966s0 0 209.00000 0 4919 - 209.00000 - - 7832s0 0 209.00000 0 4927 - 209.00000 - - 10164s0 0 209.00000 0 4922 - 209.00000 - - 11850s0 0 209.00000 0 4916 - 209.00000 - - 13135s0 0 209.00000 0 4924 - 209.00000 - - 14284s0 0 209.00000 0 4930 - 209.00000 - - 16081s0 0 209.00000 0 4942 - 209.00000 - - 17815s0 0 209.00000 0 5101 - 209.00000 - - 18628s0 0 209.00000 0 4742 - 209.00000 - - 19445s0 0 209.00000 0 5053 - 209.00000 - - 20425s0 0 209.00000 0 4970 - 209.00000 - - 21358s0 0 209.00000 0 4928 - 209.00000 - - 23743s0 0 209.00000 0 4947 - 209.00000 - - 25540s0 0 209.00000 0 5029 - 209.00000 - - 27184s0 0 209.00000 0 5012 - 209.00000 - - 28992s0 0 209.00000 0 5100 - 209.00000 - - 30796s0 0 209.00000 0 5027 - 209.00000 - - 31820s0 0 209.00000 0 5106 - 209.00000 - - 33856s0 0 209.00000 0 5106 - 209.00000 - - 35385s0 2 209.00000 0 5106 - 209.00000 - - 47056s1 5 209.00000 1 4981 - 209.00000 - 13027 47493s3 8 209.00000 2 5041 - 209.00000 - 6034 48181s7 16 209.00000 3 5036 - 209.00000 - 7034 49341s15 26 209.00000 4 4984 - 209.00000 - 8094 53714s25 36 209.00000 5 5054 - 209.00000 - 13888 54131s35 46 209.00000 5 5045 - 209.00000 - 11531 54484s45 56 209.00000 6 5050 - 209.00000 - 10120 54749s55 73 209.00000 7 5033 - 209.00000 - 9030 55083s72 84 209.00000 8 5049 - 209.00000 - 7471 55489s83 98 209.00000 9 5062 - 209.00000 - 7297 55856s97 149 209.00000 10 5072 - 209.00000 - 6780 56843s148 243 209.00000 12 5077 - 209.00000 - 6148 61607s246 438 209.00000 19 5053 - 209.00000 - 5821 67016s447 659 209.00000 28 4953 - 209.00000 - 5985 72875s670 877 209.00000 45 4831 - 209.00000 - 6019 80608s888 1014 209.00000 61 4727 - 209.00000 - 6459 91951s1029 1151 209.00000 72 4616 - 209.00000 - 7096 117062s1172 1280 209.00000 94 4378 - 209.00000 - 7912 126992s1305 1344 209.00000 108 4334 - 209.00000 - 8493 134686s1387 1446 209.00000 115 4306 - 209.00000 - 8425 143648s1503 1635 209.00000 128 4222 - 209.00000 - 9253 156614s1704 1785 209.00000 144 4005 - 209.00000 - 10259 163621s1860 1916 209.00000 154 3814 - 209.00000 - 11293 171141s1999 2037 209.00000 169 3670 - 209.00000 - 11833 179167s2128 2132 209.00000 173 3548 - 209.00000 - 12251 235864s0 -
Hi Jaromił,
just an update. With smaller model I played around with the parameters quite a bit and also tried tuning. With your help I found the following parameter choices gave the greatest improvement in solve time:
Set parameter SolutionLimit to value 1
Set parameter Method to value 4
Set parameter Heuristics to value 1
Set parameter MIPFocus to value 1(The NoRelHeurTime parameter didn't seem to do much.) I also bought a new MacBookPro with the M1 Max chip that speeded up things. On my old laptop with the default parameters the small model took about 31 minutes to solve. Now with the new parameter set, the modified objective function, and the new laptop, I just got a solution in 21 seconds! I'm running the big problem with this new setup, which hopefully leads to a solution eventually.
Thank you,
Marcus.
0 -
Wow! This is indeed a huge improvement. I hope that it also helps with the big problem.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
6 comments