Scholarlink

<p>We investigate using Constraint Programming (CP) and Domain-Independent Dynamic Programming (DIDP) to solve the master problem in Logic-based Benders Decomposition (LBBD) models, focusing on the challenge of feasibility cut formulation. For CP, we exploit variable assignment bounds, variable assignment counting, and global constraints to construct three combinatorial cut encodings. For the state-based DIDP model, we propose two cut encoding approaches: using additional preconditions of state transitions or adding state constraints. Each of these approaches can be modeled using integer numeric variables or set variables, resulting in four novel encodings. We apply the three CP variants and four DIDP variants to the LBBD model of the simple assembly line balancing problems with sequence-dependent setup times type-1 (SUALBP-1). Experimental results show all approaches outperform a mixed-integer programming (MIP) based master problem and the state-of-the-art monolithic MIP model, with the three CP variants being superior to all of the DIDP approaches. Though the evaluation is specific to SUALBP-1, the proposed approaches can be used for other problems where LBBD with feasibility cuts is applicable.</p>

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

Solving logic-based benders decomposition master problems with constraint programming and domain-independent dynamic programming

  • 期刊论文

  • 发表日期：

    2025年12月22日

查看全文
  • Jiachen Zhang,
  • J. Christopher Beck

摘要

We investigate using Constraint Programming (CP) and Domain-Independent Dynamic Programming (DIDP) to solve the master problem in Logic-based Benders Decomposition (LBBD) models, focusing on the challenge of feasibility cut formulation. For CP, we exploit variable assignment bounds, variable assignment counting, and global constraints to construct three combinatorial cut encodings. For the state-based DIDP model, we propose two cut encoding approaches: using additional preconditions of state transitions or adding state constraints. Each of these approaches can be modeled using integer numeric variables or set variables, resulting in four novel encodings. We apply the three CP variants and four DIDP variants to the LBBD model of the simple assembly line balancing problems with sequence-dependent setup times type-1 (SUALBP-1). Experimental results show all approaches outperform a mixed-integer programming (MIP) based master problem and the state-of-the-art monolithic MIP model, with the three CP variants being superior to all of the DIDP approaches. Though the evaluation is specific to SUALBP-1, the proposed approaches can be used for other problems where LBBD with feasibility cuts is applicable.