CPLEX 中的多容量背包

Question

我遇到了交叉背包问题，其中一组项目中的多个项目的最大数量需要通过最小化成本放入一个箱子中。我能够解决 CPLEX 中的优化问题。

但是，当问题由两个箱（具有不同容量）组成时，我发现在 CPLEX 中实施时遇到困难。

问题：

Bin = [B1, B2] 
Capacity = [7,5]

Item = [I1, I2, I3, I4]
Weight = [6,3,1,4]
Price = [2,8,2,4]

objective就是放置最大数量的物品，同时最小化总价。

如何在 CPLEX 中解决这个 objective 问题？

下面是我的代码片段：

// ITEMS
int n=4; // no of items
range items = 1..n; // range of items
int p[items] = [2,8,2,6]; //price
int w[items] = [6,3,1,4]; //weight

// BINS
int m=2; // no of bins
range bins=1..m; // range of bin
int capacity[bins] = [7,5]; // capacity of each bin

dvar boolean x[items][bins]; 

// model ; max the profit
maximize sum(i in items, j in bins) p[i]*x[i][j];

subject to {
    forall (j in bins)
        cons1 : sum(i in items) w[i]*x[i][j] <= capacity[j];
    forall (i in items)
        cons2 : sum(j in bins) x[i][j] == 1;    
}

-谢谢

Answer 1

您可以在 CPLEX_Studio1271\opl\examples\opl\knapsack 中找到背包示例。

Answer 2

如果你添加

assert sum(i in items) w[i]<=sum(b in bins) capacity[b];

然后这个断言被违反了，这就解释了为什么你没有得到解决方案。您没有足够的垃圾箱容量。

但是如果你转向：

int capacity[bins] = [7,5]; // capacity of each bin

进入

int capacity[bins] = [7,7]; // capacity of each bin

那么你就会得到一个解决方案。

CPLEX 中的多容量背包

multi-capacities Knapsack in CPLEX

optimization

knapsack-problem

cplex