寻找最佳 cuts/sections 以减少残差的算法

Question

输入数据

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

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

需要客户（长度=数量）

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 模型也可以在例如果肉。

寻找最佳 cuts/sections 以减少残差的算法

Algorithm of finding optimal cuts/sections to reduce remains

algorithm

optimization

mathematical-optimization