algorithm - 迭代找出可变数量元素的组合

Question

我正在制作一个程序，它使用动态规划来决定如何在 DVD 之间分配一些文件(电影)，以便它使用最少数量的 DVD。

经过深思熟虑，我决定这样做的一个好方法是查看小于 4.38 GB(DVD 的实际大小)的所有可能的电影组合，然后选择最大的一部(即浪费最少的空间)并以最有效的组合删除电影并重复直到电影用完。

问题是我不知道如何循环，所以我可以找出所有可能的组合，因为电影的大小各不相同，因此无法使用特定数量的嵌套循环。

伪代码:

Some kind of loop:
    best_combination=[]
    best_combination_size=0
    if current_combination<4.38 and current_combination>best_combination_size:
        best_combination=current_combination
        best_combination_size=best_combination_size
print(best_combination)
delete best_combination from list_of_movies

第一次发布问题..所以请放轻松!提前致谢

附言我想出了一种使用 Dijkstra 的方法来做到这一点，我认为它会很快但内存不友好。如果有人感兴趣，我很乐意讨论。

Answer 1

你真的应该坚持使用 common bin-packing heuristics 。维基百科文章很好地概述了方法，包括指向针对问题定制的精确方法的链接。但请始终牢记:这是一个 np 完全问题!

我将向您展示一些支持我的提示的示例，即您应该坚持启发式方法。

以下 python 代码:

• 创建参数化随机问题(多种方法/标准的正态分布；验收抽样以确保没有电影大于 DVD)
• 使用一些随机的 binpacking-library，它实现了一些贪婪启发式(我之前没有尝试或测试过这个库；所以没有保证!；不知道使用了哪种启发式)
• 使用简单的混合整数编程实现(由商业求解器求解；开源求解器如 cbc struggle，但可能用于良好的近似解)

代码

import numpy as np
from cvxpy import *
from time import time

""" Generate some test-data """
np.random.seed(1)
N = 150  # movies
means = [700, 1400, 4300]
stds = [100, 300, 500]
DVD_SIZE = 4400

movies = []
for movie in range(N):
    while True:
        random_mean_index = np.random.randint(low=0, high=len(means))
        random_size = np.random.randn() * stds[random_mean_index] + means[random_mean_index]
        if random_size <= DVD_SIZE:
            movies.append(random_size)
            break

""" HEURISTIC SOLUTION """
import binpacking
start = time()
bins = binpacking.to_constant_volume(movies, DVD_SIZE)
end = time()
print('Heuristic solution: ')
for b in bins:
    print(b)
print('used bins: ', len(bins))
print('used time (seconds): ', end-start)

""" Preprocessing """
movie_sizes_sorted = sorted(movies)
max_movies_per_dvd = 0
occupied = 0
for i in range(N):
    if occupied + movie_sizes_sorted[i] <= DVD_SIZE:
        max_movies_per_dvd += 1
        occupied += movie_sizes_sorted[i]
    else:
        break

""" Solve problem """
# Variables
X = Bool(N, N)  # N * number-DVDS
I = Bool(N)     # indicator: DVD used

# Constraints
constraints = []
# (1) DVDs not overfilled
for dvd in range(N):
    constraints.append(sum_entries(mul_elemwise(movies, X[:, dvd])) <= DVD_SIZE)
# (2) All movies distributed exactly once
for movie in range(N):
    constraints.append(sum_entries(X[movie, :]) == 1)
# (3) Indicators
for dvd in range(N):
    constraints.append(sum_entries(X[:, dvd]) <= I[dvd] * (max_movies_per_dvd + 1))

# Objective
objective = Minimize(sum_entries(I))

# Problem
problem = Problem(objective, constraints)
start = time()
problem.solve(solver=GUROBI, MIPFocus=1, verbose=True)
#problem.solve(solver=CBC, CliqueCuts=True)#, GomoryCuts=True, KnapsackCuts=True, verbose=True)#, GomoryCuts=True, MIRCuts=True, ProbingCuts=True,
              #CliqueCuts=True, FlowCoverCuts=True, LiftProjectCuts=True,
              #verbose=True)
