leximin: Spend more time looking into why weights need to be randomised

[foobacca]

In #19 we had to make a change to the leximin algorithm, in particular changing the initial weights from all being 1.0 to being a random choice between 0.8 and 1.0.

The code at that commit (before refactoring) was at

stratification-app/stratification.py

Line 1483 in ffbf19e

weights = {id: random.uniform(0.8, 1.0) for id in agent_vars}

    # We begin using a multiplicative-weight stage. Each agent has a weight between 0.8 and 1
    # Note that if all start with the same weight then we can end up with some committees
    # having the wrong number of results.
    weights = {id: random.uniform(0.8, 1.0) for id in agent_vars}

Before making that change, we found that when running a test expecting 46 in a committee, the first committee would actually have 49.

@foobacca noticed that for subsequent rounds the weights were changed - sometimes decreased for some members, to make it more likely others would be included, and sometimes increased across the board if we're getting the same result more than once. So every round apart from the first round has a mix of weights and every round apart from the first round produced the expected number of committee members (46). That led to trying the initial weight randomisation, which worked.

Questions we'd like to investigate:

• did the tests and algorithm work fine when the work was done originally committed? If so, we could try a git bisect to see what broke the code.
• is there any reason that random weights would cause something bad to happen?
• can we try reducing the variation - say random values from 0.98 to 1 - to see if that keeps the tests passing with less difference from the initial version.
• can we understand how we end up with the wrong number of members of the committee. Do we need to deepen our understanding of the original algorithm.

[foobacca]

@pgoelz - this may be of interest to you, as you contributed the code originally (though some years ago).

[pgoelz]

Hi Hamish, thanks for adding me to the thread. Your finding sounds like there’s a pretty big bug either in the mip library or (more likely) in the underlying CoinOR CBC solver. Do you still observe the weird 49 behavior when you update the mip package? If so, it might make sense to make a ticket in the mip package (here is a ticket I made for a different issue I encountered).

For an immediate fix, I think it would be more robust not to change the initial weights, but to check, any time the code runs new_set = _ilp_results_to_committee(...) that new_set has the right number of participants and satisfies all the quotas, and to only add the set if it does. (You could put this functionality directly into _ilp_results_to_committee, for example.)

Longer-term, I suspect the right fix is to move away from CoinOR CBC altogether because it’s brittle and slow (this is also why, if no commercial solver is installed, the tool runs the easier algorithm maximin rather than leximin). I’ve heard some promising things about https://highs.dev/ , a newish open-source solver, but haven’t experimented with it myself yet.