Алгоритм минимизации количества печатных форм при печати листов наклеек

Ее можно выразить как задачу целочисленного программирования, которую необходимо решить с помощью таких инструментов, как OR-Tools, хотя ограничения LP такие:

• фиксированное количество переменных (F)
• без умножения переменных (М)

означают две вещи: 1. Вы должны предполагать максимальное количество пластин из-за (F) и 2. Вы не можете явно смоделировать «количество листов, напечатанных с пластины», чтобы умножить ее на «количество прорезей на пластине с типом наклейки t», потому что из (М).

Хитрость в моделировании этого заключается в том, чтобы иметь отдельную переменную для каждой тройки {plate, slot, kind of sticker} со значением v, означающим «Мне нужны v наклейки определенного типа, напечатанные из этого слота. Например, оптимизированный подход из вашего вопроса будет следующим:

Slot:   0  1  2  3  4  5  6  7  8  9
A      50 50 50 50  0  0  0  0  0  0
B       0  0  0  0 50 50 50 50 50 50

и пластине придется напечатать 50 листов, потому что это максимум для отдельных слотов.

Очевидно, что это требует некоторых ограничений, чтобы избежать попыток печати нескольких разных типов наклеек из одного слота. К счастью, это можно выразить в целочисленном программировании.

Также в реальности вы печатаете одинаковое количество наклеек из каждого слота. К счастью, это просто означает, что для конкретной пластины вам нужно распечатать m листов, где m — это максимум переменных из всех слотов — хотя функция стоимости должна это учитывать.

Теперь о том, как предотвратить использование одного и того же слота для разных типов наклеек. Первая часть — ввести набор теневых целочисленных переменных, по одной для каждого v, каждая из которых имеет значение в диапазоне [0..1].

Теперь, если мы добавим набор ограничений, таких как v[p,s,k] < b[p,s,k] * 1000000, мы выразим, что конкретный v может быть ненулевым тогда и только тогда, когда соответствующий b равен 1. Теперь мы можем просто добавить ограничение для каждого слота, чтобы сумма b не превышала 1, что, в свою очередь, позволяет сделать только один v отличным от нуля для каждого слота на каждой пластине.

Очевидно, что также должны быть ограничения, выражающие, что сумма v по всем пластинам и слотам для каждого типа наклеек дает необходимое количество наклеек, но это просто.

Для целевой функции нам нужно количество использованных тарелок, которое снова можно решить с помощью переменной «логического» типа, по одной для каждой тарелки.

Я закодировал PoC для этого с помощью OR-инструментов, и это, кажется, работает, хотя для создания трех пластин и [20000, 500, 500] для наклеек требуется 8 секунд, чтобы создать первую пластину с напечатанным A * 10 1600 раз, вторую с напечатанными A * 8, B, C. 500 раз. В более крупных случаях кажется, что он быстро сходится к оптимальному или близкому к оптимальному решению, но «доказательство» его оптимальности занимает целую вечность.

Чтобы помочь другим, кто ищет код для решения подобной проблемы, мне удалось реализовать решение этой проблемы благодаря принятому ответу. Вот код.

from ortools.linear_solver import pywraplp


def solve_sticker_problem(
    num_slots,
    required_stickers,
    max_sheets_per_plate,
    max_wastage_ratio,
):
    # Initialize the solver
    solver = pywraplp.Solver.CreateSolver("SAT")

    if not solver:
        return None

    num_sticker_types = len(required_stickers)
    max_plates = (
        num_sticker_types  # We will presume max plates to be equal to kinds of stickers
    )

    # Decision variables
    # v[p, s, t] - number of stickers of type t in slot s on plate p
    v = {}
    # b[p, s, t] - binary variable if slot s on plate p is used for sticker type t
    b = {}
    # u[p] - binary variable if plate p is used
    u = [solver.IntVar(0, 1, f"u[{p}]") for p in range(max_plates)]

    for p in range(max_plates):
        for s in range(num_slots):
            for t in range(num_sticker_types):
                v[p, s, t] = solver.IntVar(0, solver.infinity(), f"v[{p},{s},{t}]")
                b[p, s, t] = solver.IntVar(0, 1, f"b[{p},{s},{t}]")

    # Constraints
    # 1. Each slot on each plate can be used for at most one type of sticker
    for p in range(max_plates):
        for s in range(num_slots):
            solver.Add(sum(b[p, s, t] for t in range(num_sticker_types)) == 1)
            for t in range(num_sticker_types):
                solver.Add(v[p, s, t] <= b[p, s, t] * max_sheets_per_plate)

    # 2. Sum of stickers of each type over all plates and slots should meet the required count
    for t in range(num_sticker_types):
        sumOfStickers = sum(
            v[p, s, t] for p in range(max_plates) for s in range(num_slots)
        )
        solver.Add(sumOfStickers >= required_stickers[t])
        solver.Add(
            sumOfStickers
            <= required_stickers[t] + (required_stickers[t] * max_wastage_ratio)
        )

    # 3. If a plate is used, it should be counted
    for p in range(max_plates):
        for t in range(num_sticker_types):
            for s in range(num_slots):
                solver.Add(v[p, s, t] <= u[p] * max_sheets_per_plate)

    # 4. Use same number of stickers for every slot in a plate
    for p in range(max_plates):
        for s in range(num_slots - 1):
            solver.Add(
                sum(v[p, s, t] for t in range(num_sticker_types))
                == sum(v[p, s + 1, t] for t in range(num_sticker_types))
            )

    # Objective: Minimize the number of plates used
    solver.Minimize(solver.Sum(u[p] for p in range(max_plates)))

    # Solve the problem
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print("Solution:")
        for p in range(max_plates):
            if u[p].solution_value() == 1:
                prints = 0
                slots: dict[str, int] = {}
                for s in range(num_slots):
                    for t in range(num_sticker_types):
                        if b[p, s, t].solution_value() == 1:
                            slots[f"Type{t}"] = slots.get(f"Type{t}", 0) + 1
                            prints = v[p, s, t].solution_value()
                print(f"Plate {p} ({prints} sheets): {slots}")


# Example usage
num_slots = 10  # Number of slots per plate
required_stickers = [20000, 500, 500]  # Number of required stickers for each type
max_sheets_per_plate = 1000000  # Maximum sheets you can print from a plate
max_waste_percent = 0  # Percentage of max allowed wastage with respect to required stickers. Set to 0 to avoid wastage


solve_sticker_problem(
    num_slots,
    required_stickers,
    max_sheets_per_plate,
    max_waste_percent / 100,
)

Выход:

Solution:
Plate 1 (500.0 sheets): {'Type2': 1, 'Type0': 8, 'Type1': 1}
Plate 2 (1600.0 sheets): {'Type0': 10}

Примечание. Время увеличивается экспоненциально по мере увеличения количества типов наклеек. Вы можете увеличить потери, чтобы сократить затраченное время. Любые оптимизации, которые можно сделать здесь, приветствуются, поскольку я новичок в целочисленном программировании и инструментах OR.