Skip to main content

MIP Start does not produce an incumbent solution while I can prove that the MIP Start is feasible

Answered
Max Aalberse
Edited
  • Gurobi-versary
  • First Comment
  • First Question

Dear,

For my thesis I am working on a optimization problem and designed two algorithms. One MIP and one GA. The problem is that the GA found a better solution than the MIP, even though this is already strange, when I try to implement the solution using MIP Start no incumbent is found and if I try to fix the values of the variables the model becomes infeasible. 

However using the same constraints as used in the MIP I can prove that the solution found by the GA is more optimal than the one produced by MIP and that it satisfies all constraints

Do you have any ideas how to solve this issue?

Related to

0

Comments

8 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    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 why not try our AI Gurobot?.
  • Jaromił Najman
    • Gurobi Staff

    Hi Max,

    Could you share the MIP start file and the model file such we can try to reproduce the issue you describe? Please have a look at Posting to the Community Forum for more information on sharing files.

    Could you also share the Gurobi output when you provide the initial point? Especially the first 30-40 lines are of interest.

    Best regards,
    Jaromił

    1
  • Max Aalberse
    • Gurobi-versary
    • First Comment
    • First Question

    Dear Jaromił,

    I uploaded the model to FileMail: https://www.filemail.com/d/mkqnmszrlxirfbk

    The runfile is either MIP.ipynb or MIP.py,  the rest is there because it is necessary to run the file. Both the MIP start and proof that the solution for the MIP start does comply with all constraints is also in this file.

    The output of Gurobi is as follows:

    Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 3707 rows, 3912 columns and 16049 nonzeros
Model fingerprint: 0x021a5c98
Model has 544 quadratic objective terms
Model has 2278 quadratic constraints
Model has 1 general constraint
Variable types: 36 continuous, 3876 integer (3638 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+04]
  QMatrix range    [1e+00, 4e+01]
  QLMatrix range   [1e+00, 1e+06]
  Objective range  [1e+00, 5e+04]
  QObjective range [2e+00, 2e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 6e+04]

User MIP start did not produce a new incumbent solution

Presolve removed 269 rows and 1033 columns
Presolve time: 0.06s
Presolved: 58671 rows, 21375 columns, 168262 nonzeros
Presolved model has 1 SOS constraint(s)
Variable types: 822 continuous, 20553 integer (19907 binary)

Root relaxation: objective 3.116538e+05, 1781 iterations, 0.02 seconds

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

     0     0 314133.482    0  145          - 314133.482      -     -    0s
H    0     0                    406166.32732 314133.482  22.7%     -    0s
     0     0 322873.992    0   81 406166.327 322873.992  20.5%     -    0s
H    0     0                    367420.41314 322873.992  12.1%     -    0s
H    0     0                    340704.71760 322873.992  5.23%     -    0s
     0     0 329921.358    0   90 340704.718 329921.358  3.17%     -    0s
H    0     0                    333944.97540 329921.358  1.20%     -    0s
     0     0 330069.975    0  117 333944.975 330069.975  1.16%     -    1s
     0     0 330101.633    0  120 333944.975 330101.633  1.15%     -    1s
H    0     0                    332031.97540 330116.457  0.58%     -    1s
     0     0 330116.457    0  114 332031.975 330116.457  0.58%     -    1s
H    0     0                    331303.97540 330153.482  0.35%     -    1s
H    0     0                    331289.97540 330153.482  0.34%     -    1s
     0     0 330153.482    0  118 331289.975 330153.482  0.34%     -    1s
     0     0 330168.689    0  120 331289.975 330168.689  0.34%     -    1s
     0     0 330210.081    0  100 331289.975 330210.081  0.33%     -    1s
H    0     0                    331148.15894 330210.081  0.28%     -    1s
     0     0 330214.297    0   81 331148.159 330214.297  0.28%     -    1s
     0     0 330214.297    0   81 331148.159 330214.297  0.28%     -    1s
     0     2 330214.297    0   81 331148.159 330214.297  0.28%     -    1s
H   31    29                    331134.15894 330214.297  0.28%  10.5    1s
H  193   117                    331004.15894 330214.297  0.24%   8.0    2s
  2624   733 331002.454   23   77 331004.159 330694.198  0.09%   6.0    5s
* 2744   711              51    330996.97540 330949.196  0.01%   7.4    5s
H 2745   673                    330991.97540 330949.196  0.01%   7.3    5s

Cutting planes:
  Gomory: 13
  Implied bound: 4
  MIR: 11
  Flow cover: 28
  RLT: 21
  Relax-and-lift: 11

Explored 2757 nodes (23152 simplex iterations) in 5.74 seconds
Thread count was 12 (of 12 available processors)

