IBM ILOG CPLEX双列表遍历与选址优化求解咨询

一、能否求得最优解？ #

这个问题属于带约束的设施选址-分配问题，是典型的混合整数规划变种（曼哈顿距离的绝对值可通过CPLEX原生支持的线性化处理）。针对你当前的规模（42个配送点、最多5个设施点），CPLEX完全可以求得最优解：

• 变量规模：布尔变量共5×42+5=215个，连续变量仅5×2=10个，整体变量数极少
• 约束数量：总约束数不到300个，属于求解器可快速处理的小问题范畴

二、模型代码修正与迭代操作优化 #

你当前的代码存在索引逻辑错误，同时可优化区域参数的迭代使用，以下是修正后的方案：

1. 关键错误修正 #

• 决策变量X定义错误：无需[1..L,1..L]的大数组，改为X[1..N,1..2]即可，对应每个设施点的(x,y)坐标
• 连接变量C维度错误：应改为C[1..N,1..NDO]，表示设施点到配送点的连接关系
• 目标函数索引错误：曼哈顿距离应为设施n的坐标到配送点d的坐标的距离，修正后逻辑如下：

minimize sum(n in 1..N) sum(d in 1..NDO) (C[n,d] * (abs(X[n,1] - XDO[d,1]) + abs(X[n,2] - XDO[d,2])));

2. 区域参数迭代优化（对应6个区域的约束） #

针对你提到的6个区域（A-F）的XMIN/XMAX参数，提供两种迭代使用方案：

方案1：设施点可选择任意区域

新增布尔变量绑定设施与区域，实现每个设施点落在某一个区域内：

dvar boolean AssignArea[1..N, 1..NA]; // 设施n是否分配到区域a

subject to {
    // 每个设施点仅绑定一个区域（未建设的设施无绑定）
    forall(n in 1..N) sum(a in 1..NA) AssignArea[n,a] == D[n];
    
    // 设施坐标受绑定区域的XMIN/XMAX约束
    forall(n in 1..N, a in 1..NA) {
        X[n,1] >= XMIN[a,1] * AssignArea[n,a];
        X[n,1] <= XMAX[a,1] * AssignArea[n,a];
        X[n,2] >= XMIN[a,2] * AssignArea[n,a];
        X[n,2] <= XMAX[a,2] * AssignArea[n,a];
    }
}

方案2：设施点固定对应区域

若需求是6个设施点分别对应6个区域，直接将N设为NA=6，遍历每个设施点绑定对应区域：

int N = NA; // 改为6，对应6个区域

subject to {
    forall(n in 1..N) {
        X[n,1] >= XMIN[n,1] * D[n];
        X[n,1] <= XMAX[n,1] * D[n];
        X[n,2] >= XMIN[n,2] * D[n];
        X[n,2] <= XMAX[n,2] * D[n];
    }
}

3. 完整修正代码 #

///// Constants /////////////////////////////////////////////////////////////////////////////////////////////////////

// Number of centers
int N = 5;  // 若对应6个区域，改为NA即可
  
// 区域参数（A-F共6个）
int NA = 6;                     
float XMIN[1..NA, 1..2] = [     
        [51.0,      123.5],     // Area A
        [112.0,     64.0],      // Area B
        [183.25,    37.5],      // Area C
        [231.25,    80.0],      // Area D
        [216.75,    151.25],    // Area E
        [111.75,    177.75]     // Area F
 ];
 
float XMAX[1..NA, 1..2] = [ 
        [118.5,     151.75],    // Area A
        [185.75,    122.0],     // Area B
        [263.5,     61.75],     // Area C
        [269.25,    114.0],     // Area D
        [245.25,    176.5],     // Area E
        [153.0,     191.25]     // Area F
 ];

 // 区域土地成本
float cl[1..NA] = [600, 700, 1000, 200, 400, 900];
 
