多矩阵列选择问题的线性规划（LP）建模求助

嘿，刚接触线性规划的时候碰到这种问题确实容易懵，我来帮你一步步拆解建模思路——咱们先把问题拆成严格要求同行所有选中列元素相同和放松到至少p%列元素相同两种场景来梳理：

先明确基础符号定义 #

先把变量和矩阵的标记理清楚，方便后续建模：

• 给10个矩阵编号：M_1, M_2, ..., M_{10}，每个都是100行×200列的整数矩阵
• 对第k个矩阵，它的第j列记为c_{k,j}（k=1..10, j=1..200）
• 行位置编号：i=1..100
• 定义0-1选择变量x_{k,j}：如果从第k个矩阵选中第j列，x_{k,j}=1，否则为0

场景1：严格要求同行所有10列元素相同 #

你的目标是最大化「对应行位置上，10个选中列元素完全相同」的行数。

目标函数

定义0-1变量y_i：如果第i行的10个选中列元素全相同，y_i=1，否则为0。我们要最大化满足条件的行数总和：

maximize  Σ(y_i)  （i从1到100）

约束条件

1. 每个矩阵必选且仅选一列：

   Σ(x_{k,j}) = 1  （对每个k=1..10，j从1到200）
   

2. 保证y_i=1时，同行所有选中列元素一致：
   这里需要引入辅助变量：对每个行i和整数v（矩阵中出现过的元素值），定义0-1变量z_{i,v}：如果第i行的10个选中列元素全为v，z_{i,v}=1，否则为0。
   • 每个行最多对应一个统一值：Σ(z_{i,v}) ≤ 1（对每个i）
   • y_i = Σ(z_{i,v})（对每个i）——y_i为1当且仅当存在某个v使得该行全为v
   • 约束选中列的元素匹配：如果第k个矩阵的第j列在第i行的元素≠v，那么不能同时选中该列且让该行全为v：

     x_{k,j} + z_{i,v} ≤ 1  （对每个i,k,j，当M_k[i][j]≠v时）
     

场景2：放松到至少p%的列元素相同 #

如果要求没那么严格，比如希望每行至少有 T = ⌈10×p%⌉ 个选中列元素相同（比如p=80时，T=8），我们可以分两种目标来建模：

目标A：最大化满足条件的行数

定义0-1变量y_i：如果第i行至少有T个选中列元素相同，y_i=1，否则为0。目标是：

maximize  Σ(y_i)  （i从1到100）

需要额外引入变量：

• 对每个行i和值v，定义w_{i,v}：第i行中选中列元素为v的数量（整数变量）
• 定义t_i：第i行中相同元素的最大出现次数

约束补充：

1. 计算w_{i,v}的取值：

   w_{i,v} = Σ( x_{k,j} )  （对每个i,v，k从1到10，j遍历M_k第i行元素为v的列）
   

2. 关联t_i和w_{i,v}：t_i是该行相同元素的最大次数，所以：

   t_i ≤ w_{i,v} + 10×(1 - z_{i,v})  （对每个i,v）
   Σ(z_{i,v}) = 1  （对每个i）
   

   这里z_{i,v}是0-1变量，表示是否选v作为该行的“众数值”，10是大常数（最多10列），确保当z_{i,v}=1时，t_i≤w_{i,v}，其他v的约束自动失效。
3. 关联y_i和t_i：

   t_i ≥ T×y_i
   t_i ≤ 10  （对每个i）
   

   当y_i=1时，t_i必须≥T；y_i=0时，t_i可以是任意值（但不超过10）。

目标B：最大化所有行的“相同元素次数总和”

如果你的目标是让所有行的相同元素最大次数加起来尽可能大（比如某行有7个相同元素，另一行有9个，总和是16），那目标函数直接改成：

maximize  Σ(t_i)  （i从1到100）

约束和上面的t_i、w_{i,v}约束一致即可。

一些实操提示 #

• 因为选列是离散的0-1选择，这本质是整数线性规划（ILP），普通LP求解器可能需要开启整数规划支持
• 枚举值v的时候，不用考虑所有整数，只需要枚举每个行i中实际出现过的元素值，能大幅减少变量数量
• 如果矩阵元素取值范围很大，可以先预处理每个行的元素频率，只保留出现过的v值

备注：内容来源于stack exchange，提问作者AlexG