组合优化在Python中

huangapple
go评论106阅读模式
英文:

Combination Optimization in Python

问题

我需要从仓库中收集产品以进行捆绑，格式如下：{产品:数量}
center_a_products = {1: 8, 2: 4, 3: 12}

每个仓库有不同种类和数量的产品，格式如下：{仓库:{产品:数量}}
product_quantities = {1: {1: 10, 2: 3, 3: 15}, 2: {1: 5, 2: 8, 3: 10}, 3: {1: 12, 2: 6}}

我每次只能访问一个仓库，但可以从一个仓库收集多个产品。如果某种产品的总数量小于center_a_products，我必须访问包含该产品的每个仓库并收集该产品的总数量。有很多组合符合这些条件，但我需要知道访问最少数量仓库的最有效组合。

我尝试了这个代码，但失败了...

  1. from itertools import combinations
  3. # 定义仓库
  4. centers = [1, 2, 3]
  6. # 定义中心A所需的产品和数量
  7. center_a_products = {
  8.     1: 8,
  9.     2: 4,
  10.     3: 12
  11. }
  13. # 定义每个仓库的产品和数量
  14. product_quantities = {
  15.     1: {1: 10, 2: 3, 3: 15},
  16.     2: {1: 5, 2: 8, 3: 10},
  17.     3: {1: 12, 2: 6}
  18. }
  20. # 检查产品组合是否符合要求的函数
  21. def meets_requirements(combination):
  22.     product_counts = {product: 0 for product in center_a_products.keys()}
  23.     for center, products in combination:
  24.         for product, quantity in products.items():
  25.             product_counts[product] += quantity
  26.     for product, required_quantity in center_a_products.items():
  27.         if product_counts[product] < required_quantity:
  28.             return False
  29.     return True
  31. # 查找所有产品组合
  32. combinations_to_move = []
  33. for r in range(1, len(centers) + 1):
  34.     for combination in combinations(zip(centers, [product_quantities[c] for c in centers]), r):
  35.         if meets_requirements(combination):
  36.             combinations_to_move.append(combination)
  38. # 打印组合
  39. for idx, combination in enumerate(combinations_to_move, start=1):
  40.     print(f"Combination {idx}:")
  41.     for center, products in combination:
  42.         for product, quantity in products.items():
  43.             print(f"Move {quantity} units of product {product} from Center {center}")

我期望的输出类似于这样：

  1. Move 8 units of product 1 from Center 1
  2. Move 3 units of product 2 from Center 1
  3. Move 12 units of product 3 from Center 1
  4. Move 1 units of product 3 from Center 2
英文:

I need to gather products from warehouse centers for product bundling
like this {product:quantity}
center_a_products = {1: 8, 2: 4, 3: 12}

Every centers has different kinds and quantities of products
like this {center:{product:quantity}} product_quantities = {1: {1: 10, 2: 3, 3: 15}, 2: {1: 5, 2: 8, 3: 10}, 3: {1: 12, 2: 6}}

I can only visit one center at a time but I can collect multiple product from one center.
If total quantity of some product is less than center_a_products, I must visit every center containing that product and collect total quantity of that product.
There are many combination meets these conditions but I need to know most efficient combination that visits the smallest number of centers

I tried this but it failed...

  1. from itertools import combinations
  3. # Define the centers
  4. centers = [1, 2, 3]
  6. # Define the products and quantities needed in Center A
  7. center_a_products = {
  8.     1: 8,
  9.     2: 4,
  10.     3: 12
  11. }
  13. # Define the products and quantities for each center
  14. product_quantities = {
  15.     1: {1: 10, 2: 3, 3: 15},
  16.     2: {1: 5, 2: 8, 3: 10},
  17.     3: {1: 12, 2: 6}
  18. }
  20. # Function to check if a product combination meets the requirements
  21. def meets_requirements(combination):
  22.     product_counts = {product: 0 for product in center_a_products.keys()}
  23.     for center, products in combination:
  24.         for product, quantity in products.items():
  25.             product_counts[product] += quantity
  26.     for product, required_quantity in center_a_products.items():
  27.         if product_counts[product] &lt; required_quantity:
  28.             return False
  29.     return True
  31. # Find all combinations of products
  32. combinations_to_move = []
  33. for r in range(1, len(centers) + 1):
  34.     for combination in combinations(zip(centers, [product_quantities[c] for c in centers]), r):
  35.         if meets_requirements(combination):
  36.             combinations_to_move.append(combination)
  38. # Print the combinations
  39. for idx, combination in enumerate(combinations_to_move, start=1):
  40.     print(f&quot;Combination {idx}:&quot;)
  41.     for center, products in combination:
  42.         for product, quantity in products.items():
  43.             print(f&quot;Move {quantity} units of product {product} from Center {center}&quot;)

I expected something like this

  1. Move 8 units of product 1 from Center 1
  2. Move 3 units of product 2 from Center 1
  3. Move 12 units of product 3 from Center 1
  4. Move 1 units of product 3 from Center 2

答案1

得分: 4