end = time()

""" Print solution """
for dvd in range(N):
    movies_ = []
    for movie in range(N):
        if np.isclose(X.value[movie, dvd], 1):
            movies_.append(movies[movie])
    if movies_:
        print('DVD')
        for movie in movies_:
            print('     movie with size: ', movie)

print('Distributed ', N, ' movies to ', int(objective.value), ' dvds')
print('Optimizatio took (seconds): ', end-start)

部分输出

Heuristic solution:
-------------------
('used bins: ', 60)
('used time (seconds): ', 0.0045168399810791016)

MIP-approach:
-------------
Root relaxation: objective 2.142857e+01, 1921 iterations, 0.10 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   21.42857    0  120  106.00000   21.42857  79.8%     -    0s
H    0     0                      68.0000000   21.42857  68.5%     -    0s
H    0     0                      63.0000000   21.42857  66.0%     -    0s
     0     0   21.42857    0  250   63.00000   21.42857  66.0%     -    1s
H    0     0                      62.0000000   21.42857  65.4%     -    2s
     0     0   21.42857    0  256   62.00000   21.42857  65.4%     -    2s
     0     0   21.42857    0  304   62.00000   21.42857  65.4%     -    2s
     0     0   21.42857    0  109   62.00000   21.42857  65.4%     -    3s
     0     2   21.42857    0  108   62.00000   21.42857  65.4%     -    4s
    40     2   27.61568   20   93   62.00000   27.61568  55.5%   110    5s
H  156    10                      61.0000000   58.00000  4.92%  55.3    8s
   262     4   59.00000   84   61   61.00000   59.00000  3.28%  44.2   10s
   413    81 infeasible  110        61.00000   59.00000  3.28%  37.2   15s
H  417    78                      60.0000000   59.00000  1.67%  36.9   15s
  1834  1212   59.00000  232   40   60.00000   59.00000  1.67%  25.7   20s
...
...
 57011 44660 infeasible  520        60.00000   59.00000  1.67%  27.1  456s
 57337 44972   59.00000  527   34   60.00000   59.00000  1.67%  27.1  460s
 58445 45817   59.00000   80   94   60.00000   59.00000  1.67%  26.9  466s
 59387 46592   59.00000  340   65   60.00000   59.00000  1.67%  26.8  472s

分析

关于上面例子的一些观察:

• 启发式立即获得一些值(value) 60 的解决方案
• 商业求解器需要更多时间，但还需要找到一个值为 60(15 秒)的解决方案
  • 还尝试找到更好的解决方案或证明没有更好的解决方案(MIP 求解器是完整的 = 找到最佳解决方案或证明没有给定无限时间!)
  • 一段时间没有进展!
  • 但是:我们得到了证明，最多有一个大小为 59 的解决方案
  • = 也许 通过最优地解决问题你会节省一张 DVD；但很难找到解决方案，而且我们不知道这个解决方案是否存在(目前)!

备注

• 上述观察在很大程度上取决于数据统计
• 很容易尝试其他问题(可能更小)，其中商业 MIP 求解器找到了使用更少 1 张 DVD 的解决方案(例如 49 对 50)
  • 这不值得(记住:开源求解器的难度更大)
  • 公式非常简单，根本没有调整(不要只责怪求解器)
• 有合适的精确算法(实现起来可能要复杂得多)

结论

启发式算法非常容易实现，并且通常可以提供非常好的解决方案。其中大多数还具有非常好的理论保证(例如，与使用最佳解决方案相比，最多 11/9 opt + 1 #DVDs = first fit decreasing heuristic)。尽管我总体上热衷于优化，但我可能会在这里使用启发式方法。

一般问题也很流行，所以在许多编程语言中应该有一些很好的库来解决这个问题!