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:
- 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).
- 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.
Stability/reproducibilityPersistence 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.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.