如何将工厂仓库选址的CPLEX模型改写为CP模型？求解存疑

云原生阿岚

2026-6-23

工厂与仓库联合选址：CPLEX MIP转CP模型的优化问题

原MIP模型（CPLEX标准.mod文件）

int l = ...;
int n = ...;
int t = ...;
int m = ...;

range j = 1..m;
range i = 1..n;
range h = 1..l;
range e = 1..t;

int D[j] = ...;
int K[i] = ...;
int S[h] = ...;
int W[e] = ...;
float F[i] = ...;
float f[e] = ...;
float c1[h][i] = ...;
float c2[i][e] = ...;
float c3[e][j] = ...;

dvar boolean y1[i];
dvar boolean y2[e];
dvar int+ x1[e][j];
dvar int+ x2[i][e];
dvar int+ x3[h][i];

minimize
  sum(I in i) (F[I] * y1[I]) + 
  sum(E in e) (f[E] * y2[E]) + 
  sum(H in h, I in i) (c1[H][I] * x3[H][I]) +
  sum(I in i, E in e) (c2[I][E] * x2[I][E]) +
  sum(E in e, J in j) (c3[E][J] * x1[E][J]);
 
 subject to {
    forall(H in h)
      sum(I in i) x3[H][I] <= S[H];
    forall(I in i)
      sum(H in h) (x3[H][I]) - sum(E in e) (x2[I][E]) >= 0;
    forall(I in i)
      sum(E in e) x2[I][E] <= K[I] * y1[I];
    forall(E in e)
      sum(I in i) (x2[I][E]) - sum(J in j) (x1[E][J]) >= 0;
    forall(E in e)
      sum(J in j) x1[E][J] <= W[E] * y2[E];
    forall(J in j)
      sum(E in e) x1[E][J] == D[J];
}

原MIP模型的.dat文件

l = 3; //number of suppliers
n = 4; //number of potential factory locations
t = 5; //number of potential warehouse locations
m = 7; //number of markets or demand points
SheetConnection sheet("Task.xlsx");
D from SheetRead(sheet, "PWL!b26:h26"); //annual demand from customer
K from SheetRead(sheet, "PWL!h12:h15"); //potential capacity of factory at site
S from SheetRead(sheet, "PWL!f4:f6"); //supply capacity at supplier
W from SheetRead(sheet, "PWL!j21:j25"); //potential warehouse capacity at site
F from SheetRead(sheet, "PWL!g12:g15"); //fixed cost of locating a plant at site
f from SheetRead(sheet, "PWL!i21:i25"); //fixed cost of locating a warehouse at site
c1 from SheetRead(sheet, "PWL!b4:e6"); //cost of shipping one unit from supply source to factory 
c2 from SheetRead(sheet, "PWL!b12:f15"); //cost of producing and shipping one unit from factory to warehouse 
c3 from SheetRead(sheet, "PWL!b21:h25"); // cost of shipping one unit from warehouse to customer

x3 to SheetWrite(sheet, "PWL!m4:p6"); //quantity shipped from warehouse to market
x2 to SheetWrite(sheet, "PWL!m12:q15"); //quantity shipped from factory to warehouse
x1 to SheetWrite(sheet, "PWL!m21:s25"); //quantity shipped from supplier to factory at site
y1 to SheetWrite(sheet, "PWL!r12:r15"); //1 if factory is located at site i, 0 otherwise
y2 to SheetWrite(sheet, "PWL!t21:t25"); //1 if warehouse is located at site e, 0 otherwise

已实现的CP模型代码

.dat文件

nSuppliers = 3;
nFactories = 4;
nWarehouses = 5;
nMarkets = 7;

D = [150, 150, 100, 100, 100, 150, 100];
K = [350, 280, 400, 300];
S = [350, 290, 310];
W = [350, 350, 350, 350, 350];
F = [450000, 500000, 450000, 450000];
f = [30000, 40000, 35000, 20000, 35000];

c1 = [
    [1.9, 1.9, 1.8, 1.9],
    [2.0, 2.0, 1.9, 1.8],
    [1.8, 2.0, 1.9, 2.0]
];

c2 = [
    [6.1, 7.8, 7.9, 7.9, 7.8],
    [7.7, 7.1, 6.9, 7.8, 7.7],
    [6.7, 6.0, 7.1, 6.9, 6.7],
    [7.0, 6.0, 6.5, 7.6, 6.6]
];

c3 = [
    [4.5, 5.0, 4.6, 5.5, 4.8, 4.1, 4.9],
    [4.8, 4.6, 4.9, 5.7, 5.7, 5.9, 4.0],
    [5.2, 5.1, 5.1, 4.2, 4.7, 4.0, 5.0],
    [5.2, 5.9, 4.3, 5.9, 5.7, 4.1, 4.7],
    [4.9, 5.3, 4.1, 4.5, 4.7, 5.6, 4.0]
];

.mod文件片段

using CP;

execute
{
  cp.param.timelimit=10;
}

求解结果与问题

运行后得到以下结果，核心问题是分支数超过200万，搜索10秒才终止，且仅找到26个解：

