CPLEX求解三阶段二维装箱问题出现不可行解错误求助

模型基本说明 #

• 优化目标：将n个同时具备高度、宽度属性的物品分配至数量最少的bin（即料箱小车/Trolley）中
• 装箱逻辑：采用三阶段层级结构，先将物品分配至栈（stack），再将栈分配至条带（stripe），最后将条带分配至bin
• 索引规则：所有物品按高度降序排列，高度最高的物品索引最小；栈、条带均以其包含的最高物品的索引（即栈/条带内最小物品索引）作为自身标识
• 改动点：原模型要求同一栈内所有物品宽度完全一致，本次修改目标为允许同栈放置不同宽度物品。新增float类型决策变量e表示栈在所属条带内占用的宽度，计划通过约束先限定每个栈内物品的最大宽度为e的取值，再约束单条带所有栈的e值之和不超过bin的宽度上限。

报错现象 #

首次运行（bin宽度为默认值）时求解器返回不可行，日志如下：

Legacy callback                                  pi
Warning:  Non-integral bounds for integer variables rounded.
Infeasibility row 'c160':  0 <= -5.

其中冲突行c160为新增的宽度约束，具体表达式：
c160: - _e(1)(2)#26 + 5 a(2)(2)#52 <= 0

上调bin的宽度容量后，报错变为：

Legacy callback                                  pi
Warning:  Non-integral bounds for integer variables rounded.
Row 'c255' infeasible, all entries at implied bounds.

对应冲突行c255表达式：

c255: _e(1)(1)#25 + _e(1)(2)#26 + _e(1)(3)#27 + _e(1)(4)#28 + _e(1)(5)#29
   - 20 b(1)(1)#65 <= 0

手动代入已知可行解的变量取值后，模型依然在新增约束处报不可行，手动赋值代码如下：

/*a[1][1]==1;
a[1][3]==1;

a[2][2]==1;
a[2][4]==1;

a[5][5]==1;

b[1][1]==1;
b[1][2]==1;

c[1][1]==1;

b[5][5]==1;
c[5][5]==1;*/

完整模型代码（OPL） #

int n=...; // 物品总数
range iitem=1..n;

float heighttrolley=...;    // bin的高度上限
float widthtrolley=...;     // bin的宽度上限

float heightitem[iitem]=...;    // 物品i的高度
float widthitem[iitem]=...;     // 物品i的宽度

dvar boolean a[1..n][1..n]; // 0-1变量，物品i是否分配到栈j
dvar boolean b[1..n][1..n]; // 0-1变量，栈j是否分配到条带k
dvar boolean c[1..n][1..n]; // 0-1变量，条带k是否分配到bin l
dvar boolean d[1..n-1][2..n][1..n-1]; // 0-1变量，物品i是否在bin l中贡献总高度且属于栈j
dvar float e[1..n][1..n];   // 条带k中栈j的占用宽度


minimize sum (l in 1..n) c[l][l]; // 最小化使用的bin总数

subject to{
// 索引规则约束：物品只能分配到索引不大于自身的栈，条带只能分配到索引不大于自身的bin
forall(j in 1..n, i in 1..n: i<j)
a[j][i]==0;   
forall(l in 1..n, k in 1..n: k<l)
c[l][k]==0;
forall(l in 1..n-1, i in l+1..n, j in l..n-1: i<l+1 && j<l && j>i-1)  
d[l][i][j]==0;

// e变量上界约束
forall(j, k in iitem)
e[j][k]<=widthtrolley;
        
// 每个物品必须且只能分配到一个栈
forall(i in iitem)
sum (j in 1..i) a[j][i]==1;

// 未激活的栈（栈顶物品未放入该栈）不能分配物品
forall(j in 1..n-1)
sum (i in j+1..n)a[j][i]<=(n-j)*a[j][j];

// 同栈物品堆叠总高度不能超过bin高度上限
forall(j in 1..n-1, i in iitem: i>j && heightitem[i]+heightitem[j]>heighttrolley)
a[j][i]==0;

// 每个激活的栈必须且只能分配到一个条带
forall(j in 1..n)
sum (k in 1..n) b[k][j]==a[j][j];

// 栈高度不能超过所属条带的高度约束1
forall(k in 2..n, j in 1..k-1)
sum(i in j..n) heightitem[i]*a[j][i]<= sum(i in k..n)heightitem[i]*a[k][i]+(heighttrolley+1)*(1-b[k][j]);

// 栈高度不能超过所属条带的高度约束2
forall(k in 1..n-1, j in k+1..n)
sum(i in j..n) heightitem[i]*a[j][i]<= sum(i in k..n)heightitem[i]*a[k][i]+heighttrolley*(1-b[k][j]);

// 每个激活的条带必须且只能分配到一个bin
forall(k in 1..n)
sum(l in 1..k)c[l][k]==b[k][k];

// bin内所有条带堆叠总高度不能超过bin高度上限
forall(l in 1..n-1)
sum(i in l..n)heightitem[i]*c[l][i]+sum(i in l+1..n)heightitem[i]*sum(j in l..i-1)d[l][i][j]<=heighttrolley*c[l][l];

// d变量取值约束
forall(l in 1..n-1, i in l+1..n, j in l..i-1){
a[j][i]+c[l][j]-1<=d[l][i][j];
d[l][i][j]<=(a[j][i]+c[l][j])/2;}

// 未激活的bin不能分配条带
forall(l in 1..n-1)
sum(k in l+1..n)c[l][k]<=(n-l)*c[l][l];

// 新增约束：栈j内任意物品的宽度不超过该栈在所属条带k中的e值
forall(i,j,k in iitem)
widthitem[i]*a[j][i]<=e[k][j];          

// 新增约束：单条带内所有栈的e值之和不超过bin宽度上限
forall(k in iitem)
sum(j in iitem)e[k][j]<=widthtrolley*b[k][k];
}

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