Why CNES selected LocalSolver to schedule satellite communication
Centre National d’Etudes Spatiales (CNES) is the French space agency responsible for shaping and implementing France’s space policy. With a €2.3 billion turnover and 20,000 employees in 2021, CNES is a significant player in the European space scene. In 2018, CNES launched a public tender to solve a satellite communication scheduling problem. LocalSolver won an extensive benchmark, including the Mixed-Integer Linear Programming (MILP) solver IBM ILOG CPLEX and the Constraint Programming (CP) solver IBM ILOG CP Optimizer.
The satellite communication scheduling problem
Every week, CNES needs to determine a communication schedule between satellites in orbit and ground stations positioned around the globe. The satellites must communicate regularly to send the data they collected (radar or meteorological), their position (orbit verification), and, if necessary, receive commands.
The quality of a schedule depends on many different criteria. For example, the cumulated time spent communicating with certain satellites over certain periods should be within a given time window. Other satellites should only communicate with stations during precise time periods. Others still have a limited number of communications allowed per day. All these criteria are made into penalty-minimizing objective functions.
Input data
- 10 stations
- 10 satellites
- 3,000 potential slots
- 150 reservation criteria
Decisions
For each slot, each station, and each satellite, decide if this station communicates with this satellite during this slot
Constraints
- At each time, one station communicates with at most one satellite
- At each time, one satellite communicates with at most one station
Objectives
For each reservation criterion, minimize a feasibility measure. For example, minimize the number of slots to reach the required minimum per day and satellite, or the number of minutes exceeding the maximum threshold allowed for a station on a given day.
Mathematical model and results
Using LocalSolver, CNES now builds near-optimal schedules in a few seconds. A typical instance of this problem, corresponding to a 1-week schedule, comprises:
- 3,000 binary variables
- 10,000 constraints
- 15 to 30 objectives, depending on the reservation criteria
- Near-optimality reached on all objectives in less than 30 seconds
Why LocalSolver
After an extensive benchmark against IBM ILOG CPLEX (Mixed-Integer Linear Programming) and IBM ILOG CP Optimizer (Constraint Programming), CNES selected LocalSolver to solve satellite communication scheduling problems. Several points motivated this choice. First, thanks to its unique primal heuristics, LocalSolver offers near-optimal solutions in seconds, whereas their previous tool regularly failed to deliver solutions, so they had to build a schedule by hand. Moreover, LocalSolver allows multiobjective optimization, also known as “goal programming.” This allows “partial” solutions to be delivered to users when all the requirements are not achievable. This cannot be implemented straightforwardly with IBM solvers. Beyond LocalSolver’s ease of use and performance, the responsive support provided by LocalSolver optimization scientists and their ability to understand CNES business needs were crucial.
Please look at our customers‘ webpage for more case studies in various industries. Are you interested in trying it out? Register in a minute and get licenses for free. Then, contact us with any questions: we will gladly help you solve your optimization problems.