Selective routing problem with synchronization
研究望远镜多目标光谱仪管理中出现的同步约束下的选择性路径问题，提出三种数学模型和分支定价切割算法，帮助天文学家在时间限制内选择并排序观测对象以最大化总优先级。
We introduce a new optimization problem arising in the management of a multi-object spectrograph in a telescope. The field of view of the spectrograph is divided in 55 contiguous and parallel spatial bands. Each band is associated with two opposite sliding bars that can be positioned to observe an astronomical object. The observation of an object requires the synchronized configuration of the bars in several contiguous bands to form a slitlet in the position of the object. A multi-slit pattern for the bars permits the simultaneous observation of several objects requiring bars of different bands. Each astronomer using this spectrograph propose a list of objects to observe. Since the instrument is quite demanded, the manager of the telescope imposes a time limitation to the astronomers, so they need to select a subset of objects from their lists. This paper describes and solves the selection problem. The problem must also find a sequence of configurations for the bars in each band to maximize the total priority of the selection, subject to some synchronization issues and the time limitation. We show three mathematical formulations. One of them is a set-partitioning model where a master problem manages the synchronization constraints and a subproblem generates columns satisfying the time limitation. We propose two branch-and-price-and-cut algorithms for solving the set-partitioning model, and discuss an extensive computational experiment showing the performance of the algorithms on two families of instances.