A Novel Bayesian Network Based Scheme for Finding the Optimal Solution to Stochastic Online Equi-partitioning Problems

A number of intriguing decision scenarios, such as order picking, revolve around partitioning a collection of objects so as to optimize some application specific objective function. In its general form, this problem is referred to as the Object Partitioning Problem (OOP), known to be NP-hard. We here consider a variant of OPP, namely the Stochastic Online Equi-Partitioning Problem (SO-EPP). In SO-EPP, objects arrive sequentially, in pairs. The relationship between the arriving object pairs is stochastic: They belong to the same partition with probability p. From a history of object arrivals, the goal is to predict which objects will appear together in future arrivals. As an additional complication, the partitions of related objects are required to be of equal cardinality. The decision maker, however, is not informed about the true relation between the objects, he is merely observing the stream of object pairs, and has to predict future behavior. Inferring the correct partitioning from historical behavior is thus a significant challenge, which becomes even more difficult when p is unknown. Previously, only heuristic sub-optimal solution strategies have been proposed for SO-EPP. In this paper, we propose the first it 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 correct object partitioning with optimal accuracy. We are also able to simultaneously infer p, allowing us to accelerate learning as object pairs arrive. Being optimal, BN-EPP provides superior performance compared to existing state-of-the-art solution schemes. BN-EPP is also highly flexible, being capable of encoding object partitioning constraints. Finally, BN-EPP is parameter free - its performance does not rely on fine tuning any parameters. As a result of these advantages, BN-EPP opens up for significantly improved performance for OOP based appl- cations.