strong formulation for the spot-5 daily photograph scheduling problem
Earth observation satellites, such as the SPOT-5, take photographs of the earth according to consumers demands. Obtaining a good schedule for the photographs is a combinatorial optimization problem known in the literature as the daily photograph scheduling problem (DPSP). The DPSP consists of selecting a subset of photographs, from a set of candidates, to different cameras, maximizing a profit function and satisfying a large number of constraints. Commercial solvers, with standard integer programming formulations, are not able to solve some DPSP real instances available in the literature. In this paper we present a strengthened formulation for the DPSP, based on valid inequalities arising in node packing and 3-regular independence system polyhedra. This formulation was able, with a commercial solver, to solve to optimality all those instances in a short computation time.
| Departamento de Ingeniería Industrial |
| Facultad de Ciencias Físicas y Matemáticas | Universidad de Chile |
República 701, Santiago, Chile | Teléfono:(562)978-4072 | Fax:(562)978-4011