Set Partitioning Benchmarks

Benchmarks: Set Partitioning Problem

The set partitioning problem (SPP) seeks to partition a set of items into subsets such that each item appears in exactly one subset and the cost of the subsets chosen is minimized. This problem can be used to model many important real-life transportation problems, including airline crew scheduling (Hoffman and Padberg, 1993; Barnhart et al., 1998; Mingozzi et al., 1999), vehicle scheduling (Ribeiro and Soumis, 1994; Borndörfer, Löbel, and Weider, 2008; Hadjar, Marcotte, and Soumis, 2006; Boschetti, Mingozzi, and Ricciardelli, 2004) and vehicle routing (Agarwal, Mathur, and Salkin, 1989;Baldacci, Christofides, and Mingozzi, 2008;Bramel and Simchi-Levi, 1997). Additional applications are described by Balas and Padberg, 1976 and El-Darzi and Mitra, 1995

Benchmarks:

As shown in Table 1, AlphaQUBO found optimal solutions for the first 7 of these modest sized problems. AlphaQUBO obtained a better solution than other solvers on the market including CPLEX and delivered a “time to best” by a wide margin on all 8 problems.   

Table 1

Table 2 highlights how AlphaQUBO quickly found best known solutions for all 24 problems. CPLEX was able to find best known solutions for only 11 of the 24 problems. AlphaQUBO had a “time to best” advantage over CPLEX that typically ranged from 1 to 3 orders of magnitude. All told, AlphaQUBO outperformed CPLEX be a wide margin in terms of both solution quality and solution time.

Table 2