LP early termination

[baharev]

When solving an LP relaxation, I want to terminate the simplex solver early if the objective function reaches a certain threshold, since the node will be cut off anyway. I thought the objective_bound option would do exactly that, but this option seems to have no effect.

How can I achieve early termination?

As a workaround, I could add the objective as an additional constraint and impose the bound that constraint, but it’s not ideal.

Maybe a custom simplex interrupt callback could do it, but that’s also not ideal in Python.

Any help is greatly appreciated.

[jajhall]

Let's assume that your LP is a minimization.

By default, HiGHS uses the dual simplex algorithm. When objective_bound is set, it terminates when the (increasing) dual objective value reaches objective_bound - since the optimal primal objective value is guaranteed to be no less than objective_bound.

The objective_bound option is used successfully in the HiGHS MIP solver.

In what way have you used the objective_bound option and feel that it has no effect?

[baharev]

Thank you for your prompt response.

Here is a minimal reproducible example:

from highspy import Highs, ObjSense

h = Highs()

x0 = h.addVariable(ub=10)
x1 = h.addVariable(ub=10)
x2 = h.addVariable(ub=1)
x3 = h.addVariable(ub=7)

h.addConstr(  x0 + 2*x1 + 3*x2 + 2*x3 <= 15)
h.addConstr(3*x0 + 4*x1 + 2*x2 +   x3 <= 10)
h.addConstr(2*x0 + 2*x1 + 2*x2 + 2*x3 <= 20)
h.addConstr(4*x0 + 3*x1 +   x2 +   x3 <= 10)

h.setObjective(2*x0 + 2*x1 + x2 + x3, ObjSense.kMaximize)

h.setOptionValue('presolve', 'off')

h.setOptionValue('objective_bound', 0.0)
print('objective_bound:', h.getOptionValue('objective_bound'))

h.run()

print()
print('Model status:', h.getModelStatus())
print('Objective value:', h.getObjectiveValue())
print('Solution:')
print('\n'.join(str(x) for x in h.getSolution().col_value))

No matter how I set the objective_bound, the LP is solved to optimality in 4 simplex iterations. I expected early termination.

I don't see my mistake.

---

Just to avoid the XY problem, here’s the context:

I’m implementing a custom, problem-specific branch-and-bound algorithm that already outperforms general-purpose MILP solvers like HiGHS and SCIP.

Each child node inherits the initial basis and LP relaxation solution from its parent, that is, I warm-start the solver from a dual feasible solution. However, there’s no need to solve the LP relaxation to optimality if the node can be cut off because its objective exceeds the current incumbent. Therefore, I want the simplex solver to stop as soon as it reaches this cutoff value.

This is currently a real performance bottleneck.

[jajhall]

I see that objective_bound is only applied in the case of minimizations - as only that was necessary for the HiGHS MIP solver (which minimizes internally) - so this is something for me to add

However, for your example (as a maximizer), the optimal objective value is 8.6363636364. The initial dual objective value is 48, and the next three are 9, 8.8, 8.6923, and then the optimal value of 8.6363636364. Hence an objective bound of 0 is never satisfied.

I've hacked something in, and with an objective_bound value of 8.7, the solver takes only 3 iterations, and returns the status HighsModelStatus::kObjectiveBound.

I'll revert this back to an issue, but it won't be fixed soon

[baharev]

Thank you for your prompt response.

it won't be fixed soon

Is there any practical workaround in the meantime?

I looked into Highs.cbSimplexInterrupt, which exposes HighsCallbackOutput.objective_function_value, but this always seems to be -inf. Perhaps I’m misunderstanding the purpose of this attribute or callback. Also, invoking a pure Python function at every simplex iteration is a performance concern.

[jajhall]

If you negate the costs and 'objective_bound', and minimize, then it should work as you wish

[baharev]

OK, thank you.

[jajhall]

OK, thank you.

Note that, due to another quirk mentioned in #2473, the simplex solver won't terminate immediately once the 'objective_bound' is reached, but it shouldn't make a big difference with large problems

[baharev]

Yes, I know, that is why I was asking for a workaround with callbacks. But I’ve reached the same conclusion: a few extra iterations won’t noticeably impact performance on my large LPs, and flipping the objective sign is easy to implement. It is an acceptable workaround for the time being.