How to keep solutions stable/persistent in a problem with many equally good solutions?

Question

Suppose we have a worker-assignment problem where we seek to assign Alice, Bob, Chris, ... to jobs A, B, C, ... subject to various constraints and some objective function based on these assignments, and with the following considerations:

1. Many employees are identical except in name. (Workers $i$ and $j$ considered "identical" if for every feasible solution, the allocations for worker $i$ can be swapped with those for $j$ without changing the feasibility or objective-function value of the solution).
2. Similarly, many jobs are identical except in name.

Hence, there will be many optimal solutions that differ from one another only by swaps between identical entities - let's call these "sibling" solutions.

3. Stability/reproducibility Persistence of solutions is desired. If we rerun the same problem to optimality, we want to get the exact same solution, not one of its siblings. If we make small changes to the problem and rerun, we want to change the solution by enough to achieve optimality in the new version of the problem, but no more than that.

4. We may wish to do this many times, without keeping records of all the old solutions.

How can we achieve this?

If it weren't for #4, one possible solution would be to add a small term to the objective function that penalises changes from previous solutions. Unfortunately this becomes impractical if we are doing a lot of runs with small changes.

I have figured out one way to do this and will post as a self-answer, but I am interested in hearing others.

Answer 1

IMHO, the question and posted answer confuse some different issues:

1. Reproducibility. This is about finding the same solution when running the algorithm again with the same input, i.e. providing deterministic behavior. Algorithm developers put in quite some effort to make this happen (not completely trivial when running in multi-threaded environments, you need to design for this). As a user, we are happy to pay a performance penalty for this compared to an opportunistic parallel implementation: staying sane is more important.

2. Symmetry. This is a structural property of a model. It is one of the reasons we can see multiple optimal solutions. Symmetry breaking has been extensively studied in Mixed-Integer and Constraint Programming as it can have a huge impact on performance. Advanced solvers often have options to (try to) deal with symmetries (e.g. using orbital branching [Ostrowski e.a. 2011]). However, adding symmetry-breaking constraints at the model level is still often a good idea.

3. Persistence. This is about staying close to a previously found solution after changing the model/data a little bit. Obviously, only when not too expensive in terms of objective degradation. This is a well-known problem that can be handled by adding a penalty term to the objective (see e.g. Brown e.a. 1997).

These are different issues with different solutions.

Answer 2

Use worker/job identifiers to reproducibly perturb the objective function

If we didn't have to deal with possible changes to the problem, we could use a standard symmetry-breaking method: use a seeded random number generator to make small changes to the objective function in a reproducible way that creates a "tiebreaker" between siblings. As well as improving reproducibility of outcomes, this can also help solver performance in some cases.

In order to accommodate minor changes to the problem, we modify this slightly:

Let $x[i,j]$ be the binary decision variable that indicates whether worker $i$ is assigned to job $j$.

Define a function $f(i,j)$ which hashes the unique names (character strings) of worker $i$ and job $j$ to a numeric value between 0 and 1, in such a way that for $(i,j) != (k,l)$ the probability that $f(i,j)=f(k,l)$ is very small.

Modify the objective function by adding a perturbation term $x[i,j]f(i,j)k$ for some small constant k.

Adding new workers and jobs to the problem will require generating new perturbation terms, but under this approach it doesn't change the existing terms. Hence, in allocating jobs between Alice and Bob, the relevant tiebreakers will remain the same, and hence we can expect similar outcomes (unless the new workers/jobs require significant changes to Alice & Bob's allocations to restore optimality).

As noted by Ilmari Karonen in a comment, persistence of solutions might not always be desirable:

Since you've used worker assignment as your example problem, let me note that there's a potential pitfall with your solution, and indeed with any scheme that tries to achieve your stated goal: solutions that are equivalent from your perspective may not be equivalent from the workers' perspective, and any stable tie-breaking scheme that "randomly" perturbs the job/worker objective terms can easily end up always assigning Alice to all the "shitty" jobs (or no jobs at all!) while Bob gets the "nice" jobs (at least in Alice's opinion) for no justifiable reason. Hello, discrimination lawsuit.

Answer 3

At the beginning of your simulations, create a seed through some random means to use for your later random engine choices. Often simply the current floating-point time is a good and sufficient choice (and trivially allows both reproducing your results and new results from the same program)

With your seed selected (and recorded for later result replication!), configure your system to base from it in a structured manner whenever you have a random choice

Good examples

• broadly, choosing one of or the ordering of N to "go first" when they are otherwise equal
• ordering unordered workers with the same arrival times or feeding from the same queue (should Alice take precedence over Bob at the water cooler if they both arrive at the same time? which of two equal carriages driving towards a bridge should give way?)
• shuffling a collection of predetermined inputs which should come randomly (ie. a hat full of numbers for who goes first in an event with an equal amount of numbers as members - the value here can be somewhat dubious, but it may model a real process)
• which part should be chosen from a bin with known, but random identifiers

Bad examples

• choosing computational system result priority when two arrive together (your results are not being determined by the seed, as workers may return at different rates based upon outside values - instead, if the worker return timings could be close, you should gate and predetermine their order based upon your seed)