Presolve for a very large LP

Answered

July 19, 2023 18:09 Edited

Hello,

I am trying to solving a very large LP, I am confused why the number of constraints removed during presolve is lager than the number of constraints in the original model? Please read the following log information. Besides, is there any suggestions for solving such large LP? I am using dual simplex to solve now and I have a norm constraint in model.

Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (linux64)
Thread count: 18 physical cores, 36 logical processors, using up to 18 threads
Optimize a model with 4222911 rows, 4227604 columns and 967656368 nonzeros
Model fingerprint: 0x44eb37ad
Model has 1 general constraint
Variable types: 4227604 continuous, 0 integer (0 binary)
Coefficient statistics:
  Matrix range [5e-06, 2e+06]
  Objective range [1e+03, 1e+03]
  Bounds range [0e+00, 0e+00]
  RHS range [1e+00, 1e+00]
Presolve removed 0 rows and 0 columns (presolve time = 66s) ...
Presolve removed 0 rows and 0 columns (presolve time = 73s) ...
Presolve removed 0 rows and 0 columns (presolve time = 81s) ...
Presolve removed 0 rows and 0 columns (presolve time = 88s) ...
Presolve removed 0 rows and 0 columns (presolve time = 98s) ...
Presolve removed 3495041 rows and 0 columns (presolve time = 283s) ...
Presolve removed 3495041 rows and 0 columns (presolve time = 463s) ...
Presolve removed 3495041 rows and 0 columns (presolve time = 470s) ...
Presolve removed 3495041 rows and 0 columns (presolve time = 480s) ...
Presolve removed 3495041 rows and 3495041 columns (presolve time = 481s) ...
Presolve removed 3495041 rows and 3495041 columns (presolve time = 488s) ...
Presolve removed 3495041 rows and 3495041 columns (presolve time = 698s) ...
Presolve removed 3495041 rows and 3495041 columns (presolve time = 1066s) ...
Presolve removed 3495041 rows and 3495041 columns (presolve time = 1239s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 1784s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 1798s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 1993s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2115s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2120s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2125s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2130s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2135s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2140s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2145s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2150s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2155s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2160s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2165s) ...
Presolve removed 3495041 rows and 3496469 columns (presolve time = 2348s) ...
Presolve removed 3497727 rows and 3499155 columns (presolve time = 2496s) ...
Presolve removed 3497727 rows and 3499155 columns (presolve time = 2503s) ...
Presolve removed 3497727 rows and 3499155 columns (presolve time = 2522s) ...
Presolve removed 3497727 rows and 3499155 columns (presolve time = 2525s) ...
Presolve removed 3497727 rows and 3499155 columns (presolve time = 2532s) ...
Presolve removed 3497727 rows and 3499155 columns (presolve time = 2541s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 2715s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 2727s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 2734s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 2743s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 2748s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 2875s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3395s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3516s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3529s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3686s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3813s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3815s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3820s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3826s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3830s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3835s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3840s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3845s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3850s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3855s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3860s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3865s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3870s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3875s) ...
Presolve removed 7720638 rows and 3499155 columns (presolve time = 3880s) ...

Related to

Comments

3 comments

Jaromił Najman

Gurobi Staff

July 20, 2023 14:05
Could you please share the rest of the log? In particular what is reported after presolve is done?
0
Dong Han

July 20, 2023 14:17
Sure, here is the log information for solving the problem successfully.

Set parameter Username

Academic license - for non-commercial use only - expires 2023-09-23

Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (linux64)

Thread count: 18 physical cores, 36 logical processors, using up to 18 threads

Optimize a model with 4222911 rows, 4227604 columns and 967656368 nonzeros

Model fingerprint: 0x44eb37ad

Model has 1 general constraint

Variable types: 4227604 continuous, 0 integer (0 binary)

Coefficient statistics:

Matrix range [5e-06, 2e+06]

Objective range [1e+03, 1e+03]

Bounds range [0e+00, 0e+00]

