Skip to main content

Checking intermediate solutions against a threshold, Linear programming

Comments

6 comments

  • Thomas Opfer
    Gurobi-versary
    Thought Leader

    Whether your approach makes sense or not depends on the LP algorithm. Please keep in mind that in dual simplex, the first feasible solution that is found typically is already optimal and early termination makes no sense with any objective function. (That's why I like to call dual simplex an "exterior-point method".:-D ) With primal simplex, it might make sense, but primal simplex might be inferior to dual simplex. I don't know about barrier as I never implemented it. You could play around with the 3 algorithms.

    Furthermore, I think that (II) is faster than (I) because using a zero objective function often causes dual degeneracy. It happens very often that using some objective function is faster.

    Best regards,
    Thomas

    1
  • Simon Jantsch
    Gurobi-versary
    First Comment
    First Question

    Thank you for your comment. That clears things up for me a bit.

    Regarding the gurobi interface: if I use primal simplex and find in the callback that the current value of SPX_OBJVAL is already above the given threshold, how do I access the corresponding solution?

    My current try is to terminate using model.terminate(), but then the I get Status=11 (Interrupted) and SolCount=0 and cannot access any values in the variables.

    Regards,

    Simon

    0
  • Thomas Opfer
    Gurobi-versary
    Thought Leader

    Maybe, there are better ways to achieve your goal, but couldn't you call terminate(), then remove the objective function and then restart primal simplex. This should terminate in 0 (1?) steps as the current basis is feasible (and optimal with zero objective).

    Best regards,
    Thomas

    0
  • Simon Jantsch
    Gurobi-versary
    First Comment
    First Question

    Unfortunately that does not seem to work as if I change the objective function the current basis seems to be gone, it starts again and needs many iterations (>20).

    But there needs to be a way to extract the current basis from an interrupted optimization instance, no? If I don't change the objective function, I can see that it starts with the basis it had computed before the interrupt. I also tried to access the Vbasis attribute of the variables, but that is also not accessible after an interrupt.

    Thanks again for your help and best regards,

    Simon

    0
  • Thomas Opfer
    Gurobi-versary
    Thought Leader

    Hmm, I guess only someone who knows internals of Gurobi can give an adequate answer. I do not really expect such a behaviour.

    Does this also happen if you set DualReductions (and maybe PreDual) to 0? Does this happen if you disable the presolver completely?

    Best regards,
    Thomas

    0
  • Simon Jantsch
    Gurobi-versary
    First Comment
    First Question

    If I disable Presolve completely I still observe the same behaviour. I have posted my question on stack overflow, maybe somebody there can help:

    https://stackoverflow.com/questions/57770333/gurobi-checking-intermediate-solutions-of-linear-program-against-a-threshold

    0

Please sign in to leave a comment.