A Branch-and-Price Algorithm for Scheduling Observations on a Telescope

Nicolas Catusse, Hadrien Cambazard, Nadia Brauner, Pierre Lemaire, Bernard Penz, Anne-Marie Lagrange, Pascal RubiniIJCAI 2016

Abstract

Scheduling telescope time is a high-stakes optimization challenge where efficiency directly impacts scientific output. This paper addresses a specific "mandatory instant" constraint—requiring observations to occur exactly as a target crosses its meridian—to ensure peak image quality. We present a specialized Branch-and-Price algorithm that leverages the unique properties of this constraint to find optimal schedules, significantly outperforming traditional heuristics and standard solvers.

Introduction

Astronomical imaging surveys often involve hundreds of targets observed over several months. Because telescope time is a scarce resource, the objective is to maximize the total "scientific interest" (a weighted sum) of the targets successfully scheduled. The authors identify a critical, under-studied constraint: the mandatory instant. In many surveys, a target must be observed at its highest point in the sky (the meridian) to minimize atmospheric interference and field rotation. This requirement transforms the task into a parallel machine scheduling problem with time-windows and a mandatory processing instant.

Theoretical Complexity

The researchers established that while single-night versions of this problem are often tractable, the multi-night extension is significantly more difficult. Specifically, they prove that the multi-night version is NP-complete, meaning the computational effort required to find an optimal solution grows exponentially with the number of targets and nights.

Table 1: Computational complexity of various scheduling scenarios, highlighting the NP-complete nature of parallel machine problems.

The Branch-and-Price Framework

To solve this NP-complete problem, the paper proposes a Branch-and-Price algorithm. This approach integrates three core optimization techniques:

  1. Column Generation: The problem is decomposed into a "Master Problem" that selects the best combination of nightly schedules and a "Sub-problem" that generates new, high-value schedules for individual nights.
  2. Dynamic Programming (DP): The "mandatory instant" constraint imposes a fixed chronological order on observations within a single night (Property 2). If Target A’s meridian precedes Target B’s, Target A must be scheduled first. This property allows for a highly efficient DP algorithm to solve the nightly sub-problems.
  3. Constraint Programming (CP): CP is utilized to "prune" the search tree, rapidly discarding infeasible schedules where target durations overlap their mandatory instants.

Performance Evaluation

The algorithm was tested on a real-world dataset from the SPOT tool and 20 synthetic datasets mimicking realistic survey conditions, with up to 1,000 targets and 142 nights.

Table 2: Comparative performance of the Branch-and-Price (B&P) algorithm against Mixed-Integer Programming (MIP) and heuristic (SPOT) baselines.

As shown in the experimental results, the Branch-and-Price algorithm found and proved the optimal solution for 18 out of 21 datasets. In the remaining cases, the optimality gap was negligible (less than 0.11%). In contrast, standard Mixed-Integer Programming (MIP) solvers failed to find any feasible solutions for larger datasets within a two-hour limit. Furthermore, the B&P approach consistently outperformed the existing SPOT heuristic, capturing up to 29% more scientific value in some instances.

Conclusion

The inclusion of the "mandatory instant" constraint, while theoretically restrictive, provides a computational structure that the Branch-and-Price algorithm successfully exploits. This method offers a practical, exact solution for complex telescope scheduling, ensuring that scarce observation time is utilized to its maximum scientific potential. Future work will look to incorporate variables such as slew times, weather uncertainty, and dynamic atmospheric conditions into the model.

Summary updated

BibTeX
@inproceedings{catusse2016branch,
  author = {Nicolas Catusse and Hadrien Cambazard and Nadia Brauner and Pierre Lemaire and Bernard Penz and Anne-Marie Lagrange and Pascal Rubini},
  title = {{A Branch-and-Price Algorithm for Scheduling Observations on a Telescope}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure