Мякоть занимает слишком много времени, чтобы решить - PullRequest
Новая
       48

Мякоть занимает слишком много времени, чтобы решить

1 голос
/ 17 июня 2019

Я пытаюсь упаковать предметы в грузовики с помощью Pulp Solver, он работает хорошо, когда количество предметов мало (то есть <25), но когда я увеличиваю количество до даже 30-32, это занимает целую вечность. </p>

Это код решения целлюлозы: 

def allocator(item_mass, item_vol, truck_mass, truck_vol, truck_cost, id_series):
    n_items = len(item_vol)
    set_items = range(n_items)
    n_trucks = len(truck_cost)
    set_trucks = range(n_trucks)


    y = pulp.LpVariable.dicts('truckUsed', set_trucks,
        lowBound=0, upBound=1, cat=LpInteger)

    x = pulp.LpVariable.dicts('itemInTruck', (set_items, set_trucks), 
        lowBound=0, upBound=1, cat=LpInteger)

    # Model formulation
    prob = LpProblem("Truck allocation problem", LpMinimize)

    # Objective
    prob += lpSum([truck_cost[i] * y[i] for i in set_trucks])
    # Constraints
    for j in set_items:
        # Every item must be taken in one truck
        prob += lpSum([x[j][i] for i in set_trucks]) == 1

    for i in set_trucks:
        # Respect the mass constraint of trucks
        prob += lpSum([item_mass[j] * x[j][i] for j in set_items]) <= truck_mass[i]*y[i]

        # Respect the volume constraint of trucks
        prob += lpSum([item_vol[j] * x[j][i] for j in set_items]) <= truck_vol[i]*y[i]
    # Ensure y variables have to be set to make use of x variables:
    for j in set_items:
        for i in set_trucks:
            x[j][i] <= y[i]

    s = id_series  # id_series

    prob.solve()

Есть ли что-то, что я делаю не так?

Вот ссылка на блокнот jupyter и тестовые файлы.

Ответы [ 2 ]

0 голосов
/ 18 июня 2019

Я подозреваю, что ваша проблема слишком симметрична.т.е. есть несколько грузовиков, которые абсолютно одинаковы.

Когда это происходит, CBC может потратить время на поиск «лучшего» решения.

У вас есть 2 варианта:

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

  • Задайте функцию вторичной стоимости, чтобы сделать вещи менее симметричными, то есть предпочитайте, чтобы элементы с наименьшим номером были назначеныдо самых пронумерованных грузовиков.Эта симметрия происходит автоматически в коммерческих решениях, таких как gurobi.

0 голосов
/ 17 июня 2019

По умолчанию вы используете CBC, MIP-решатель с открытым исходным кодом.
2 возможных подхода:

  1. используйте лучший решатель, такой как CPLEX или GUROBI (реклама, но бесплатная для студентови ученые).У PuLP есть API для них обоих.
  2. Вам нужно оптимальное решение?Если это не так, установите ограничение по времени.

Пример: 

prob.solve(pulp.COIN(maxSeconds=your_time_limit))
...