logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Solving the swath segment selection problem through Lagrangean relaxation

delete2008-03-01
delete5
PRE
AI
R
Roberto Cordone
F
Federico Gandellini
G
Giovanni Righini *
DOI：10.1016/j.cor.2006.04.005delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
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. [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 500000 swath segments within 0.4% of the optimum. The algorithm also proves experimentally superior to commercial MIP solvers in computing heuristic solutions. (c) 2006 Elsevier Ltd. All rights reserved.
Keywords:
earth observation satellites
lagrangean relaxation
combinatorial optimization
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

C
Computers and Operations Research
IF:
4.3
Papers:
6.5K
Citations:
1.8W

Organization

No organization information available