问题描述适合使用[Mixed-Integer-Linear Program (MIP)]解决。

解决混合整数问题的便捷库是PuLP，它附带了内置的Coin-OR suite和特定的整数求解器CBC。

我们制定了描述问题的模型：

  1. import pulp
  3. # 省略部分代码...
  5. # 满足所有需求
  6. for product in center_a_products:
  7.     problem += pulp.lpSum(product_vars[center, product] for center in product_quantities) == center_a_products[product]
  9. # 我们只能从一个中心获取物品，如果我们访问它
  10. # 还有：不能从一个中心拿取比库存更多的物品
  11. for center in product_quantities:
  12.     for product in product_quantities[center]:
  13.         problem += product_vars[center, product] <= center_vars[center] * product_quantities[center][product]
  15. # 最小化访问的中心数量
  16. problem += pulp.lpSum(center_vars.values())
  17. problem.solve()

打印解决方案：

  1. for center in product_quantities:
  2.     if center_vars[center].varValue == 1:
  3.         for product in product_quantities[center]:
  4.             quantity = product_vars[center, product].varValue
  5.             if quantity > 0:
  6.                 print(f"Move {quantity} units of product {product} from center {center}")

输出：

  1. Move 8.0 units of product 1 from center 3
  2. Move 4.0 units of product 2 from center 3
  3. Move 12.0 units of product 3 from center 3

目前您提供的示例非常简单。可以轻松添加附加约束，但您需要提供问题和预期输出的更好描述。

将问题描述转换为线性程序可能需要一些实践。这个程序中最棘手的一行是：

  1. problem += product_vars[center, product] <= center_vars[center] * product_quantities[center][product]

目标是最小化 center_vars，但满意度约束会强制其中一些为1。

要获得描述问题的思路，而不是考虑解决方案，我建议观看Raymond Hettinger在PyCon 2019上的精彩演讲 - Modern solvers: Problems well-defined are problems solved。

安装 PuLP：

  1. pip install pulp
英文:

The problem description lends itself to solving with a Mixed-Integer-Linear Program (MIP).

A convenient library for solving mixed integer problems is PuLP that ships with the built-in Coin-OR suite and in particular the integer solver CBC.

We formulate a model that describes your problem:

  1. import pulp
  4. center_a_products = {
  5.     1: 8,
  6.     2: 4,
  7.     3: 12
  8. }
  10. product_quantities = {
  11.     1: {1: 10, 2: 5, 3: 15},
  12.     2: {1: 5, 2: 8, 3: 10},
  13.     3: {1: 12, 2: 6, 3: 20}
  14. }
  16. problem = pulp.LpProblem(&quot;CenterSatisfactionProblem&quot;, pulp.LpMinimize)
  18. # Center vars are binary variables that we minimize in the objective. They indicate whether a center was visited or not
  19. center_vars = {center: pulp.LpVariable(f&quot;Center_{center}&quot;, cat=&quot;Binary&quot;) for center in product_quantities}
  20. product_vars = {(center, product): pulp.LpVariable(f&quot;Center_{center}_Product_{product}&quot;, lowBound=0, cat=&quot;Integer&quot;)
  21.                 for center in product_quantities
  22.                 for product in product_quantities[center]}
  25. # Satisfy all demand
  26. for product in center_a_products:
  27.     problem += pulp.lpSum(product_vars[center, product] for center in product_quantities) == center_a_products[product]
  29. # We can only take stuff from a center if we visit it 
  30. # Also: can&#39;t take more stuff from a center than is in stock
  32. for center in product_quantities:
  33.     for product in product_quantities[center]:
  34.         problem += product_vars[center, product] &lt;= center_vars[center] * product_quantities[center][product]
  35. # Minimize amount of centers visited
  36. problem += pulp.lpSum(center_vars.values())
  37. problem.solve()

Print solution:

  1. for center in product_quantities:
  2.     if center_vars[center].varValue == 1:
  3.         for product in product_quantities[center]:
  4.             quantity = product_vars[center, product].varValue
  5.             if quantity &gt; 0:
  6.                 print(f&quot;Move {quantity} units of product {product} from center {center}&quot;)

Output:

  1. Move 8.0 units of product 1 from center 3
  2. Move 4.0 units of product 2 from center 3
  3. Move 12.0 units of product 3 from center 3

Currently the example you provided is pretty trivial. It's easily possible to add additional constraints, but you need to provide better description of the problem and the expected output.

Translating a problem description into a linear program can take some practice. The trickiest line in this program is

  1. problem += product_vars[center, product] &lt;= center_vars[center] * product_quantities[center][product]

The objective minimizes center_vars, but the satisfaction constraint forces some of them to be 1.

To get the mindset of describing problems, rather than thinking of solutions I recommend Raymond Hettinger's excellent talk on PyCon 2019 - Modern solvers: Problems well-defined are problems solved

to install PuLP

  1. pip install pulp

huangapple
  • 本文由 发表于 2023年7月3日 19:18:11
  • 转载请务必保留本文链接：https://go.coder-hub.com/76604223.html
  • combinations
  • math
  • optimization
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定