A significant challenge in making Expressive Commerce a reality is that the expressiveness and flexibility of buyer and seller interaction makes analysis an extremely complex combinatorial optimization problem. Specifically, this is a clearing problem, deciding which supply and demand alternatives to accept and reject (and to what extent in the case of partially acceptable alternatives) so as to satisfy all, or most of, the operational constraints.

Prior to CombineNet, no technology was capable of solving clearing problems of the scale and expressiveness created by Expressive Commerce; for example, Hohner et al. found integer programming techniques to be effective for sourcing problems only as large as 500 items and 5,000 bids. CombineNet's optimization and algorithm technology development has yielded speed improvements of 4-5 orders of magnitude.

There is significant structure in the Expressive Commerce problem instances, and it is paramount that the optimization engine, or solver, be sophisticated enough to take advantage of the structure. Mixed integer programming (MIP) techniques for tree search are quite good at taking advantage of the structure, and CombineNet takes advantage of those techniques. However, general-purpose MIP techniques that are embodied in the leading general-purpose MIP solvers are not sufficient for the clearing problems encountered in Expressive Commerce.

The optimization engine at the core of CombineNet ASAP uses highly sophisticated tree search algorithms to find the provably optimal solution. Given that the algorithms find the optimal answer, and the problem is NP-complete, in the worst-case the run-time has to be more than polynomial in the size of the input (unless P=NP). However, in practice on real-world optimization problems the algorithms run extremely fast: the median run-time is less than 1 second and the average is 20 seconds, with some outlier instances taking days. The algorithms are also anytime algorithms: they provide better and better solutions during the search process.

CombineNet's algorithm development began in 1997, and the company has 16 people working on the algorithms, half of them full time. The team has tested hundreds of techniques (some from the operations research and computer science literature and some invented at CombineNet) to see which ones enhance speed on market clearing problems. CombineNet published in detail the first generations of its search algorithms. The new ideas in these algorithms included different formulations of the basic combinatorial auction clearing problem (branching on items, branching on bids, and multi-variable branching), upper and lower bounding across components in dynamically detected decompositions, sophisticated strategies for branch question selection, dynamically selecting the branch selection strategy at each search node, the information-theoretic branching approach, sophisticated look-ahead techniques, solution seeding, primal heuristics, identifying and solving tractable cases at nodes techniques for exploiting part of the remaining problem falling into a tractable class, domain-specific preprocessing techniques, fast data structures, methods for handling reserve prices, and incremental winner determination and quote computation techniques.

CombineNet has also invented a host of techniques in the tree search algorithms that it has decided to keep proprietary, at least for now. They include different formulations of the market clearing problem, 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), etc.

While the academic literature on combinatorial auctions has focused on a variant where the only form of expressiveness is package bidding (sometimes supplemented with mutual exclusion constraints between bids), in CombineNet's experience with real problems the complexity is dominated by rich side constraints (business rules, preferences, etc.). Therefore, CombineNet has invested significant effort into developing techniques that deal with side constraints efficiently. CombineNet has faced several hundred different types of real-world side constraints. All of them are supported by CombineNet's software by abstracting into eight classes from an algorithmic perspective. This way, speed enhancements within each class get automatically leveraged across all side constraint types within the class.

The resulting optimal tree search algorithms are often 10,000 times faster than the state-of-the-art general-purpose MIP solvers on the hard instances of real-world market clearing. By and large the main reason for this drastic speed difference is that CombineNet specializes on a subclass of MIP problems and has 20,000 real-world instances in this subclass on which to improve its algorithms. The speed has allowed CombineNet's clients to handle drastically larger and more expressive optimization problems, for example, sourcing events with more than 2.5 million bids (on 168 thousand items, multiple units of each) or more than 300,000 side constraints.

The technology is incorporated into a back-end clearing engine which is used across all ASAP events, clients, and industries by CombineNet. The speed is critical to success in business applications: it allows non-technical business professionals to analyze alternatives in minutes rather than months. Given the complexities of these problems, and multiple stakeholder involvement, exploration of alternatives as enabled by combinatorial optimization is the key to success.