如何为满足批量约束的订单排序场景构建对应数学整数约束

基础变量定义 #

先明确输入参数：

• 总订单数：N
• 订单类别总数：K（示例中K=2，对应A、B两类）
• 第k类订单总数量：D_k（示例中D_A=9, D_B=6）
• 批量最小长度：m，批量最大长度：M（示例中m=4）
  定义两类0-1决策变量：
• y_{i,k} ∈ {0,1}：第i个排序位置是否为k类订单，取值1代表是，0代表否
• start_{i,k} ∈ {0,1}：第i个排序位置是否为k类订单的一个新批量的起始点，取值1代表是，0代表否，就是你原本思路里x_i对应的变量定义

核心约束集合 #

基础位置约束 #

每个位置仅能分配一类订单，且每类订单总数量匹配需求：

• 对任意位置i ∈ [1,N]：∑_{k=1}^K y_{i,k} = 1
• 对任意类别k ∈ [1,K]：∑_{i=1}^N y_{i,k} = D_k

批量起始点判定约束 #

仅当当前位置是k类订单，且前一位置不是k类订单（或当前是第一个位置）时，才会触发k类订单的批量起始标记：

• 对任意类别k，任意位置i ≥ 2：start_{i,k} ≥ y_{i,k} - y_{i-1,k}
• 对任意类别k，第一个位置：start_{1,k} = y_{1,k}

最小批量长度约束 #

如果某位置触发了k类的批量起始标记，则接下来至少m个连续位置都必须是k类订单，刚好匹配你提到的「x_i=1则后续m个值都为1」的逻辑：

• 对任意类别k，任意位置i ∈ [1, N - m + 1]：∑_{t=i}^{i+m-1} y_{t,k} ≥ m * start_{i,k}
• 对任意类别k，任意位置i > N - m +1：start_{i,k} = 0（剩余位置不足m个，无法开启新批量）

最大批量长度约束 #

避免连续同类型订单长度超过M，两种实现方式二选一即可：

方式1（简单易实现）

任意连续M+1个位置中，k类订单的数量最多为M：

• 对任意类别k，任意位置i ∈ [1, N-M]：∑_{t=i}^{i+M} y_{t,k} ≤ M

方式2（和起始标记联动）

如果某位置触发了k类的批量起始标记，则第i+M个位置不能为k类（或超出总长度）：

• 对任意类别k，任意位置i ∈ [1, N-M]：y_{i+M,k} ≤ 1 - start_{i,k}

示例适配说明 #

你给出的示例中仅限制了最小批量为4、无最大批量限制时，只需将M设为总订单数15即可，上述约束可以覆盖你给出的两个合法排序结果，同时会排除出现长度小于4的同类型批量的非法排序。

内容的提问来源于stack exchange，提问作者Zhe