2
$\begingroup$

There is a certain family of typical branch & bound problems in which we have to put $n$ objects into $m$ indistinguishable bags.

Usually solutions are represented by $n$-size vectors in which $V[i]$ means that the $i$-th element is in the $V[i]$-th bag.

Is there a way to avoid generating equivalent solutions without performing an $\mathcal{O}(n)$ time check once the potentially equivalent solution has been built?

I was trying to do something similar as when avoiding circular permutations, but no adaptations seems to work.

$\endgroup$
2
$\begingroup$

You could impose a canonical ordering on the bags.

For instance, in each bag find the lowest-numbered item in that bag, and imagine labelling the bag with that number. Now add the additional constraint that to be a valid solution, the bags must be in sorted order according to their label. In other words, the label on the $i$th bag must be less than the label on the $i+1$st bag.

If you can express this constraint within your system, it ensures that each equivalent solution will be generated only once.

$\endgroup$

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.