Exact algorithms for the satellite image selection problem

Space development is more relevant than ever with the increasing number of satellite launches for various applications. The amount of space data collected daily is growing exponentially and many customers are interested in continuously monitoring different regions of the Earth. It often requires stitching together many images from other providers to cover an Area of Interest (AOI), resulting in a mosaic. Each satellite image has various parameters, such as cost, download time, cloud coverage, and resolution. The main question is how to optimally select the subset of available images to fully cover the AOI while minimizing total cost and cloud coverage. The problem is known as satellite image mosaic selection (SIMS).Manual selection of promising images is often impossible, especially when dealing with large AOIs or many photos. To solve the problem, we propose several new exact algorithms using different techniques, such as branch-and-bound or mixed-integer linear programming. These algorithms show quality and efficiency compared with existing approaches and are expected to benefit various industrial applications.