Pyomo：无法将非线性约束转换为线性约束

Question

我目前正在研究一个线性编程问题，我们将会话分配给某些护理人员，并且约束给了我一个非线性错误。 在放置约束的代码之前，我将介绍该约束中使用的所有模型项。

• model.CASE_COMBINATIONS 是一个集合，对应于两个系列之间的叉积以及会话的 id（也是一个集合）。假设这代表了所有情况的组合。 这是该集的代码：

    model.CASE_COMBINATIONS = pe.Set(
            initialize=product(
                self.df_sessions["idx"].unique(),
                self.df_sessions["idx"].unique(),
            ),
            dimen=2,
        )

• model.SESSION_ASSIGNED 是模型的一个变量，它指示是否选择某个会话由某个护理人员执行。如果护理人员被分配给该会话，则此变量通过将 1 分配给元组（会话，护理人员）来实现此目的，否则分配 0。

这是 model.SESSION_ASSIGNED 和 model.TASKS 的代码：

model.SESSION_ASSIGNED = pe.Var(model.TASKS, domain=pe.Binary)

model.TASKS = pe.Set(
            initialize=model.CASES * model.CAREGIVERS, dimen=2
        )

• model.CASE_BIGGER 是一个参数，它告诉我们，对于每个会话元组（case1，case2），case1 的 idx 是否大于 case2。我们这样做是因为 idx 是有序的，因此这使我们能够知道哪个会话首先发生。 这是代码：

    model.CASE_BIGGER = pe.Param(
                model.CASE_COMBINATIONS, initialize=self._generate_case_bigger()

    def _generate_case_bigger(self):
            case_bigger = {}
            for case1, case2 in product(
                self.df_sessions["idx"].unique(), self.df_sessions["idx"].unique()
            ):
                case_bigger[(case1, case2)] = int(case1 > case2)
            return case_bigger

• model.COMMUTE 对应于客户端两个不同位置之间的通勤时间的参数，其中对于每个元组（session1，session2），我们将有一个到两者之间的通勤时间的映射。 这是代码：

    model.COMMUTE = pe.Param(
                model.CLIENT_CONNECTIONS,
                initialize=self._generate_clients_commute(),
            )

• model.IDX_CLIENTS 只是对应于我们为会话拥有的两组不同 id 之间的映射，我相信它与当前的问题基本无关。

现在对于具有非线性问题的约束：

def commute_care(model, caregiver):
    commute_expr = sum(
        [
            model.SESSION_ASSIGNED[case[0], caregiver] *
            model.SESSION_ASSIGNED[case[1], caregiver] *
            ( 
                model.CASE_BIGGER[case[1], case[0]] *
                model.COMMUTE[(model.IDX_CLIENTS[case[0]], model.IDX_CLIENTS[case[1]])] +

                (1 - model.CASE_BIGGER[case[1], case[0]]) *
                model.COMMUTE[(model.IDX_CLIENTS[case[1]], model.IDX_CLIENTS[case[0]])]
            )
            for case in model.CASE_COMBINATIONS
        ]
    )
    return model.COMMUTE_CARE[caregiver] == commute_expr

有了这个约束，我们想要计算每个护理人员的通勤时间。我们迭代不同案例的叉积，并计算每对案例是否将它们分配给同一个护理人员，如果是，我们计算它们之间的通勤时间。这些通勤时间的总和等于所有这些通勤时间的总和。 有谁知道如何将此约束转换为线性约束？ 谢谢你

Answer 1

从代码中退一步，您可以得到以下形式的表达式：

a[i,j]*x[i]*x[j]

其中 a 是常数，x 是二元变量。这可以使用众所周知的重构来线性化：

a[i,j]*y[i,j]
y[i,j] <= x[i]
y[i,j] <= x[j]
y[i,j] >= x[i]+x[j]-1

其中 y 是一个额外的二进制变量。 （y可以放宽到0到1之间连续）。