Solving the swath segment selection problem through Lagrangean relaxation

The swath segment selection problem (SSSP  ) is an NPNP-hard combinatorial optimization problem arising in the context of planning and scheduling satellite operations. It was defined by Muraoka et al. [ASTER observation scheduling algorithm. In: Proceedings of SpaceOps 1998, Tokyo, Japan, 1998] and Knight and Smith [Optimal nadir observation scheduling. In: Proceedings of the fourth international workshop on planning and scheduling for space (IWPSS 2004), Darmstadt, Germany, 2004], 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%0.4% of the optimum. The algorithm also proves experimentally superior to commercial MIP solvers in computing heuristic solutions.