Limit solutions for an LP

Answered

Zohar Levi

• August 11, 2022 12:08
• Edited

I have a large linear program that takes 10 seconds, which is too long. I'd like to limit it and get a solution that is feasible but not necessarily optimal.

For a mix-int problem, there's the parameter SolutionLimit. Is there something similar for LP? For example, the first vertex that the simplex algorithm finds.

0

• 

  Jaromił Najman

  Gurobi Staff

  • August 11, 2022 15:22
  • Edited

  It is currently not possible to get an intermediate point of the Simplex (or Barrier) solution process.

  If the objective value only is enough in your case, then you can tell Gurobi to stop as soon as an iterate gets primal feasible and retrieve the last objective value in a callback. This would look similar to this:

  import gurobipy as gp
  from gurobipy import GRB
  
  def simplexcallback(model,where):
    if where == GRB.Callback.SIMPLEX:
        vio = model.cbGet(GRB.Callback.SPX_PRIMINF)
        if vio < 1e-6:
          print(model.cbGet(GRB.Callback.SPX_OBJVAL))
          print("Reached primal feasibility")
          model.terminate()
  
  m = gp.read("myLP.lp")
  
  m.setParam("Method",0)
  
  m.optimize(simplexcallback)

  Best regards, 
  Jaromił

  0
• 

  Zohar Levi

  • August 11, 2022 23:08
  • Edited

  I see, thanks, but I need a solution to terminate prematurely.

  I'll just note that the simplex algo. has a theoretical exponential complexity, and maybe my request isn't so far fetched.

  For future reference, soplex is an established open source, and it has a parameter to control the iteration limit.

  0
• 

  Jaromił Najman

  Gurobi Staff

  • August 12, 2022 07:06

  For future reference, soplex is an established open source, and it has a parameter to control the iteration limit.

  Please note that there is the IterationLimit parameter, which controls the maximum number of iterations for Simplex algorithms.

  0
• 

  Zohar Levi

  • August 12, 2022 15:23
  • Edited

  And what happens if I stop it prematurely?

  Let's try again. This is my objective:

  https://math.stackexchange.com/questions/4510587/find-a-feasible-but-not-optimal-solution-to-a-large-lp

  Can I specify a warm-start, use the primal simplex, terminate it early and get a better feasible solution?

  Your python callback, how do I specify it in matlab?

  0
• 

  Jaromił Najman

  Gurobi Staff

  • August 16, 2022 06:50

  Can I specify a warm-start, use the primal simplex, terminate it early and get a better feasible solution?

  If you terminate the Simplex algorithm early, due to,e.g., the IterationLimit or TimeLimit parameter, you will not be able to retrieve the current Simplex candidate (let it be feasible or not) from Gurobi. Thus, I don't think that there is any other option for you here except to let Simplex run till optimality.

  Your python callback, how do I specify it in matlab?

  Unfortunately, Gurobi's MATLAB interface does not support callbacks.

  0
• 

  Zohar Levi

  • August 16, 2022 09:38

  Okay, thanks.

  0
• 

  Jaromił Najman

  Gurobi Staff

  • August 29, 2022 11:58
  • Edited

  Here is an update and a correction to my last statement.

  If you terminate the Simplex algorithm early, due to,e.g., the IterationLimit or TimeLimit parameter, you will not be able to retrieve the current Simplex candidate (let it be feasible or not) from Gurobi. Thus, I don't think that there is any other option for you here except to let Simplex run till optimality.

  You can access the current Simplex candidate but you have to run the Simplex algorithm with presolve turned off, i.e., set Presolve=0.

  Note that solving models without presolve can impact performance drastically.

  0
• 

  Zohar Levi

  • August 29, 2022 23:33

  It works, thanks.

  0

Please sign in to leave a comment.