6
$\begingroup$

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.

  1. 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.

  2. 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.

$\endgroup$
6
  • 2
    $\begingroup$ If some workers or jobs are exactly identical, create variables for groups of workers or groups of jobs. For example $x_{i, j}$ the number of jobs of group $j$ assigned to workers of group $i$ $\endgroup$
    – fontanf
    Nov 21 at 9:41
  • 1
    $\begingroup$ @fontanf You should make this a solution. The first stage would be a model that decides how many workers from each group of identical workers gets assigned to each job category. The second stage would be a mechanism (likely not a mathematical model) for choosing which worker gets assigned to which job based on the optimal solution. This could be as simple as assigning the alphabetically first worker to the lowest index job. If this mechanism is inherently reproducible, there is no need to store anything. $\endgroup$
    – prubin
    Nov 21 at 16:26
  • $\begingroup$ @fontanf That's certainly a good approach when it can be achieved, and would make for a good solution post, though I'd note that it's not always trivial to break the problem into stages in this way! $\endgroup$ Nov 21 at 23:30
  • $\begingroup$ 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. $\endgroup$ Nov 22 at 15:00
  • $\begingroup$ … Of course, if your "workers" are actually servers in a data center, that might not matter since they won't complain. But for problem instances where the workers might complain, you'd probably want to add some kind of a fairness criterion to ensure that, at least in the long run, equivalent workers get assigned equal amounts of work and are rotated evenly between different jobs, even if the jobs differ "only in name". (For that matter, you might want something like that for load-balancing purposes anyway, even if your workers are computers.) $\endgroup$ Nov 22 at 15:00
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks Erwin, I've corrected my terminology re. persistence. I'm aware that these are not the same issues, but they are related in this problem. Re. #3, I am specifically looking for a method that does not require tracking previous solutions. $\endgroup$ Nov 21 at 23:26
  • 1
    $\begingroup$ You probably need to wait for a new class of paranormal solvers for that. $\endgroup$ Nov 22 at 1:52
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)
$\endgroup$
3
  • $\begingroup$ Using a set random seed for perturbation/tie-breaking is my go-to when there are no changes to the problem, but it's liable to break when there are. For instance, if we remove Bob from the problem, then Chris may now get the random numbers that Bob would've otherwise received, changing Chris's tiebreakers and hence changing outcomes beyond what's needed to accommodate the loss of a worker. $\endgroup$ Nov 22 at 22:04
  • $\begingroup$ excellent! the problem changing in such a way shouldn't affect its reproducibility; if Bob is removed from the problem, that should be recorded such that the result can be reproduced (ie. providing the seed and instructions for both a Bob and Bobless run could be reproduced by someone else) $\endgroup$
    – ti7
    Nov 22 at 22:59
  • $\begingroup$ I initially used the wrong term in my question, but as Erwin pointed out, what I was talking about in requirement #3 is persistence of solutions, not merely reproducibility. The object is not just that we get the same allocation every time we run the exact same scenario, but that when we change it to a similar scenario we get a similar allocation: the differences between the Bob and no-Bob allocations shouldn't be (much) more than those required to find the new optimum. $\endgroup$ Nov 23 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.