The swath segment selection problem (SSSP) is an NP-hard combinatorial optimization problem arising in the context of planning and scheduling satellite operations. It was defined by Muraoka et al. and Knight & Smith, who respectively proposed a greedy algorithm, named ASTER, and a branch-and-bound algorithm based on a network flow relaxation. Here we tackle the problem with more advanced mathematical programming tools: using a Lagrangean relaxation, coupled with a Lagrangean heuristic and subgradient optimization, we solve in one hour instances with up to 500 000 swath segments within 0.4% of the optimum. The algorithm also proves experimentally superior to commercial MIP solvers in computing heuristic solutions.
