Expected behaviour of re-runs after model changes

[timellemeet]

Hi, I was wondering if there is more documentation on how resolving with model changes works. My use case is column generation with three steps:

1. Solve the model
2. Expand the model (add a single column)
3. Rounding heuristic (only if no columns with potential savings remain)

In the rounding heuristic a single constraint is added, the bounds of some columns are set to zero, and a helper column is added with high penalty to prevent infeasibilities.

When I add columns the run time increases slightly which makes sense.

However the moment I do the first rounding there is a big jump in run time. Is it expected that adding and updating rows is a lot more time consuming for a consecutive run? In later rounding steps, there is not such a jump.

The thing that surprises me most however is that even after rounding, and we go back to only solving and adding columns, the run time remains high. But so at that point the problem is not much larger than before. Almost as if the first time we add and update rows, the warm start functionality gets "disabled".

Below you find some metrics I tracked. Solving is just timing the call to run.

(I am using highspy)

[jajhall]

There's no documentation I can point you to because what's going on internally is far from trivial. Essentially, when you change the model, HiGHS will try to start simplex as efficiently as it can.

I've got a guess as to what's happening, but need some more information

When you're just adding columns, what bounds do they have? It matters whether they are both finite, and whether 0 is a feasible value for the variable.

When you are rounding, what are the bounds on the helper column?

When you're adding columns after rounding, what bounds do they have? It matters whether they are both finite, and whether 0 is a feasible value for the variable.

Another thing you can do that will give me more information is to set simplex_strategy to 1. This will ensure that the dual simplex algorithm is always used. It's possible that when you're adding columns the LP remains primal feasible, in which case HiGHS will choose to use the primal simplex algorithm to restore dual feasibility. This should be more efficient than using the dual simplex algorithm, which would have to regain dual feasibility (Phase 1) and then get primal feasibility (Phase 2). However, the implementation of the dual simplex algorithm is more efficient.

[timellemeet]

I understand!

To answer your questions:

Every column is bound between or equal to 0 and 1.

Each column belongs to a single "rounding group", each rounding group contains one or more columns.

An "Entity group" in turn contains multiple rounding groups. From the start of the problem. The sum of all columns belonging to an entity group (so nested relation) is equal to 1 as a constraint. This means that the sum of columns for a rounding group is bound between 0 and 1. In the rounding step we select a rounding group and add as constraint the specifically the sum of those columns must also be equal to 1, making the other rounding groups in that entity group equal to 0.

The helper variable is another column in the entity group that ensures a first feasible solution is possible (by not violating other constraints). This has a high penalty and subsequent column generation will ensure it won't be used in the end solution. Note: this helper variable right now is not part of the rounding group that is fixed. So when we do a rounding step we start of from an infeasible point. Is that relevant?

Will try with the other simplex method! But the default value is already 1 right? If I set it explicitly, will that ensure the strategy will stay they same throughout all iterations?

[timellemeet]

I see thank you! Would the currently set option that also have been changed after a run?

[timellemeet]

@jajhall I did a run with debugging on to dive a bit further into this. Two observations:

• Warnings for columns of too large size, would you recommend lowering the penalty of the big M helper columns?
• Indeed a fallback to primal simplex solver. Is there a way to avoid this (simplex strategy is already set)? Or would you say it is best practice to keep it? Or is it because of the too large size columns?

Last runs after just adding columns:

First solve after rounding:

Second rounding right after:

Adding a column:

Adding another column:

[jajhall]

I did a run with debugging on to dive a bit further into this. Two observations:

• Warnings for columns of too large size, would you recommend lowering the penalty of the big M helper columns?

Yes, your |costs| of 1e24 are more than dangerously large. In the version you're running they are accepted with a warning. In the latest version, anything larger than 1e20 in magnitude is treated as infinity - which implies a bound preventing the variable from being positive (negative) according to the sign of the cost

• Indeed a fallback to primal simplex solver. Is there a way to avoid this (simplex strategy is already set)? Or would you say it is best practice to keep it? Or is it because of the too large size columns?

Here the primal simplex solver is being used to "clean up" after dual simplex. [Dual simplex applies a relative perturbation to the costs - as logged - for computational efficiency. Once optimality is identified, the perturbations are removed. This changes the dual values so that

• dual feasibility is retained (as in your second run above) so the unperturbed problem has been solved
• there are dual infeasiblities, so primal simplex is used to regain optimality. These are usually small, so only a very small number of primal simplex iterations are required. However, with costs like 1e18 - let alone 1e24 - they are large, and many more primal simplex iterations are required

Your second run is "special" since dual simplex starts from a dual feasible point, and only one iteration is required.

Otherwise, as your costs get larger, dual simplex struggles more - and primal simplex clean-up after removing the perturbations takes a long time. It's actually interesting to see that you're solving these problems at all. I'd have expected the situation you describe in #1629 to occur more frequently. I can only think that none of the basic variables have costs of 1e24 - otherwise your duals would all be of this order of magnitude, and you'd be trying to satisfy a tolerance of 1e-7. This relative size of 1e31 is almost double the 64-bit precision!

Reduce your costs so that they are never larger than 1e12, and let's see what happens.

[timellemeet]

This seems to have solved the issue, thanks a lot

[jajhall]

That's good. I meant to add that the next version of HiGHS will give a more explicit warning that the user is supplying excessive values for the costs (and bounds) with suggestions on the scaling that would be appropriate.

[jajhall]

I see thank you! Would the currently set option that also have been changed after a run?

No, if settings are changed internally - as is necessary algorithmically - user settings are restored

[timellemeet]

@jajhall as a follow up question. Some of my regular column costs sometimes approach 1e12 (not often). These now results in some times the big M columns (1e12) not resulting in the expected behavior. Would you recommend I scale the costs of my regular columns but keep the ghost columns as is? I would the relative size difference again result the previous problems?

[jajhall]

Regular column costs larger than 1e9 lead to dual values of the same size, and HiGHS assesses dual feasibility using an absolute tolerance (ie ignoring the magnitude of the costs) of 1e-7 (by default). This is asking for trouble because the size of the dual relative to the tolerance is around machine precision.

I'd scale all your regular costs down so that the largest is 1e6, and use no more than 1e12 for the big M columns