Solution count 10: 330992 330997 331004 ... 340705

Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (5.0767e-06) exceeds tolerance
Warning: max general constraint violation (5.0767e-06) exceeds tolerance
Best objective 3.309919753998e+05, best bound 3.309679753998e+05, gap 0.0073%
    0
  • Max Aalberse
    • Gurobi-versary
    • First Comment
    • First Question 
    Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
    Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
    Optimize a model with 3707 rows, 3912 columns and 16049 nonzeros
    Model fingerprint: 0x021a5c98
    Model has 544 quadratic objective terms
    Model has 2278 quadratic constraints
    Model has 1 general constraint
    Variable types: 36 continuous, 3876 integer (3638 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+04]
      QMatrix range    [1e+00, 4e+01]
      QLMatrix range   [1e+00, 1e+06]
      Objective range  [1e+00, 5e+04]
      QObjective range [2e+00, 2e+00]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 6e+04]

    User MIP start did not produce a new incumbent solution
    Presolve removed 269 rows and 1033 columns
    Presolve time: 0.06s
    Presolved: 58671 rows, 21375 columns, 168262 nonzeros
    Presolved model has 1 SOS constraint(s)
    Variable types: 822 continuous, 20553 integer (19907 binary)
    Root relaxation: objective 3.116538e+05, 1781 iterations, 0.02 seconds
        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
         0     0 314133.482    0  145          - 314133.482      -     -    0s
    H    0     0                    406166.32732 314133.482  22.7%     -    0s
         0     0 322873.992    0   81 406166.327 322873.992  20.5%     -    0s
    H    0     0                    367420.41314 322873.992  12.1%     -    0s
    H    0     0                    340704.71760 322873.992  5.23%     -    0s
         0     0 329921.358    0   90 340704.718 329921.358  3.17%     -    0s
    H    0     0                    333944.97540 329921.358  1.20%     -    0s
         0     0 330069.975    0  117 333944.975 330069.975  1.16%     -    1s
         0     0 330101.633    0  120 333944.975 330101.633  1.15%     -    1s
    H    0     0                    332031.97540 330116.457  0.58%     -    1s
         0     0 330116.457    0  114 332031.975 330116.457  0.58%     -    1s
    H    0     0                    331303.97540 330153.482  0.35%     -    1s
    H    0     0                    331289.97540 330153.482  0.34%     -    1s
         0     0 330153.482    0  118 331289.975 330153.482  0.34%     -    1s
         0     0 330168.689    0  120 331289.975 330168.689  0.34%     -    1s
         0     0 330210.081    0  100 331289.975 330210.081  0.33%     -    1s
    H    0     0                    331148.15894 330210.081  0.28%     -    1s
         0     0 330214.297    0   81 331148.159 330214.297  0.28%     -    1s
         0     0 330214.297    0   81 331148.159 330214.297  0.28%     -    1s
         0     2 330214.297    0   81 331148.159 330214.297  0.28%     -    1s
    H   31    29                    331134.15894 330214.297  0.28%  10.5    1s
    H  193   117                    331004.15894 330214.297  0.24%   8.0    2s
      2624   733 331002.454   23   77 331004.159 330694.198  0.09%   6.0    5s
    * 2744   711              51    330996.97540 330949.196  0.01%   7.4    5s
    H 2745   673                    330991.97540 330949.196  0.01%   7.3    5s

    Cutting planes:
      Gomory: 13
      Implied bound: 4
      MIR: 11
      Flow cover: 28
      RLT: 21
      Relax-and-lift: 11

    Explored 2757 nodes (23152 simplex iterations) in 5.74 seconds
    Thread count was 12 (of 12 available processors)

    Solution count 10: 330992 330997 331004 ... 340705

    Optimal solution found (tolerance 1.00e-04)
    Warning: max constraint violation (5.0767e-06) exceeds tolerance
    Warning: max general constraint violation (5.0767e-06) exceeds tolerance
    Best objective 3.309919753998e+05, best bound 3.309679753998e+05, gap 0.0073%
    0
  • Jaromił Najman
    • Gurobi Staff
    Edited

    Hi Max,

    Thank you for uploading the files. Could you simplify this issue further by generating a MIP start file, cf. MST format? This would greatly simplify the investigation process, because one then could execute

    gurobi_cl inputfile=initial_point.mst your_model.lp

    Best regards,
    Jaromił

    1
  • Max Aalberse
    • Gurobi-versary
    • First Comment
    • First Question

    This should work

    https://www.filemail.com/d/mhwwehyppgfzsca

    0
  • Jaromił Najman
    • Gurobi Staff

    Hi Max,

    The issue with your MIP start is that, e.g., variable \(\texttt{ss_0,1}\) is a binary variable but you provide

    ss_0,1 40

    in the MST file.

    I found this by fixing all variable bounds to the MIP start value, and computing the IIS via the following code

    import gurobipy as gp 
    from gurobipy import *

    m = gp.read("MILP_Test2_lp.lp")
    m.read("MIPStart.mst")

    for v in m.getVars():
      v.lb = v.Start
      v.ub = v.Start
    # need to determine that model is infeasible before IIS can be computed
    m.optimize()

    m.computeIIS()
    m.write("myIIS.ilp")

    Best regards,
    Jaromił

    1
  • Max Aalberse
    • Gurobi-versary
    • First Comment
    • First Question

    Dear Jaromił,

    Thank you very much for spotting the mistake, The model now indeed finds a better solution.

    Kind regards,

    Max

    0

Post is closed for comments.

Didn't find what you were looking for?

New post