Scholarlink

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 the cycle. We formulate the LCCP as a set partitioning problem, which can be solved to global optimality by branch and price. On standard benchmark instances from the literature, this formulation consistently satisfies the integer round-up property (IRUP), i.e., the objective value of the root node relaxation rounded up is equal to the optimal objective value. In this paper we construct counterexamples with small coefficients for which the set partitioning formulation of LCCP does not have IRUP, and provide some simple conditions under which IRUP holds. Our computational tests reveal that 30 out of 51 standard test instances with IRUP can be explained by these conditions.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Investigating Round-Up Properties for the Length-Constrained Cycle Partition Problem

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Kilian Runnwerth,
  • Mohammed Ghannam,
  • Ambros Gleixner

摘要

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 the cycle. We formulate the LCCP as a set partitioning problem, which can be solved to global optimality by branch and price. On standard benchmark instances from the literature, this formulation consistently satisfies the integer round-up property (IRUP), i.e., the objective value of the root node relaxation rounded up is equal to the optimal objective value. In this paper we construct counterexamples with small coefficients for which the set partitioning formulation of LCCP does not have IRUP, and provide some simple conditions under which IRUP holds. Our computational tests reveal that 30 out of 51 standard test instances with IRUP can be explained by these conditions.