Back to SYMPHONY Home Page
Although SYMPHONY is a mature software library and already contains the advanced features required for most uses, some future enhancements are planned. Currently, there is another version of SYMPHONY, code-named BCP, under development at IBM. BCP implements SYMPHONY in C++ with several enhancements, such as the ability to generate arbitrary variables (making the handling of cuts and variables completely symmetrical), better fault tolerance and virtual machine handling, better cut pool scanning, and a more generalized branching scheme.
The current version of SYMPHONY will continue to be enhanced as well. One of the biggest changes planned is to make the implementation more scalable. Currently, the single tree manager can become a communication bottleneck when large numbers of processors are utilized. There are a number of approaches to solving this problem, all of which involve some degree of decentralization of the tree management. Of course, this decentralization can in return have other undesirable effects, such as difficulty in load balacing.
Other areas in which SYMPHONY will be improved include better management of the cut pool, better search strategies for the tree manager, and more efficient column generation. This last one is paricularly important for solving large scale paroblems. The current implementation of column generation is somewhat inefficient. We would also like to add dynamic allocation of cut generators as an option. Rather than requiring each LP to have its own dedicated cut generator, cut generators will be allocated as needed to LP processes so that more cut generation can be devoted to areas of the tree that are ``difficult'' and less to areas that are ``easy.'' This idea was investigated for Set Partitioning in [6] and found to be effective. Refined tree search algorithms, optimized for parallelism, should also allow better load-balancing.