Scipy优化-最小化用于组合问题 – 仅整数解

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

Scipy Optimize Minimize For Combinatorics - Integer only solutions

问题

我有以下代码，试图将最佳产品（a或b）分配给每个工厂（1、2、3、4或5）。
如何设置约束/边界，以仅使用整数值0或1？
例如，我已设置x0 = [1,0,1,1,0]，对于此示例数据的解决方案是[0,0,0,0,0]。
此外，这种方法是否正确解决了这个问题？我还尝试过pulp，但似乎不支持动态排放费用，因为这些费用是按总量计算的，而不是按工厂水平计算的。

  1. import numpy as np
  2. from scipy.optimize import minimize
  4. data = {
  5.     '1': (1.2,),
  6.     '2': (1.0,),
  7.     '3': (1.7,),
  8.     '4': (1.8,),
  9.     '5': (1.6,)
  10. }
  12. unit_cost_b = 8
  13. limit_b = 100
  14. echarge_b = 0.004
  16. unit_cost_a = 5
  17. limit_a = 60
  18. echarge_a = 0.007
  20. def objective(x):
  21.     x_a = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 0]
  22.     x_b = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 1]
  24.     total_unit_cost = (len(x_a) * unit_cost_a) + (len(x_b) * unit_cost_b)
  25.     total_usage_a = np.sum(x_a)
  26.     total_usage_b = np.sum(x_b)
  28.     emission_cost_a = max(total_usage_a - (len(x_a) * limit_a), 0) * echarge_a * 31
  29.     emission_cost_b = max(total_usage_b - (len(x_b) * limit_b), 0) * echarge_b * 31
  31.     return total_unit_cost + emission_cost_a + emission_cost_b
  33. bounds = [(0, 1)] * len(data)
  34. eq_cons = {'type': 'eq', 'fun': lambda x: np.sum(x) - 5}
  36. x0 = [1,0,1,1,0]
  37. print(x0)
  38. result = minimize(objective, x0, method='SLSQP', bounds=bounds, constraints=[eq_cons])
英文:

I have the below code that tries to assign the best product (a or b) to each factory (1,2,3,4 or 5).
How do I set constraints/bounds so that it only uses the integer values 0 or 1?
e.g I have set x0 = [1,0,1,1,0] and the solution for this sample data is [0,0,0,0,0]
Also, Is this even this correct approach to solve this problem? I have also tried pulp,
but it does not seem to support the dynamic emission charges, as these are calculated in aggregate not at a factory level.

  1. import numpy as np
  2. from scipy.optimize import minimize
  4. data = {
  5.     '1': (1.2,),
  6.     '2': (1.0,),
  7.     '3': (1.7,),
  8.     '4': (1.8,),
  9.     '5': (1.6,)
  10. }
  12. unit_cost_b = 8
  13. limit_b = 100
  14. echarge_b = 0.004
  16. unit_cost_a = 5
  17. limit_a = 60
  18. echarge_a = 0.007
  21. def objective(x):
  22.     x_a = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 0]
  23.     x_b = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 1]
  25.     total_unit_cost = (len(x_a) * unit_cost_a) + (len(x_b) * unit_cost_b)
  26.     total_usage_a = np.sum(x_a)  
  27.     total_usage_b = np.sum(x_b)
  28.     
  29.     emission_cost_a = max(total_usage_a - (len(x_a) * limit_a), 0) * echarge_a * 31
  30.     emission_cost_b = max(total_usage_b - (len(x_b) * limit_b), 0) * echarge_b * 31
  32.     return total_unit_cost + emission_cost_a + emission_cost_b
  34. bounds = [(0, 1)] * len(data) 
  35. eq_cons = {'type': 'eq', 'fun': lambda x: np.sum(x) - 5}
  38. x0 = [1,0,1,1,0]
  39. print(x0)
  40. result = minimize(objective, x0, method='SLSQP', bounds=bounds, constraints=[eq_cons])

答案1

得分: 2