! Time = 9,86s, Explored branches = 2 081 170, Memory usage = 28,5 MB
 !          Best Branches  Non-fixed    W       Branch decision
       1 445 819     179k         11    2         1 != x2(4)(1)
       1 445 819     164k         31    3         0 != x3(3)(2)
       1 445 819     182k         25    5        25 != x3(2)(4)
       1 445 819     183k         21    6         1 != x1(5)(1)
       1 445 819     167k         30    7       198 != x2(3)(5)
       1 445 819     174k         76    8   F        -
       1 445 819     159k         32    9         0  = x3(2)(2)
       1 445 819     172k         21   10        54 != x1(1)(5)
       1 445 819     175k         25   11       104 != x2(4)(5)
       1 445 819     168k         76   12   F    23  = x1(1)(5)
       1 445 819     183k         32    1        34 != x1(1)(6)
       1 445 819     180k         15    4         1 != x1(4)(7)
       1 445 819     183k          9    5       214 != x2(4)(5)
       1 445 819     184k         76    6   F        -
       1 445 819     175k         76    8   F     1  = x1(4)(4)
       1 445 819     160k         34    9        54 != x2(1)(4)
       1 445 819     173k         28   10        60 != x1(1)(4)
       1 445 819     176k         10   11         4 != x2(1)(3)
       1 445 819     169k         23   12         1 != x1(4)(4)
 ! ----------------------------------------------------------------------------
 ! Search terminated by limit, 26 solutions found.
 ! Best objective         : 1 445 819
 ! Number of branches     : 2 104 124
 ! Number of fails        : 1 007 321
 ! Total memory usage     : 29,2 MB (28,6 MB CP Optimizer + 0,6 MB Concert)
 ! Time spent in solve    : 10,01s (10,01s engine + 0,00s extraction)
 ! Search speed (br. / s) : 210 160,2
 ! ----------------------------------------------------------------------------

模型改写与分支数优化建议

1. 完整CP模型的正确改写

CP Optimizer与MIP的变量声明、约束写法有差异，需补全以下内容：

using CP;

// 定义范围
range Suppliers = 1..nSuppliers;
range Factories = 1..nFactories;
range Warehouses = 1..nWarehouses;
range Markets = 1..nMarkets;

// 变量声明：明确上下界，替代MIP的dvar
dvar int y1[Factories] in 0..1; // 工厂选址变量
dvar int y2[Warehouses] in 0..1; // 仓库选址变量

// 流量变量：设置合理上下界，减少搜索空间
dvar int x1[Warehouses][Markets] in 0..max(W); // 仓库到市场的流量，上限取最大仓库容量
dvar int x2[Factories][Warehouses] in 0..max(K); // 工厂到仓库的流量，上限取最大工厂容量
dvar int x3[Suppliers][Factories] in 0..max(S); // 供应商到工厂的流量，上限取最大供应商容量

// 目标函数：保持与MIP一致
minimize
  sum(i in Factories) (F[i] * y1[i]) + 
  sum(e in Warehouses) (f[e] * y2[e]) + 
  sum(h in Suppliers, i in Factories) (c1[h][i] * x3[h][i]) +
  sum(i in Factories, e in Warehouses) (c2[i][e] * x2[i][e]) +
  sum(e in Warehouses, j in Markets) (c3[e][j] * x1[e][j]);

// 约束改写：CP支持sum表达式，逻辑约束可强化
subject to {
    // 供应商产能约束
    forall(h in Suppliers)
      sum(i in Factories) x3[h][i] <= S[h];
    // 工厂供需平衡（入库≥出库）
    forall(i in Factories)
      sum(h in Suppliers) x3[h][i] >= sum(e in Warehouses) x2[i][e];
    // 工厂产能约束：未选址则无流量
    forall(i in Factories)
      sum(e in Warehouses) x2[i][e] <= K[i] * y1[i];
    // 仓库供需平衡（入库≥出库）
    forall(e in Warehouses)
      sum(i in Factories) x2[i][e] >= sum(j in Markets) x1[e][j];
    // 仓库产能约束：未选址则无流量
    forall(e in Warehouses)
      sum(j in Markets) x1[e][j] <= W[e] * y2[e];
    // 市场需求满足
    forall(j in Markets)
      sum(e in Warehouses) x1[e][j] == D[j];
}

// 求解参数设置
execute
{
  cp.param.timelimit = 10;
  // 以下是优化搜索的关键参数
  cp.param.varselection = 3; // 基于冲突的变量选择策略，减少无效分支
  cp.param.branchingpriority = [y1, y2]; // 优先分支选址变量（0-1变量）
  cp.param.heuristicfreq = 1000; // 每1000分支执行一次启发式，快速找优解
}

2. 减少分支数的核心优化措施

收紧变量上下界：给每个流量变量设置更精准的上限，比如x3[h][i]的上限设为min(S[h], K[i])，x1[e][j]设为min(W[e], D[j])，进一步缩小搜索范围。
优先处理0-1变量：通过branchingpriority让CP先确定工厂/仓库的选址，再处理流量变量，避免在流量变量上做无效分支。
强化逻辑约束：对选址变量添加显式逻辑约束，比如forall(i in Factories) (y1[i] == 0) => (sum(e in Warehouses) x2[i][e] == 0)，CP的约束传播会提前剪枝不符合条件的分支。
调整搜索策略：使用varselection=3（冲突导向）或varselection=2（最小影响）的变量选择策略，避免随机分支；开启cp.param.propagation=2增强约束传播能力，提前排除不可行解。
目标函数权重调整：将固定成本（F、f）的权重在目标中前置，CP会优先探索固定成本更低的选址方案，更快找到优质解，减少后续分支。

内容的提问来源于stack exchange，提问作者Даниил Бадин

如何将工厂仓库选址的CPLEX模型改写为CP模型？求解存疑

原MIP模型（CPLEX标准.mod文件） #

原MIP模型的.dat文件 #

已实现的CP模型代码 #

.dat文件 #

.mod文件片段 #

求解结果与问题 #

模型改写与分支数优化建议 #

1. 完整CP模型的正确改写 #

2. 减少分支数的核心优化措施 #

原MIP模型（CPLEX标准.mod文件）

原MIP模型的.dat文件

已实现的CP模型代码

.dat文件

.mod文件片段

求解结果与问题

模型改写与分支数优化建议

1. 完整CP模型的正确改写

2. 减少分支数的核心优化措施