Skip to main content

Solver Ignores an Initial Solution

Answered
Evren Guney
  • Gurobi-versary
  • First Comment
  • First Question

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

Comments

4 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    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

    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
    Edited
    • Gurobi-versary
    • First Comment
    • First Question

    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
    • Gurobi-versary
    • First Comment
    • First Question

    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

Post is closed for comments.

Didn't find what you were looking for?

New post