以下是翻译好的代码部分：

  1. 这是下面的`pulp`实现。你*可以*在`scipy`中使用`scipy.optimize.MILP`包来完成这个任务，但我相当肯定你需要将问题以矩阵格式开发，这是可行的，但是像`pulp`或`pyomo`这样的包可以为你完成，而且我认为它们更容易上手。
  3. 请注意，你**不能**在问题制定中使用`if`或`max()`，因为这些东西是非线性的，当问题交给求解器时，变量的值是*未知的*。而`pulp`大部分工作是制定要交付的问题……
  5. 在你的模型中，由于`limit`的值很大，排放数据似乎总是为零，但也许在更大的背景下或者你可以根据以下进行调整，这是有道理的。
  7. #### 代码：
  9. ```python
  10. # 工厂选择器
  12. import pulp
  14. data = {
  15.     'f1': (1.2,),
  16.     'f2': (1.0,),
  17.     'f3': (1.7,),
  18.     'f4': (1.8,),
  19.     'f5': (1.6,)
  20. }
  22. # unit_cost_b = 8
  23. # limit_b = 100
  24. # echarge_b = 0.004
  26. # unit_cost_a = 5
  27. # limit_a = 60
  28. # echarge_a = 0.007
  30. unit_cost = {'a': 5, 'b': 8}
  31. limit = {'a': 60, 'b': 100}
  32. echarge = {'a': 0.007, 'b': 0.004}
  34. # 便利项....
  35. factories = list(data.keys())
  36. products = ['a', 'b']
  37. fp = [(f, p) for f in factories for p in products]
  39. ### 问题设置
  40. prob = pulp.LpProblem('factory_assignments', pulp.LpMinimize)
  42. ### 变量
  44. # 如果制造该产品，则make[factory, product] == 1，否则为0...
  45. make = pulp.LpVariable.dicts('make', fp, cat=pulp.LpBinary)
  47. emission = pulp.LpVariable.dicts('emission', products, lowBound=0)
  49. ### 目标
  51. # 一个便捷的表达式...
  52. tot_unit_cost = sum(unit_cost
     * make[f, p] for f, p in fp)
  54. prob += tot_unit_cost + sum(emission
     for p in products)
  56. ### 约束
  58. # 限制排放大于等于表达式。它已经有一个lowBound=0，因此可以处理线性表达式中的max()。
  59. for p in products:
  60.     prob += emission
     >= sum(make[f, p] * (data[f][0] - limit
    ) for f in factories) * echarge
     * 31
  62. # 每个工厂必须生产*某物*（只有一个东西）（这在原问题中是暗含的）
  63. for f in factories:
  64.     prob += sum(make[f, p] for p in products) == 1
  66. ### 进行质量保证...
  67. print(prob)
  69. ### 解决
  70. soln = prob.solve()
  72. for f, p in fp:
  73.     if make[f, p].varValue:   # 如果变量为1，则为True
  74.         print(f'make {p} in factory {f}')
  76. print(f'tot unit cost: {pulp.value(tot_unit_cost)}')
  78. for p in products:
  79.     print(f'emission cost for {p} is: {emission
    .varValue}')

输出（截断）：

  1. 结果 - 找到最优解
  2. 目标值：25.00000000
  3. 枚举节点：0
  4. 总迭代次数：0
  5. 时间（CPU秒）：0.00
  6. 时间（墙钟秒）：0.00
  7. 打印选项已从正常更改为全部
  8. 总时间（CPU秒）：0.00（墙钟秒）：0.00
  9. 在工厂f1中制造a
  10. 在工厂f2中制造a
  11. 在工厂f3中制造a
  12. 在工厂f4中制造a
  13. 在工厂f5中制造a
  14. tot unit cost: 25.0
  15. a的排放成本为：0.0
  16. b的排放成本为：0.0

[在100毫秒内完成]

  2. <details>
  3. <summary>英文:</summary>
  4. This is a `pulp` implementation below.  You *could* do this in `scipy` using the `scipy.optimize.MILP` pkg, but I&#39;m pretty sure you would need to develop the problem in matrix format, which is doable, but packages such as `pulp` or `pyomo` do it for you and I think they are much more approachable.
  5. Realize, you **cannot** use `if` or `max()` in problem formulation as those things are nonlinear and the value of the variables is *not known* when the problem is handed over to a solver.  And the bulk of what `pulp` is doing is making the problem to hand over....
  6. On your model, the emissions data is odd and seems to always be zero because of the large values of `limit`, but perhaps it makes sense in larger context or you can adjust from the below.
  7. #### CODE:
  8. # factory picker
  9. import pulp
  10. data = {
  11. &#39;f1&#39;: (1.2,),
  12. &#39;f2&#39;: (1.0,),
  13. &#39;f3&#39;: (1.7,),
  14. &#39;f4&#39;: (1.8,),
  15. &#39;f5&#39;: (1.6,)
  16. }
  17. # unit_cost_b = 8
  18. # limit_b = 100
  19. # echarge_b = 0.004
  20. # unit_cost_a = 5
  21. # limit_a = 60
  22. # echarge_a = 0.007
  23. unit_cost = {&#39;a&#39;: 5, &#39;b&#39;: 8}
  24. limit = {&#39;a&#39;: 60, &#39;b&#39;: 100}
  25. echarge = {&#39;a&#39;: 0.007, &#39;b&#39;: 0.004}
  26. # conveniences....
  27. factories = list(data.keys())
  28. products = [&#39;a&#39;, &#39;b&#39;]
  29. fp = [(f, p) for f in factories for p in products]
  30. ### PROB SETUP
  31. prob = pulp.LpProblem(&#39;factory_assignments&#39;, pulp.LpMinimize)
  32. ### VARS
  33. # make[factory, product] == 1 if making that product, else 0...
  34. make = pulp.LpVariable.dicts(&#39;make&#39;, fp, cat=pulp.LpBinary)
  35. emission = pulp.LpVariable.dicts(&#39;emission&#39;, products, lowBound=0)
  36. ### OBJECTIVE
  37. # a convenience expression...
  38. tot_unit_cost = sum(unit_cost
     * make[f, p] for f, p in fp)
  39. prob += tot_unit_cost + sum(emission
     for p in products)
  40. ### CONSTRAINTS
  41. # constrain the emission to GTE the expression.  It already has a lowBound=0, so that
  42. # handles the max() expression in a linear expression
  43. for p in products:
  44. prob += emission
     &gt;= sum(make[f, p] * (data[f][0] - limit
    ) for f in factories) * echarge
     * 31
  45. # each factory must produce *something*  (and only 1 thing)  (this is implied in the orig problem)
  46. for f in factories:
  47. prob += sum(make[f, p] for p in products) == 1
  48. ### QA it...
  49. print(prob)
  50. ### SOLVE
  51. soln = prob.solve()
  52. for f, p in fp:
  53. if make[f, p].varValue:   # True if the variable is 1
  54. print(f&#39;make {p} in factory {f}&#39;)
  55. print(f&#39;tot unit cost: {pulp.value(tot_unit_cost)}&#39;)
  56. for p in products:
  57. print(f&#39;emission cost for {p} is: {emission
    .varValue}&#39;)
  58. #### OUTPUT (truncated):
  59. Result - Optimal solution found
  60. Objective value:                25.00000000
  61. Enumerated nodes:               0
  62. Total iterations:               0
  63. Time (CPU seconds):             0.00
  64. Time (Wallclock seconds):       0.00
  65. Option for printingOptions changed from normal to all
  66. Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00
  67. make a in factory f1
  68. make a in factory f2
  69. make a in factory f3
  70. make a in factory f4
  71. make a in factory f5
  72. tot unit cost: 25.0
  73. emission cost for a is: 0.0
  74. emission cost for b is: 0.0
  75. [Finished in 100ms]
  76. </details>
  77. # 答案2
  78. **得分**: 1
  79. 最简单的方法是使用蛮力法。如果无法将您的目标表达为线性函数，那可能是最佳选择。
  80. 示例：
  81. ```python
  82. dims = 5
  83. ranges = ((slice(0, 2, 1),) * dims)
  84. x = scipy.optimize.brute(objective, ranges, finish=None)
英文:

The simplest approach would be to use brute force. If you can't express your objective as a linear function, that might be your best bet.

Example:

  1. dims = 5
  2. ranges = ((slice(0, 2, 1),) * dims)
  3. x = scipy.optimize.brute(objective, ranges, finish=None)

huangapple
  • 本文由 发表于 2023年6月19日 06:03:54
  • 转载请务必保留本文链接：https://go.coder-hub.com/76502699.html
  • combinatorics
  • pulp
  • python
  • scipy
匿名

发表评论

匿名网友

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

确定