Trouble with sequential LP solve (JuMP, HiGHS)

Hi,

I’m afraid this is going to be completely unreproduceable, but after a couple of days I’m starting to think that my problem might not be entirely my own mistakes.

I’m using JuMP and HiGHS (or Gurobi) to solve sequential objectives with an LP, with the wrinkle that we solve twice for each objective with a difference in one constraint (a cheap way of doing a single-binary-variable IP where often one of the two options is infeasible).

For one test case (out of about 60), solving with HiGHS fails after about the 10th LP solve in the sequence with the error message

OTHER_ERROR ("There was an error calling optimize!")

The LP it’s trying to solve is feasible, but the solve immediately before is infeasible, and I’m updating constraints on the same model, not reconstructing the model from scratch, so some model state might be lying around.

Logs from HiGHS for the infeasible and failed models are:

Solving LP without presolve or with basis
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -7.5421920965e-01 Ph1: 13(1085.11); Du: 2(0.754219) 0s
          4     1.2325458579e+01 0s
Model   status      : Infeasible
Simplex   iterations: 4
Objective value     :  1.2325755066e+01
HiGHS run time      :          0.21
---------
Solving LP without presolve or with basis
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -1.2521442429e-01 Ph1: 10(6.07856); Du: 2(0.125214) 0s
          5     1.5601243444e+02 0s
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          5     1.5601569095e+02 Pr: 2(3.70398e-07); Du: 0(9.27958e-12) 0s
          5     1.5601569095e+02 0s
Model   status      : Unknown
Simplex   iterations: 5
Objective value     :  1.5601569095e+02
HiGHS run time      :          0.24

The objective shown in the second log is correct. The model appears to have been solved to optimality, but HiGHS is unhappy for some other reason. For reference, the log for a successful solve of the exact same problem (see below for the workaround) is:

Solving LP without presolve or with basis
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -1.2521440649e-01 Ph1: 10(6.07856); Du: 2(0.125214) 0s
          4     1.5601569143e+02 Pr: 0(0) 0s
Model   status      : Optimal
Simplex   iterations: 4
Objective value     :  1.5601569143e+02
HiGHS run time      :          0.23

The log for the immediately preceding infeasible solve is identical in the workaround case.

If I dump the problem LP to MPS, and HiGHS solves it with no problem, so it seems to be to do with the sequential nature of the solves. There are other test-cases that solve successfully (including this one with a workaround) that follow the same pattern of an infeasible solve followed by unsuccessful solves, so that doesn’t appear to be the issue.

Inspecting the MPSs of all the solves in a failing and workaround case shows no differences other than the ordering of some elements of the file, and the naming of one of the indices.

The really fun part of all this is that the failure is toggled by the names of one of the indices I use in the model.

If I call the supply objects (supplies appear as indices in variables and constraints) “s-1”, “s-2”,… the model solves successfully (and this is my current workaround). If I call the objects “supply-1”, “supply-2”,… the solve fails. Other names either do or don’t work, for example the prefixes “sapply” and “sepply” work, but “sopply” and “sipply” don’t. “su” doesn’t work but “supp” does…

I suspect the problem is related to HiGHS or the HiGHS binding, because the whole thing works if I use Gurobi, but given what else is going on, I really don’t know.

This is with Julia 1.7.2 and a recently updated set of packages:

pkg> st
  [2e9cd046] Gurobi v0.11.0 
  [87dc4568] HiGHS v1.1.1   
  [4076af6c] JuMP v0.23.2   
  ...

So, sorry for unhelpful report. I’m not really expecting anything given such vague information, but, in case it’s helpful, I thought I should try to document what I’ve found. I apologise if this proves to be a problem of my own making :slight_smile:

Thanks!
Geoff

1 Like

Ooof. Debugging these problems with internal state issues in the solver is tricky. (I once had Gurobi fail 1/10_000 solves…).

Can you clarify the sequence?

  • Solve an LP => infeasible
  • Modify constraint => should now be feasible
  • Solve the LP => errors?

How does the 10th LP solve fit in?

Ha! I think the first time we met was when you’d just pinned down that Gurobi bug :slight_smile:

As I’m sure you’ve guessed, this is a product mix model.

The “left” and “right” sides involve a constraint that either says “ensure that you use this byproduct everywhere it is permissible” or “ensure that you use all of this byproduct that you produce”, and we pick the feasible option, or if they’re both feasible, the one with the best objective.

(The two statements above are disjoint. It’s possible to have a plan that produces more of the byproduct than you can possibly use, and equally to have one that can use more of the byproduct than you can possibly produce. We could - and do in some circumstances - solve this as a single-binary-variable IP, but we use the shadow prices out of the LP and so this is the path of least effort for that)

1 & 2: Check feasibility of mass balance, objective is to minimise mass balance violation. Optimal both sides (optimal objective is 0 - no violation)

3 & 4: Maximise production of “highest priority” demand. Optimal both sides. All demand filled

5 & 6: Maximise production of subsequent priority demand. Optimal both sides. Demand partly filled.

7 & 8: Maximise production of subsequent priority demand. Infeasible on the left, optimal on the right.
All demand filled. (order is “left”, “right”)

9 & 10: Maximise production of subsequent (lowest) priroity demand. Infeasible on the left. “Uknown” on the right.

Like I said, I’m really not expecting a solution, but it seems right to document it.

1 Like

Is there anyway you could send me the MPS files of 9 and 10?

Sent!