Skip to content

during Lexigraphic adding and removing constraints each time is ~2x slow than adding all at start and making binding/nonbinding #215

Closed

Description

@oxinabox

In the implementation of lexographic constraints are constantly being added at each step.

This voids things that the solve tends to do when it is benifiting from solving the same problem again.
And I believe generally preferable is to add all the constraints up front for all objectives and then change which was beinging.
via changing the constant terms

I had Claude throw together a benchmark and demo of this and it found that it was indeed over 2x faster.
That is the preset row.
The add_and_delete row is it reimplementing what i believe MOA is doing, but even that seems faster.
So something else must also be be screwy.

Making something sparse with 3000 variables, 1500 constrains and 3 objectives.
solving 200 steps where each step represents the model solving a the problem with slightly different parameters.
(but not ever totally reconstructed)

Results:

variant        total s    first ms   median ms    max ms  iters/step
moa             138.55       639.5      677.99    1027.7         Not_Computed
preset           57.99       258.1      284.17     445.5        3553
add_delete      100.80       483.2      491.94     773.8        5345

The iters/step is how many iters the solver took to solve (averaged over steps). Which isn't possible to get from MOA right now.
But I think it supports my hypothesis that reusing the model with only constrain changes benefits from a kind of warm-starting in the solver.
Since the number of iterations is much lost

Full results and script to generate

Activity

  1. oxinabox commented on Oct 30, 2026

    @oxinabox
    Author

    Ah I think the code I was benchmarking implictly
    ends up doing
    Equivalent of

    set_attribute(model, MOA.ComputeIdealPoint(), false)
    

    so that explains the difference for delete_and_add

  2. odow commented on Oct 31, 2026

    @odow
    Member

    I wonder if this is also an artefact of HiGHS. I wouldn't have expected that such a minor change would make that much of a difference.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions