减少残余物的最优切割/切片算法

Question

输入数据

管道或类似库存的东西(长度=库存数量)：

pipe3m = 4 pc  
pipe4m = 1 pc  
pipe5m = 1 pc   

需要cust (长度=数量)

cut2m = 4pc  
cut2.5m = 1pc  

结果:在考虑库存的数量的情况下，最小剩余量的最优管道

pipe4m 1pc => cut2m + cut2m => remains 0m (4-2-2)  
pipe5m 1pc => cut2m + cut2.5m => remains 0.5m (5 - 2 - 2.5)  
pipe3m 1pc => cut2m => remains 1m (3-2)

所以我们需要：

pipe4m => 1pc *(if we have 2 pc of pipe4m on stock we can cut it into 2m+2m, but there is only 1)*  
pipe5m => 1pc  
pipe3m => 1pc

如何才能实现一些优化算法呢？

会有5-10个管道长度和10-20个切割，所以我认为它不能用蛮力解决，但我不是算法专家。

谢谢:)

Answer 1

较小的实例可以用混合整数线性规划求解.下面是在MiniZinc中使用来自问题的数据的一个实现。可用的管道已重新排列成一个平面阵列pipeLength。在模型中，x表示每个管道的切割，z表示是否使用管道。

int: nPipes = 6;
int: nCuts = 2;

set of int: PIPE = 1..nPipes;
set of int: CUT = 1..nCuts;

array[PIPE] of float: pipeLength = [3, 3, 3, 3, 4, 5];
array[CUT] of int: cutQuantity = [4, 1];
array[CUT] of float: cutLength = [2, 2.5];
    
array[PIPE, CUT] of var 0..10: x;
array[PIPE] of var 0..1: z;

% required cuts constraint
constraint forall(k in CUT)
    (sum(i in PIPE)(x[i,k]) = cutQuantity[k]);

% available pipes constraint
constraint forall(i in PIPE)
    (sum(k in CUT)(cutLength[k]*x[i,k]) <= pipeLength[i]);

% pipe used constraint
constraint forall(i in PIPE)
    (max(cutQuantity)*z[i] >= sum(k in CUT)(x[i,k]));

var float: loss = sum(i in PIPE)(pipeLength[i]*z[i] - sum(k in CUT)(cutLength[k]*x[i,k]));

solve minimize loss;

output ["loss=\(show_float(2, 2, loss))\n"] ++
["pipeCuts="] ++ [show2d(x)] ++
["usePipe="] ++ [show(z)];

跑步意味着：

loss="1.50"
pipeCuts=[| 0, 0 |
   0, 0 |
   0, 0 |
   0, 1 |
   2, 0 |
   2, 0 |]
usePipe=[0, 0, 0, 1, 1, 1]

同样的MILP模型也可以在例如PuLP中实现。