Solver Ignores an Initial Solution

回答済み

Evren Guney

2022年07月25日 13:26

• 
• 
• 

Hello,
I have a very small VRPTW instance (17 nodes) and when I run it, it takes hours and no feasible solution is returned. So I tried to feed Gurobi with a simple initial feasible solution and use  variable.Start method to initialize. When I run it, Gurobi returns that this solution is not better than the incumbent solution (it is feasible, because when I tried an infeasible solution it pops the violated constraint as well) and does the search from scratch (and no solution in hours again). I've applied this variable.Start method many times and this is the first time it did not (seem to) work.

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:31

  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 try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Simon Bowly

  • Gurobi Staff

  2022年07月27日 07:46

  Hi Evren,

  Can you clarify what you mean by "Gurobi returns that this solution is not better than the incumbent solution", when (if I'm reading your message correctly) Gurobi has no incumbent solution at the time? Could you please share the log file output here?

  Thanks
  Simon

  0
• 

  Evren Guney

  2022年07月27日 08:46 編集済み

  • 
  • 
  • 

  Hi Simon,
  I've attached log for two cases. One with a feasible initial solution, one with an infeasible intial solution.
  As you will see in the first one Gurobi says: "User MIP start did not produce a new incumbent solution", but it does not also find any incumbent solutions (as you can see in the first 3-lines of the iterations). I wonder why my initial solution did not qualify for an incumbent solution. In the second case, I can totally understand why Gurobi rejects my initial solution (as it is not feasible).

   

  LOG-1 // With a feasible starting solution

  Optimize a model with 940 rows, 918 columns and 5715 nonzeros
  Model fingerprint: 0x53f75410
  Variable types: 51 continuous, 867 integer (867 binary)
  Coefficient statistics:
    Matrix range     [1e+00, 1e+04]
    Objective range  [4e+02, 2e+06]
    Bounds range     [1e+00, 5e+02]
    RHS range        [1e+00, 1e+04]

  User MIP start did not produce a new incumbent solution

  Presolve removed 54 rows and 51 columns
  Presolve time: 0.03s
  Presolved: 886 rows, 867 columns, 9696 nonzeros
  Variable types: 51 continuous, 816 integer (816 binary)

  Root relaxation: objective 3.121200e+04, 56 iterations, 0.01 seconds (0.00 work units)
  Another try with MIP start

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

       0     0 31212.0000    0   34          - 31212.0000      -     -    0s
       0     0 32549.8151    0   43          - 32549.8151      -     -    0s
       0     0 35024.0000    0   40          - 35024.0000      -     -    0s

   

  LOG-2// Infeasible solution

  Optimize a model with 940 rows, 918 columns and 5715 nonzeros
  Model fingerprint: 0xa5dfe282
  Variable types: 51 continuous, 867 integer (867 binary)
  Coefficient statistics:
    Matrix range     [1e+00, 1e+04]
    Objective range  [4e+02, 2e+06]
    Bounds range     [1e+00, 5e+02]
    RHS range        [1e+00, 1e+04]

  User MIP start did not produce a new incumbent solution
  User MIP start violates constraint arrival_15 by 1.000000000

  Presolve removed 54 rows and 51 columns
  Presolve time: 0.02s
  Presolved: 886 rows, 867 columns, 9696 nonzeros
  Variable types: 51 continuous, 816 integer (816 binary)

  Root relaxation: objective 3.121200e+04, 56 iterations, 0.00 seconds (0.00 work units)
  Another try with MIP start

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

       0     0 31212.0000    0   34          - 31212.0000      -     -    0s
       0     0 32549.8151    0   41          - 32549.8151      -     -    0s
       0     0 35024.0000    0   40          - 35024.0000      -     -    0s

  0
• 

  Evren Guney

  2022年07月27日 10:01

  • 
  • 
  • 

  Hi Simon,
  
  Good news. I have tried to add the initial solution as hard constraints and then Gurobi found the model is infeasible (it doesnt show the infeasibility of the intial solution and violated constraint like Case-2).
  I discovered the violated constraint with the ComputeIIS trick and revised the model to eliminate it. So what I can tell is, sometimes even the model is infeasible Gurobi starting solution does not display the violated constraint, just warns "User MIP start did not produce a new incumbent solution". This caused me to mistakenly think that my initial solution is feasible but somehow it is not qualifying as an incumbent solution. Now it looks fine.

  0

投稿コメントは受け付けていません。