Conference Agenda

The length-constrained cycle partition problem (LCCP) is a graph optimization problem where the goal is to partition the set of nodes into as few cycles as possible. Each node is linked to a critical time and the length of a cycle must not exceed the critical time of any node in it. We formulate the LCCP as a set partitioning problem (SPP), which can be solved to global optimality by branch and price. For the SPP, we observe on standard benchmark instances from the literature a consistently small absolute gap between the root node relaxation and the optimal primal bound seemingly observing a round-up property. We say that a problem has the integer round-up property (IRUP) if the objective value of the relaxation of an integer program (IP) rounded up is equal to the optimal objective value of the IP. In this paper we investigate if the LCCP has the IRUP and the relaxed modified IRUP (MIRUP). We define several classes of LCCP with the IRUP, and provide counterexamples with small coefficients for the general case. Additionally, we present a computational study investigating whether the MIRUP holds for the SPP on randomly generated instances.