RHS range [1e+00, 1e+00]

Presolve removed 0 rows and 0 columns (presolve time = 66s) ...

Presolve removed 0 rows and 0 columns (presolve time = 73s) ...

Presolve removed 0 rows and 0 columns (presolve time = 81s) ...

Presolve removed 0 rows and 0 columns (presolve time = 88s) ...

Presolve removed 0 rows and 0 columns (presolve time = 98s) ...

Presolve removed 3495041 rows and 0 columns (presolve time = 283s) ...

Presolve removed 3495041 rows and 0 columns (presolve time = 463s) ...

Presolve removed 3495041 rows and 0 columns (presolve time = 470s) ...

Presolve removed 3495041 rows and 0 columns (presolve time = 480s) ...

Presolve removed 3495041 rows and 3495041 columns (presolve time = 481s) ...

Presolve removed 3495041 rows and 3495041 columns (presolve time = 488s) ...

Presolve removed 3495041 rows and 3495041 columns (presolve time = 698s) ...

Presolve removed 3495041 rows and 3495041 columns (presolve time = 1066s) ...

Presolve removed 3495041 rows and 3495041 columns (presolve time = 1239s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 1784s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 1798s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 1993s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2115s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2120s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2125s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2130s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2135s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2140s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2145s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2150s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2155s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2160s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2165s) ...

Presolve removed 3495041 rows and 3496469 columns (presolve time = 2348s) ...

Presolve removed 3497727 rows and 3499155 columns (presolve time = 2496s) ...

Presolve removed 3497727 rows and 3499155 columns (presolve time = 2503s) ...

Presolve removed 3497727 rows and 3499155 columns (presolve time = 2522s) ...

Presolve removed 3497727 rows and 3499155 columns (presolve time = 2525s) ...

Presolve removed 3497727 rows and 3499155 columns (presolve time = 2532s) ...

Presolve removed 3497727 rows and 3499155 columns (presolve time = 2541s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 2715s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 2727s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 2734s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 2743s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 2748s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 2875s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3395s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3516s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3529s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3686s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3813s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3815s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3820s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3826s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3830s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3835s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3840s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3845s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3850s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3855s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3860s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3865s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3870s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3875s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 3880s) ...

Presolve removed 7720638 rows and 3499155 columns (presolve time = 4019s) ...

Presolve removed 7721483 rows and 3500000 columns (presolve time = 4146s) ...

Presolve removed 7801483 rows and 3580000 columns (presolve time = 4150s) ...

Presolve removed 7831483 rows and 3610000 columns (presolve time = 4156s) ...

Presolve removed 7851483 rows and 3630000 columns (presolve time = 4161s) ...

Presolve removed 7871483 rows and 3650000 columns (presolve time = 4166s) ...

Presolve removed 7891483 rows and 3670000 columns (presolve time = 4172s) ...

Presolve removed 7901483 rows and 3680000 columns (presolve time = 4175s) ...

Presolve removed 7921483 rows and 3700000 columns (presolve time = 4182s) ...

Presolve removed 7931483 rows and 3710000 columns (presolve time = 4185s) ...

Presolve removed 7951483 rows and 3730000 columns (presolve time = 4192s) ...

Presolve removed 7961483 rows and 3740000 columns (presolve time = 4196s) ...

Presolve removed 7981483 rows and 3760000 columns (presolve time = 4202s) ...

Presolve removed 7991483 rows and 3770000 columns (presolve time = 4206s) ...

Presolve removed 8011483 rows and 3790000 columns (presolve time = 4213s) ...

Presolve removed 8021483 rows and 3800000 columns (presolve time = 4216s) ...

Presolve removed 8051483 rows and 3830000 columns (presolve time = 4220s) ...

Presolve removed 8101483 rows and 3880000 columns (presolve time = 4489s) ...

Presolve removed 8111483 rows and 3890000 columns (presolve time = 4492s) ...

