Why CNES selected Hexaly 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 budget and 2,400 employees, CNES is a significant player in the European space scene. In 2018, CNES launched a public tender to solve a satellite communication scheduling problem. Hexaly Optimizer 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
- 13 stations
- 13 satellites
- 6,000 slots
- 220 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 Hexaly, CNES now builds near-optimal schedules in 45 seconds on average. 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 a minute of running time
Why Hexaly
After an extensive benchmark against IBM ILOG CPLEX (Mixed-Integer Linear Programming) and IBM ILOG CP Optimizer (Constraint Programming), CNES selected Hexaly to solve satellite communication scheduling problems. Several points motivated this choice. First, thanks to its unique primal heuristics, Hexaly 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, Hexaly 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 Hexaly’s ease of use and performance, the responsive support provided by Hexaly optimization scientists and their ability to understand CNES business needs were crucial.
Please look at our customers’ webpage to discover more industry case studies. Are you interested in trying out Hexaly? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to talk about your optimization problems.