Skip to main content

Unexpected improvements to an LP file with zero objective function

Answered
Marcus Garvie
Gurobi-versary
Curious
Conversationalist

Hi 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.

0

Comments

6 comments

Date Votes
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Marcus Garvie
    Gurobi-versary
    Curious
    Conversationalist

    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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Marcus Garvie
    Gurobi-versary
    Curious
    Conversationalist

    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.lp
    Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (mac64[arm])
    Obj: 7733 rows, 1372296 columns, 50774952 nonzeros
    Thread count: 10 physical cores, 10 logical processors, using up to 10 threads
    Optimize a model with 7733 rows, 1372296 columns and 50774952 nonzeros
    Variable 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 columns
    Presolve time: 52.23s
    Presolved: 7229 rows, 1274592 columns, 46970412 nonzeros
    Variable types: 0 continuous, 1274592 integer (1274592 binary)
     
    Concurrent LP optimizer: primal simplex, dual simplex, and barrier
    Showing barrier log only...
    Root barrier log...
    Ordering time: 0.03s
    Barrier statistics:
     AA' NZ     : 1.412e+06
     Factor NZ  : 3.275e+06 (roughly 500 MB of memory)
     Factor Ops : 2.402e+09 (less than 1 second per iteration)
     Threads    : 8
     
                      Objective                Residual
    Iter       Primal          Dual         Primal    Dual     Compl     Time
       0   8.56184000e+04  2.09000000e+02  7.52e+02 7.52e-14  2.50e-03    85s
       1   9.91639026e+02  2.19176780e+02  6.89e+00 8.88e-16  2.68e-05    85s
       2   2.47693217e+02  2.16687891e+02  3.41e-01 9.58e-16  3.97e-06    86s
       3   2.09000000e+02  2.09747374e+02  6.33e-14 8.88e-16  2.93e-07    86s
       4   2.09000000e+02  2.09000747e+02  5.71e-14 8.88e-16  2.93e-10    87s
       5   2.09000000e+02  2.09000000e+02  1.67e-13 8.88e-16  2.95e-16    87s
     
    Barrier solved model in 5 iterations and 87.37 seconds (196.13 work units)
    Optimal objective 2.09000000e+02
     
      Building initial crossover basis                                97s
      Building initial crossover basis                               100s
      Building initial crossover basis                               105s
      Building initial crossover basis                               110s
     
    Root crossover log...
     
        1350 variables added to crossover basis                      115s
        4140 variables added to crossover basis                      120s
     
         289 DPushes remaining with DInf 0.0000000e+00               122s
           0 DPushes remaining with DInf 0.0000000e+00               123s
     
           1 PPushes remaining with PInf 0.0000000e+00               123s
           0 PPushes remaining with PInf 0.0000000e+00               123s
     
      Push phase complete: Pinf 0.0000000e+00, Dinf 2.9062210e-09    123s
    Root simplex log...
     
    Iteration    Objective       Primal Inf.    Dual Inf.      Time
         128    2.0900000e+02   0.000000e+00   0.000000e+00    123s
         128    2.0900000e+02   0.000000e+00   0.000000e+00    124s
     
    Solved with barrier
     
    Root relaxation: objective 2.090000e+02, 128 iterations, 58.47 seconds (97.70 work units)
     
        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
     
         0     0  209.00000    0 4736          -  209.00000      -     -  416s
         0     0  209.00000    0 4924          -  209.00000      -     - 2605s
         0     0  209.00000    0 4924          -  209.00000      -     - 3232s
         0     0  209.00000    0 4921          -  209.00000      -     - 5966s
         0     0  209.00000    0 4919          -  209.00000      -     - 7832s
         0     0  209.00000    0 4927          -  209.00000      -     - 10164s
         0     0  209.00000    0 4922          -  209.00000      -     - 11850s
         0     0  209.00000    0 4916          -  209.00000      -     - 13135s
         0     0  209.00000    0 4924          -  209.00000      -     - 14284s
         0     0  209.00000    0 4930          -  209.00000      -     - 16081s
         0     0  209.00000    0 4942          -  209.00000      -     - 17815s
         0     0  209.00000    0 5101          -  209.00000      -     - 18628s
         0     0  209.00000    0 4742          -  209.00000      -     - 19445s
         0     0  209.00000    0 5053          -  209.00000      -     - 20425s
         0     0  209.00000    0 4970          -  209.00000      -     - 21358s
         0     0  209.00000    0 4928          -  209.00000      -     - 23743s
         0     0  209.00000    0 4947          -  209.00000      -     - 25540s
         0     0  209.00000    0 5029          -  209.00000      -     - 27184s
         0     0  209.00000    0 5012          -  209.00000      -     - 28992s
         0     0  209.00000    0 5100          -  209.00000      -     - 30796s
         0     0  209.00000    0 5027          -  209.00000      -     - 31820s
         0     0  209.00000    0 5106          -  209.00000      -     - 33856s
         0     0  209.00000    0 5106          -  209.00000      -     - 35385s
         0     2  209.00000    0 5106          -  209.00000      -     - 47056s
         1     5  209.00000    1 4981          -  209.00000      - 13027 47493s
         3     8  209.00000    2 5041          -  209.00000      -  6034 48181s
         7    16  209.00000    3 5036          -  209.00000      -  7034 49341s
        15    26  209.00000    4 4984          -  209.00000      -  8094 53714s
        25    36  209.00000    5 5054          -  209.00000      - 13888 54131s
        35    46  209.00000    5 5045          -  209.00000      - 11531 54484s
        45    56  209.00000    6 5050          -  209.00000      - 10120 54749s
        55    73  209.00000    7 5033          -  209.00000      -  9030 55083s
        72    84  209.00000    8 5049          -  209.00000      -  7471 55489s
        83    98  209.00000    9 5062          -  209.00000      -  7297 55856s
        97   149  209.00000   10 5072          -  209.00000      -  6780 56843s
       148   243  209.00000   12 5077          -  209.00000      -  6148 61607s
       246   438  209.00000   19 5053          -  209.00000      -  5821 67016s
       447   659  209.00000   28 4953          -  209.00000      -  5985 72875s
       670   877  209.00000   45 4831          -  209.00000      -  6019 80608s
       888  1014  209.00000   61 4727          -  209.00000      -  6459 91951s
      1029  1151  209.00000   72 4616          -  209.00000      -  7096 117062s
      1172  1280  209.00000   94 4378          -  209.00000      -  7912 126992s
      1305  1344  209.00000  108 4334          -  209.00000      -  8493 134686s
      1387  1446  209.00000  115 4306          -  209.00000      -  8425 143648s
      1503  1635  209.00000  128 4222          -  209.00000      -  9253 156614s
      1704  1785  209.00000  144 4005          -  209.00000      - 10259 163621s
      1860  1916  209.00000  154 3814          -  209.00000      - 11293 171141s
      1999  2037  209.00000  169 3670          -  209.00000      - 11833 179167s
      2128  2132  209.00000  173 3548          -  209.00000      - 12251 235864s
    0
  • Marcus Garvie
    Gurobi-versary
    Curious
    Conversationalist

    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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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.

Didn't find what you were looking for?

New post