This work focuses on a combinatorial optimization problem that arises in the planning of the transshipment of containers between trains. In this application, loading/unloading of trains must be performed in a loading area that is not big enough to host all the trains at the same time. For this reason, the transshipment must be made by sequentially unloading/loading groups of trains that fit in this loading area. If needed, containers may temporarily wait in a storage area. For practical reasons, the groups of trains must be designed in such a way that each train needs to enter only once into the loading area. The goal is to minimize the use of the storage area.

Following previous works, we have used a directed graph with nodes associated with trains to model this situation. As a result, this can be seen as an acyclic graph partitioning problem (AGPP). In order to solve the AGPP, we have developed a new integer programming formulation that takes advantage of some properties of its optimal solutions. This formulation has been strengthened with several families of valid inequalities, often used to break the awkward symmetries inherent to the problem. This new formulation has allowed us to obtain optimal solutions improving the efficiency of the state-of-the-art algorithm for this problem.