All supplementary data for a paper

The Set Covering Problem (SCP) and its variants represent cornerstone NP-hard com- binatorial optimization challenges that model critical operational applications, including airline and railway crew scheduling, urban transit driver planning, telecommunications network design, and computational biology. In 2000, Alefragis, Sanders, Takkula, and Wedelin introduced a scalable parallelization and active set strategy based on Wedelin’s Lagrangian relaxation heuristic for industrial crew scheduling at Carmen Systems. Over the ensuing two and a half decades, high-performance computing hardware has undergone a profound paradigm shift: from distributed networks of single-core RISC workstations in- terconnected by 100 Mbps Fast Ethernet to massively heterogeneous nodes featuring deep multi-level cache hierarchies and graphics processing units (GPUs) boasting thousands of SIMD/SIMT compute cores. In this work, we present a comprehensive modernization and hardware-software co- design of the parallel active set solver (PAQS). First, we refactor the core algorithms from obsolete dialect-specific Unix code into standard ISO C++17, implementing dual Compressed Sparse Column (CSC) and Compressed Sparse Row (CSR) structures, cache- aligned vectorized containers, and an encapsulated MPI-3/4 interface featuring a deter- ministic four-tuple reduction operator and a transparent zero-overhead single-node stub. Second, we engineer a massively parallel CUDA acceleration subsystem, introducing warp- synchronous register-shuffling kernels for row-wise critical dual reductions and designing a novel Direct Full-GPU solver mode that eliminates host-device transfer bottlenecks and executes tens of thousands of coordinate updates per second directly within GPU mem- ory. Third, we perform an extensive computational study across six benchmark suites encompassing 180+ instances: 87 Beasley OR-Library problems, seven massive Italian Railways instances (n > 106), 14 American Airlines crew scheduling instances, urban bus scheduling problems, hard cost-correlated instances, and Euclidean geometric routing problems. Our empirical results demonstrate that modernized PAQS matches or improves the Best Known Solutions (BKS) across over 82% of OR-Library benchmarks and sets superior upper bounds on American Airlines instances. On massive railway instances with over 11 million nonzeros, PAQS identifies near-optimal feasible solutions in under 5 seconds. In contrast, the state-of-the-art commercial MIP solver Gurobi struggles within a rapid 30-second operational window (e.g., returning an incumbent of 2224 on rail4284), and even when granted plenty of time (5 full minutes / 300 seconds across 16 threads), it still cannot find comparable solutions on the largest instances (achieving 1078 vs. PAQS 1067 on rail4284, 952 vs. PAQS 948 on rail2586, and 1545 vs. PAQS 1532 on rail4872). Our findings highlight the enduring necessity and dramatic computational advantages of Lagrangian-based coordinate search heuristics accelerated by GPU architectures for ultra-large industrial integer programs.