Skip to main content

Simplex method does not stop at optimal solution.

Answered

Comments

7 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    You could try the following things:

    • Update to the latest Gurobi version 11
    • Fix all variables to the optimal solution point you have found via equality constraints and check whether the model is declared optimal or infeasible
    • Decrease the value of OptimalityTol. Is there a good reason why you increased it? It is usually not a good idea to increase this value as it may lead to unnecessary/bad iterations.

    Also, I am curious about other possible way to warm start the LP, as I am able to provide a near optimal feasible solution and hoping to speed up the simplex method.

    If you only have a feasible point without basis information, then setting the PStart attribute is the correct and currently only way to warmstart the Simplex method.

    If you still run into the described issue, could you please share the model? Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

    Best regards, 
    Jaromił

    0
  • Yakun Wang
    First Question
    First Comment

    Hi Jaromił,

    Thanks for your response,

    I tried the following things:

    • Update to the version 11.
    • Set the optimality tolerance to 1e-9.

    Same problem still happened.

    I also tried fixing all variable to the warm start solution I provided through equality constraints. The model is feasible.

    Optimize a model with 1665376 rows, 11325 columns and 6649575 nonzeros
    Model fingerprint: 0x85a74491
    Coefficient statistics:
      Matrix range     [1e+00, 1e+00]
      Objective range  [1e-02, 5e+01]
      Bounds range     [1e+00, 1e+00]
      RHS range        [2e-02, 3e+00]
    Presolve removed 1665376 rows and 11325 columns
    Presolve time: 0.72s
    Presolve: All rows and columns removed
    Iteration    Objective       Primal Inf.    Dual Inf.      Time
           0    7.8940841e+01   0.000000e+00   0.000000e+00      1s

    Solved in 0 iterations and 1.34 seconds (1.38 work units)
    Optimal objective  7.894084143e+01

    I shared the model through google drive: https://drive.google.com/file/d/18sT7V_TyCFXNzQC8ZEu4SZZ9-NQ9f5Td/view?usp=drive_link.

    Thanks!

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Thanks Yakun. Could you please also share an attr file with the PStart information to make the issue reproducible?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Thank you Yakun. I can confirm that I can reproduce the issue. I will let you know once I have more information about the issue.

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Yakun,

    The situation is that the provided optimal solution point has a big dual infeasibility. In such cases, primal Simplex may take a lot of time if the soint is primal degenerate  to actually prove optimality despite having an optimal solution point from the start.

    This paper by Megiddo shows that having an optimal primal or dual solution alone is asymptotically no better than having no solution at all. Often providing a feasible point as start vector helps but this is not always the case and you ran in one such case where it does not help. What would help is if you would provide basis information via the VBasis attribute.

    A different workaround would be to not set Method=0 but just go with defaults. In that case, maybe the dual Simplex or the Barrier algorithm converge to an optimal solution quickly.

    Best regards, 
    Jaromił

     

    0
  • Yakun Wang
    First Question
    First Comment

    Thank you for your response!

    0

Please sign in to leave a comment.