Presolve removed 8121483 rows and 3900000 columns (presolve time = 4495s) ...

Presolve removed 8141483 rows and 3920000 columns (presolve time = 4501s) ...

Presolve removed 8161483 rows and 3940000 columns (presolve time = 4507s) ...

Presolve removed 8171483 rows and 3950000 columns (presolve time = 4510s) ...

Presolve removed 8191483 rows and 3970000 columns (presolve time = 4516s) ...

Presolve removed 8211483 rows and 3990000 columns (presolve time = 4521s) ...

Presolve removed 8231483 rows and 4010000 columns (presolve time = 4527s) ...

Presolve removed 8251483 rows and 4030000 columns (presolve time = 4531s) ...

Presolve removed 8271483 rows and 4050000 columns (presolve time = 4535s) ...

Presolve removed 8301483 rows and 4080000 columns (presolve time = 4541s) ...

Presolve removed 8341483 rows and 4120000 columns (presolve time = 4546s) ...

Presolve removed 8401483 rows and 4180000 columns (presolve time = 4550s) ...

Presolve removed 8445822 rows and 4224339 columns (presolve time = 5052s) ...

Presolve removed 8445822 rows and 4224339 columns (presolve time = 5330s) ...

Presolve removed 8445822 rows and 4227604 columns (presolve time = 5719s) ...

Presolve removed 8445822 rows and 4227604 columns (presolve time = 5900s) ...

Presolve removed 8445822 rows and 4227604 columns (presolve time = 5991s) ...

Presolve removed 9173692 rows and 4227604 columns (presolve time = 6082s) ...

Presolve removed 9173692 rows and 4227604 columns (presolve time = 6309s) ...

Presolve removed 9173692 rows and 4227604 columns (presolve time = 6499s) ...

Presolve removed 4222911 rows and 4227604 columns

Presolve time: 6499.41s

Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 6521.58 seconds (1003.64 work units)

Thread count was 1 (of 36 available processors)

Solution count 1: 1000

Optimal solution found (tolerance 1.00e-04)

Best objective 1.000000000000e+03, best bound 1.000000000000e+03, gap 0.0000%

Successfully solving model :)
0
Chung-Kyun Han

Gurobi Staff

July 21, 2023 05:32 Edited
Hi Dong Han

Thank you for reaching out and sharing the log.

Your first question is

“why the number of constraints removed during presolve is lager than the number of constraints in the original model?”.

You have 4222911 linear constraints + 1 norm constraint.
Upon the norm constraint and other general constraints, here is an excerpt from Constraints | Simple General Constraints.

Note that adding any of these constraints to an otherwise continuous model will transform it into a MIP

As stated above, each general constraint has an equivalent MIP formulation that consists of linear and SOS constraints, and possibly auxiliary variables.

This means that Gurobi would reformulate the norm constraint into its MIP equivalence by adding extra constraints/variables.

Here are a few general parameter suggestions that might help to speed up large LP problems.

1. Set Method parameter as 2 (=barrier) → ‘barrier algorithm’ works well for the large and sparse matrix.
2. Try other helpful parameters regarding resolve.
    2.1. Presolve ( < 2, if the value is 2, Gurobi will spend more time on resolve)
    2.2. PreSparsify
    2.3. Symmetry

As explained at the KB article "What does "Presolve: All rows and columns removed" mean?", Gurobi presolve manages to solve the model to optimality in 6521.58 seconds. You can experiment with setting Presolve to 1 to see whether it helps to reduce the runtime or not. The setting makes Gurobi spend less time in presolve, so Gurobi may not be able to find the optimal solution in presolve. However, the total runtime might be reduced by leaving some work for the branch-and-cut algorithm.

Please also note that you are using Gurobi version 9.5.2. You can try our latest version 10.0.2.

If you have any further questions, feel free to leave messages.

Best regards,
Chung-Kyun Han
0

Please sign in to leave a comment.

Presolve for a very large LP

Comments

Didn't find what you were looking for?