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

 

ID

Variables

CPLEX (Optimal Found Value)

CPLEX (Time)

alphaQUBO (Optimal Found Value)

alphaQUBO (Time)

SPP01a

6,000

10872

7851

10872

53

SPP01c

6,000

22860

2598

22860

275

SPP01d

6,000

14798

14115

14793

12

SP002a

8,000

14959

15348

14959

34

SP002b

8,000

9621

18071

9621

74

SPP02c

8,000

30425

16423

30425

95

SPP02d

8,000

19882

10191

19816

19

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

 

Instance

Vars

Density %

CPLEX (Optimal Found Value)

CPLEX (Time)

alphaQUBO (Optimal Found Value)

alphaQUBO (Time)

1

10,000

25

7292

947

7292

378.2

2

10,000

50

4543

1543

4543

11.6

3

10,000

25

37968

284

37968

5.4

4

10,000

50

24297

8683

24297

1337

5

15,000

25

10930

66

10930

17.5

6

15,000

50

7174

2176

7047

Not Available

7

15,000

25

57834

993

57419

706.7

8

15,000

50

37962

2373

37671

556.8

9

20,000

259833

14900

50369

14900

1535.1

10

20,000

Not Available

9412

Not Available

9412

3.6

11

20,000

25

77448

2119

77198

1729.1

12

20,000

504786

50188

Not Available

50188

5.7

13

25,000

25

18517

589

18498

10

14

25,000

50

12008

1847

11923

813.8

15

25,000

25

96690

548

96445

1474.3

16

25,000

50

63173

18903

63156

98

17

30,000

25

22405

859

22405

14.1

18

30,000

50

14457

2507

14457

1551.7

19

30,000

25

115950

16031

115687

410.3

20

30,000

50

76276

17393

75684

11.5

21

40,000

25

30592

2532

30445

894.1

22

40,000

50

19815

7184

19558

11.5

23

40,000

25

155162

19152

155069

393.4

24

40,000

50

101835

10286

101835

12.9