The swath segment selection problem (SSSP) is an Formula Not Shown -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 Formula Not Shown of the optimum. The algorithm also proves experimentally superior to commercial MIP solvers in computing heuristic solutions.
Solving the swath segment selection problem through Lagrangean relaxation / R. Cordone, F. Gandellini, G. Righini. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 35:3(2008), pp. 854-862.
Solving the swath segment selection problem through Lagrangean relaxation
R. CordonePrimo
;G. RighiniUltimo
2008
Abstract
The swath segment selection problem (SSSP) is an Formula Not Shown -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 Formula Not Shown of the optimum. The algorithm also proves experimentally superior to commercial MIP solvers in computing heuristic solutions.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.