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. Cordone
Primo
;
G. Righini
Ultimo
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.
Earth observation satellites ; Lagrangean relaxation ; Combinatorial optimization.
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
2008
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/33672
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 2
social impact