An Optimal Bayesian Network Based Solution Scheme for the Constrained
  Stochastic On-line Equi-Partitioning Problem
  A number of intriguing decision scenarios revolve around partitioning a
collection of objects to optimize some application specific objective function.
This problem is generally referred to as the Object Partitioning Problem (OPP)
and is known to be NP-hard. We here consider a particularly challenging version
of OPP, namely, the Stochastic On-line Equi-Partitioning Problem (SO-EPP). In
SO-EPP, the target partitioning is unknown and has to be inferred purely from
observing an on-line sequence of object pairs. The paired objects belong to the
same partition with probability $p$ and to different partitions with
probability $1-p$, with $p$ also being unknown. As an additional complication,
the partitions are required to be of equal cardinality. Previously, only
sub-optimal solution strategies have been proposed for SO- EPP. In this paper,
we propose the first optimal solution strategy. In brief, the scheme that we
propose, BN-EPP, is founded on a Bayesian network representation of SO-EPP
problems. Based on probabilistic reasoning, we are not only able to infer the
underlying object partitioning with optimal accuracy. We are also able to
simultaneously infer $p$, allowing us to accelerate learning as object pairs
arrive. Furthermore, our scheme is the first to support arbitrary constraints
on the partitioning (Constrained SO-EPP). Being optimal, BN-EPP provides
superior performance compared to existing solution schemes. We additionally
introduce Walk-BN-EPP, a novel WalkSAT inspired algorithm for solving large
scale BN-EPP problems. Finally, we provide a BN-EPP based solution to the
problem of order picking, a representative real-life application of BN-EPP.
