Algorithm of finding optimal cuts/sections to reduce remains

Question

Input data

Pipes or somethins like on stock (length = quantity on stock):

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

Needed cust (length = quantity)

cut2m = 4pc  
cut2.5m = 1pc  

Result: optimal pipes for minimum remains, considering quantity that left on stock

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)

So we need:

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

How can I implement some optimal algorithm for this?
There will be 5-10 pipe lengths and 10-20 cuts, so I think that it can't be solved with brute force, but I'm not algorithm guru.

Thanks :)

Answer 1

Smaller instances can be solved with mixed-integer linear programming. Here is an implementation in MiniZinc using the data from the question. The available pipes have been rearranged into a flat array pipeLength. In the model x denotes the cuts from each pipe and z denotes whether a pipe is used or not.

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)];

Running gives:

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

The same MILP-model could also be implemented in e.g. PuLP.