// 配送点坐标
int NDO = 42;                  
float XDO[1..NDO, 1..2] = [    
        [85.5,  99.25],     // 1.Neuchâtel
        [58.0,  152.25],    // 2.Lausanne
        [25.75, 186.0],     // 3.Genève
        [108.75,83.5],      // 4.Biel
        [62.75, 122.25],    // 5.Yverdon-Les-Bains
        [125.0, 104.5],     // 6.Bern
        [102.75,118.75],    // 7.Fribourg
        [98.25, 142.75],    // 8.Bulle
        [138.75,126.5],     // 9.Thun
        [154.25,135.0],     // 10.Interlaken
        [246.75,186.75],    // 11.Bellinzona
        [228.25,188.75],    // 12.Locarno
        [280.0, 116.5],     // 13.Chur
        [213.5, 21.0],      // 14.Schaffhausen
        [118.75,58.5],      // 15.Delémont
        [133.0, 76.0],      // 16.Solothurn
        [146.5, 45.25],     // 17.Liestal
        [205.75,80.25],     // 18.Zoug
        [214.5, 109.75],    // 19.Altdorf
        [185.25,110.0],     // 20.Sarnen
        [195.25,102.0],     // 21.Stans
        [189.5, 92.75],     // 22.Luzern
        [170.75,56.0],      // 23.Aarau
        [208.0, 58.75],     // 24.Zürich
        [235.5, 38.5],      // 25.Frauenfeld
        [270.5, 52.75],     // 26.Sankt-Gallen
        [265.75,56.5],      // 27.Herisau
        [275.25,61.25],     // 28.Appenzell
        [246.5, 95.0],      // 29.Glaris
        [121.5, 180.75],    // 30.Sion
        [136.25,37.0],      // 31.Basel
        [214.5, 97.0],      // 32.Schwyz
        [282.5, 83.0],      // 33.Vaduz
        [223.5, 46.25],     // 34.Winterthur
        [171.0, 173.0],     // 35.Brig
        [95.25, 197.0],     // 36.Martigny
        [141.0, 211.0],     // 37.Zermatt
        [241.0, 207.0],     // 38.Lugano
        [307.5, 116.25],    // 39.Davos
        [99.0,  53.5],      // 40.Porrentruy
        [33.5,  165.5],     // 41.Nyon
        [204.25,154.0]      // 42.Airolo
];
///// 决策变量 ///////////////////////////////////////////////////////////////////////////////////////////

dvar float X[1..N, 1..2];  // 每个设施点的(x,y)坐标
dvar boolean D[1..N];       // 是否建设该设施点
dvar boolean C[1..N, 1..NDO];  // 设施点n是否连接配送点d

///// 目标函数 ///////////////////////////////////////////////////////////////////////////////////////////

minimize sum(n in 1..N) sum(d in 1..NDO) (C[n,d] * (abs(X[n,1] - XDO[d,1]) + abs(X[n,2] - XDO[d,2])));

///// 约束条件//////////////////////////////////////////////////////////////////////////////////////////////////
subject to {
  
// C1: 每个配送点必须且只能连接一个设施点
forall(d in 1..NDO) {
    sum(n in 1..N) C[n,d] == 1;
};

// C2: 仅当设施点被建设时，才能连接配送点
forall(n in 1..N, d in 1..NDO) {
    C[n,d] <= D[n];
};

// C3: 至少建设一个设施点
sum(n in 1..N) D[n] >= 1;

// C4: 最多建设N个设施点
sum(n in 1..N) D[n] <= N;

// C5-C6: 设施点坐标约束（若需可选区域，替换为AssignArea逻辑）
forall(n in 1..N) {
    X[n,1] >= XMIN[n,1] * D[n];
    X[n,2] >= XMIN[n,2] * D[n];
    X[n,1] <= XMAX[n,1] * D[n];
    X[n,2] <= XMAX[n,2] * D[n];
}

}

三、迭代操作核心技巧 #

• 遍历区域参数：用forall(a in 1..NA)可迭代6个区域的所有参数，结合分配变量实现设施与区域的灵活绑定
• 遍历设施-配送对：forall(n in 1..N, d in 1..NDO)是处理连接关系的标准方式，确保所有配对被约束覆盖
• 条件约束开关：通过D[n]作为开关，未建设的设施自动跳过坐标约束，避免无效限制

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