Nested branch-and-price for multi-mode nanosatellite task scheduling with interior-point regularization and GPU acceleration

The capabilities of nanosatellites are constrained by their limited power availability and size, which poses challenges for mission planning and operation. This study addresses the Offline Nanosatellite Task Scheduling (ONTS) problem by introducing multi-mode capability into the scheduling process, enhancing its relevance for more realistic, adaptable, and robust mission planning. We propose a Mixed-Integer Linear Programming (MILP) model for this problem that accommodates conventional resource and temporal constraints across multiple operational modes. The MILP model is improved with valid inequalities incorporating auxiliary variables alongside multi-mode cover cuts enhanced with lifting procedures. Furthermore, we introduce a Nested Branch-and-Price (NB&P) algorithm that enhances the standard branch-and-price approach by incorporating a dual-level optimization structure for handling hierarchical scheduling. This dual framework simultaneously facilitates job allocation and mode selection, employing dynamic column generation influenced by dual prices to progressively refine task schedules towards optimality. Additionally, enhanced interior-point methods have been effectively adapted for tackling large-scale instances, aligned with a GPU-accelerated dynamic programming solution utilizing CUDA technology. Empirical evaluations show that the modified MILP approach, combined with the NB&P algorithm, significantly improves computational efficiency, demonstrating up to a 629-fold reduction in computation time and consistently achieving zero-gap solutions.