Skip to main content

Unable to find optimal solution for some instances

Answered

Comments

8 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Yaroslav,

    You could try experimenting with most important parameters for MIPs.

    Did you try to not use the Lagrangian relaxation? Moving constraints to the objective function with penalty terms often leads to numerical problems and a weak relaxation.

    Maybe our recent Tech Talk on weak & strong MIP formulations might be of interest.

    Best regards, 
    Jaromił

    1
  • Yaroslav Pylyavskyy
    Conversationalist
    First Question

    Hi Jaromil,

    Thank you for your reply and the resources provided.

    Yes, I tried without Lagrangian relaxation but it gives an infeasible solution. That is why I use it actually, to relax some hard constraints and get a feasible solution.

    Best regards,

    Yaroslav

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Yaroslav,

    When you noticed that your model is infeasible, did you try determining why? The Knowledge Base article How do I determine why my model is infeasible? is helpful here.

    I think that it is best to try to find out why your model is infeasible instead of using Lagrangian relaxation which is often numerically unstable.

    Best regards, 
    Jaromił

    0
  • Yaroslav Pylyavskyy
    Conversationalist
    First Question

    Hi Jaromil,

    Yes, I found which constraints were responsible for infeasibility.

    By the way, for instance 10 I am not using Lagrangian relaxation as the model is feasible. However, the solver gets stuck at 0.15% gap and could run for 2 days without finding optimal solution.

    Which alternative method would you recommend to Lagrangian relaxation?

    Best regards,

    Yaroslav

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Yaroslav,

    I am not aware of any other general method which would fit here. You could try to strengthen your formulation, see our Tech Talk on Weak & Strong Formulations.

    You could also try finding parameters to improve convergence, see Most important parameters for MIP.

    The most important question would be: How accurate is your model? Do you really need a MIPGap that is better than 0.15% or would already a 0.5% or even a 1% gap be enough for your application? For MIPs, closing the last few percent is often the hardest part and takes the longest time.

    Best regards, 
    Jaromił

    1
  • Yaroslav Pylyavskyy
    Conversationalist
    First Question

    Hi Jaromil,

    I just wanted to report to you something odd that I noticed regarding gurobi's performance between pulp and gurobipy. It seems that gurobi's performance is better when using pulp, instead of gurobipy. Please see below logs.

     

    Pulp

    Set parameter Threads to value 7
    Set parameter TimeLimit to value 65
    Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
    Thread count: 4 physical cores, 8 logical processors, using up to 7 threads
    Optimize a model with 9005 rows, 100810 columns and 565110 nonzeros
    Model fingerprint: 0xc55f00a6
    Variable types: 0 continuous, 100810 integer (0 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+01]
      Objective range  [1e+00, 2e+04]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 1e+00]
    Presolve removed 1901 rows and 29 columns
    Presolve time: 0.47s
    Presolved: 7104 rows, 100781 columns, 435452 nonzeros
    Variable types: 0 continuous, 100781 integer (100781 binary)

    Root relaxation: objective 2.021500e+04, 4702 iterations, 0.59 seconds (0.89 work units)

        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

         0     0 20215.0000    0   36          - 20215.0000      -     -    2s
    H    0     0                    270215.00000 20215.0000  92.5%     -    3s
         0     0 20215.0000    0  452 270215.000 20215.0000  92.5%     -    5s
    H    0     0                    50215.000000 20215.0000  59.7%     -    9s
         0     0 20215.0000    0  452 50215.0000 20215.0000  59.7%     -    9s
         0     0 20215.0000    0  665 50215.0000 20215.0000  59.7%     -   17s
    H    0     0                    20245.000000 20215.0000  0.15%     -   18s
         0     0 20215.0000    0  671 20245.0000 20215.0000  0.15%     -   20s
         0     0 20215.0000    0  332 20245.0000 20215.0000  0.15%     -   24s
         0     0 20215.0000    0   47 20245.0000 20215.0000  0.15%     -   34s
         0     0 20215.0000    0  207 20245.0000 20215.0000  0.15%     -   37s
         0     0 20215.0000    0  173 20245.0000 20215.0000  0.15%     -   44s
         0     0 20215.0000    0   44 20245.0000 20215.0000  0.15%     -   48s
         0     0 20215.0000    0   88 20245.0000 20215.0000  0.15%     -   49s
         0     0 20215.0000    0   45 20245.0000 20215.0000  0.15%     -   54s
         0     0 20215.0000    0   22 20245.0000 20215.0000  0.15%     -   55s
         0     2 20215.0000    0   20 20245.0000 20215.0000  0.15%     -   59s
         1     5 20215.0000    1  251 20245.0000 20215.0000  0.15% 10552   65s

    Cutting planes:
      Cover: 85
      Clique: 319
      MIR: 22
      StrongCG: 1
      GUB cover: 58
      Zero half: 39
      RLT: 3

    Explored 3 nodes (180712 simplex iterations) in 65.14 seconds (89.12 work units)
    Thread count was 7 (of 8 available processors)

    Solution count 4: 20245 20245 50215 270215 

    Time limit reached
    Best objective 2.024500000000e+04, best bound 2.021500000000e+04, gap 0.1482%
    Gurobi status= 9

     

    Gurobipy

    Set parameter Threads to value 7
    Set parameter TimeLimit to value 65
    Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
    Thread count: 4 physical cores, 8 logical processors, using up to 7 threads
    Optimize a model with 9005 rows, 100810 columns and 565110 nonzeros
    Model fingerprint: 0xb2ddc278
    Variable types: 0 continuous, 100810 integer (100810 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+01]
      Objective range  [1e+00, 2e+04]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 1e+00]
    Presolve removed 1901 rows and 29 columns
    Presolve time: 0.49s
    Presolved: 7104 rows, 100781 columns, 435452 nonzeros
    Variable types: 0 continuous, 100781 integer (100781 binary)

    Root relaxation: objective 2.021500e+04, 4828 iterations, 0.72 seconds (1.08 work units)

        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

         0     0 20215.0000    0   12          - 20215.0000      -     -    2s
    H    0     0                    140215.00000 20215.0000  85.6%     -    3s
    H    0     0                    60215.000000 20215.0000  66.4%     -    3s
         0     0 20215.0000    0  213 60215.0000 20215.0000  66.4%     -    4s
    H    0     0                    50215.000000 20215.0000  59.7%     -    8s
         0     0 20215.0000    0   41 50215.0000 20215.0000  59.7%     -   13s
         0     0 20215.0000    0  204 50215.0000 20215.0000  59.7%     -   14s
         0     0 20215.0000    0   53 50215.0000 20215.0000  59.7%     -   18s
         0     0 20215.0000    0  146 50215.0000 20215.0000  59.7%     -   21s
         0     0 20215.0000    0   34 50215.0000 20215.0000  59.7%     -   25s
         0     0 20215.0000    0    9 50215.0000 20215.0000  59.7%     -   27s
    H    0     0                    30215.000000 20215.0000  33.1%     -   27s
         0     0 20215.0000    0   28 30215.0000 20215.0000  33.1%     -   41s
         0     0 20215.0000    0  266 30215.0000 20215.0000  33.1%     -   42s
         0     0 20215.0000    0  323 30215.0000 20215.0000  33.1%     -   48s
         0     0 20215.0000    0  142 30215.0000 20215.0000  33.1%     -   54s
         0     0 20215.0000    0  419 30215.0000 20215.0000  33.1%     -   55s
    H    0     0                    20345.000000 20215.0000  0.64%     -   62s
    H    0     0                    20285.000000 20215.0000  0.35%     -   62s
    H    0     0                    20255.000000 20215.0000  0.20%     -   62s
         0     0 20215.0000    0   69 20255.0000 20215.0000  0.20%     -   62s
         0     0 20215.0000    0   18 20255.0000 20215.0000  0.20%     -   64s

    Cutting planes:
      Cover: 126
      Clique: 388
      MIR: 24
      StrongCG: 2
      GUB cover: 111
      Zero half: 67
      Mod-K: 8
      RLT: 4

    Explored 1 nodes (229029 simplex iterations) in 65.02 seconds (77.46 work units)
    Thread count was 7 (of 8 available processors)

    Solution count 7: 20255 20285 20345 ... 140215

    Time limit reached
    Best objective 2.025500000000e+04, best bound 2.021500000000e+04, gap 0.1975%

     

    Any thoughts on why this happens?

    Best regards,

    Yaroslav

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Yaroslav,

    The exact same optimization path is only reproducible for the exact same model and parameters on the same machine, see Is Gurobi Optimizer deterministic? I don't know Pulp well, but it may be possible that the ordering of variables and/or constraints is changed during model building in pulp compared to gurobipy which would already explain the different solution path.

    You can see that the two models you solve are not exactly the same by comparing the fingerprint.

    Best regards, 
    Jaromił

    1
  • Yaroslav Pylyavskyy
    Conversationalist
    First Question

    Thanks Jaromil! Indeed, that makes sense.

    Best regards,

    Yaroslav

    0

Please sign in to leave a comment.