CombineNet VII: BoB’s Power Source

Yesterday I told you that not only could CombineNet support all of the basic cost and constraint categories required for true decision support, but that the model they generate accurately represents all of the costs and constraints they support and they can solve the model faster than all of their competitors the vast majority of the time. I also told you that today I’d highlight where this unique capability comes from.

Paul highlighted it in hisĀ “Now that’s an Electric Engine …” recent post on CombineNotes [WayBackMachine]. CombineNet’s ClearBox uses sophisticated tree-search algorithms to find the optimal allocation. Furthermore, the algorithms are ‘anytime algorithms’; they provide better and better solutions during the search process. And, CombineNet has also invented a host of proprietary techniques in tree search algorithms, including new branching strategies, custom cutting plane families, cutting plane generation and selection techniques, and machine learning methods for predicting what techniques will perform well on the instance at hand (for use in dynamically selecting a technique).

Even though every model can be built and solved on an off-the-shelf optimizer, the reality is that we are dealing with NP-Complete problems, which means that solve time generally increases exponentially with problem size. This means that for any given solver and any given model class, there is a limit on the average model size that can be solved in any given time window. Although an efficient model formulation combined with an appropriately tweaked off-the-shelf solver can solve a very decently sized problem, one must not ignore the fact that generic solvers use generic algorithms which are not always optimized for the problem at hand. This indicates that it is likely that one could create an appropriately defined custom designed algorithm that is likely to solve the model faster, if not significantly faster.

What is not as obvious is the degree of difficulty often associated with the development of these custom algorithms for strategic sourcing decision optimization. The nature of these problems is that it is very hard to determine for any given solution strategy and any given model instance, whether it is more or less likely to solve the model faster than another similar solution strategy. It’s the fundamental nature of NP-Complete. If we knew how to do it, we’d likely be in P-Space.

As highlighted in the post, CombineNet began to develop its algorithms in 1997, and it has 16 people working on the algorithms. We have tested hundreds of techniques to find those that shorten solve time for Expressive Commerce clearing problems. Some of the techniques are specific to market clearing, and others apply to combinatorial optimization more broadly. And that’s where the strength of CombineNet is – 10 years of research focussed on determining how to solve the combinatorial optimization problems that underlie strategic sourcing decision optimization problems quickly and optimally. Everything else is just icing on the cake.