Applying deep convolutional neural networks to the dragon boat partition problem

Abstract

We investigate approximating the Dragon Boat Partition problem, a practical real-worldvariant of the Partition problem. A team of dragon boat participants must be partitionedwith an approximately balanced arrangement with a preferable weight difference of 0. Wepresent two approaches that capture the participant characteristics. The first approach takesa heuristic route. The second approach applies Deep Convolutional Neural Networks to theproblem, with two versions. In our 10,000 episodes per experiment, our heuristic imple-mentation had an average episode runtime of 1.84ms, an average of 7.39 steps per episode,perfect left-right approximation rate of 98.53%, perfect front-back approximation rate of89.16%, and a perfect combined approximation rate of 90.15%. Whereas our best deeplearning model has an average episode runtime of 1.23ms, an average of 4.65 steps perepisode, perfect left-right approximate rate of 98.00%, perfect front-back approximationrate of 95.13%, and a perfect combined approximation rate of 94.28%.