Code freez if more inputs

[kiko058]

Hello I found this code. The code should calculate how to divide given lengths into pieces with the smallest possible waste, based on the specified lengths and quantities. For example, if I have a list of required pieces and I know that only 6,000mm pieces are available in stock, I need to divide them into 6,000mm-long pieces with the smallest possible waste.

The problem is that the code works excellently for a smaller number of pieces, but sometimes just one extra piece causes the program to freeze and not complete the calculation.

Can you please advise me on how to make the program able to calculate even with a larger number of inputs?

If:

 [(3650, 10), (1110, 25), (1248, 10), (1480, 10)]

work excellent

But if:

[(3650, 10), (1110, 25), (1248, 10), (1480, 20)]

Program cant count it :(

from ortools.linear_solver import pywraplp

# Final message
result = ''
rod_length = 6000

# Stored numbers for counting
numbers = [(3650, 10), (1110, 25), (1248, 10), (1480, 10)]

def create_length_list(numbers):
    result_list = []
    for num, count in numbers:
        for i in range(count):
            result_list.append(num)
    return result_list


def create_data_model():
    """Create the data for the example."""
    global rod_length
    data = {}
    weights = create_length_list(numbers)
    data['weights'] = weights
    data['items'] = list(range(len(weights)))
    data['bins'] = data['items']
    data['bin_capacity'] = rod_length
    return data


def main():
    data = create_data_model()
    global result

    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver('SCIP')

    if not solver:
        return

    # Variables
    # x[i, j] = 1 if item i is packed in bin j.
    x = {}
    for i in data['items']:
        for j in data['bins']:
            x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

    # y[j] = 1 if bin j is used.
    y = {}
    for j in data['bins']:
        y[j] = solver.IntVar(0, 1, 'y[%i]' % j)

    # Constraints
    # Each item must be in exactly one bin.
    for i in data['items']:
        solver.Add(sum(x[i, j] for j in data['bins']) == 1)

    # The amount packed in each bin cannot exceed its capacity.
    for j in data['bins']:
        solver.Add(
            sum(x[(i, j)] * data['weights'][i] for i in data['items']) <= y[j] *
            data['bin_capacity'])

    # Objective: minimize the number of bins used.
    solver.Minimize(solver.Sum([y[j] for j in data['bins']]))

    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        num_bins = 0
        for j in data['bins']:
            if y[j].solution_value() == 1:
                bin_items = []
                bin_weight = 0
                for i in data['items']:
                    if x[i, j].solution_value() > 0:
                        bin_items.append(data['weights'][i])
                        bin_weight += data['weights'][i]
                if bin_items:
                    num_bins += 1
                    result += ('\n Rod number: ' + str(num_bins) + 'Length: ' + str(
                        bin_items) + 'Used length:' + str(bin_weight))
        result += ('\n \n Number of used ' + str(rod_length) + 'mm rods: ' + str(num_bins))
    else:
        result += 'Optimal solution does not exist'


main()
print(result)

[deanhystad]

The solver also freezes if there are fewer inputs. I found many combinations of numbers, some less than half as large, that caused the solver to "freeze".

[kiko058]

The solver also freezes if there are fewer inputs. I found many combinations of numbers, some less than half as large, that caused the solver to "freeze".

Hello, and could you help me ? How to solve it?

I am new in programming and tryed lot of forums to find solver of this problem but idk... :/

Thanks