英文:
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，但似乎不支持动态排放费用，因为这些费用是按总量计算的，而不是按工厂水平计算的。
import numpy as np
from scipy.optimize import minimize
data = {
'1': (1.2,),
'2': (1.0,),
'3': (1.7,),
'4': (1.8,),
'5': (1.6,)
}
unit_cost_b = 8
limit_b = 100
echarge_b = 0.004
unit_cost_a = 5
limit_a = 60
echarge_a = 0.007
def objective(x):
x_a = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 0]
x_b = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 1]
total_unit_cost = (len(x_a) * unit_cost_a) + (len(x_b) * unit_cost_b)
total_usage_a = np.sum(x_a)
total_usage_b = np.sum(x_b)
emission_cost_a = max(total_usage_a - (len(x_a) * limit_a), 0) * echarge_a * 31
emission_cost_b = max(total_usage_b - (len(x_b) * limit_b), 0) * echarge_b * 31
return total_unit_cost + emission_cost_a + emission_cost_b
bounds = [(0, 1)] * len(data)
eq_cons = {'type': 'eq', 'fun': lambda x: np.sum(x) - 5}
x0 = [1,0,1,1,0]
print(x0)
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.
import numpy as np
from scipy.optimize import minimize
data = {
'1': (1.2,),
'2': (1.0,),
'3': (1.7,),
'4': (1.8,),
'5': (1.6,)
}
unit_cost_b = 8
limit_b = 100
echarge_b = 0.004
unit_cost_a = 5
limit_a = 60
echarge_a = 0.007
def objective(x):
x_a = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 0]
x_b = [data[str(i+1)][0] for i in range(len(data)) if x[i] == 1]
total_unit_cost = (len(x_a) * unit_cost_a) + (len(x_b) * unit_cost_b)
total_usage_a = np.sum(x_a)
total_usage_b = np.sum(x_b)
emission_cost_a = max(total_usage_a - (len(x_a) * limit_a), 0) * echarge_a * 31
emission_cost_b = max(total_usage_b - (len(x_b) * limit_b), 0) * echarge_b * 31
return total_unit_cost + emission_cost_a + emission_cost_b
bounds = [(0, 1)] * len(data)
eq_cons = {'type': 'eq', 'fun': lambda x: np.sum(x) - 5}
x0 = [1,0,1,1,0]
print(x0)
result = minimize(objective, x0, method='SLSQP', bounds=bounds, constraints=[eq_cons])
答案1
得分: 2
以下是翻译好的代码部分：
这是下面的`pulp`实现。你*可以*在`scipy`中使用`scipy.optimize.MILP`包来完成这个任务，但我相当肯定你需要将问题以矩阵格式开发，这是可行的，但是像`pulp`或`pyomo`这样的包可以为你完成，而且我认为它们更容易上手。
请注意，你**不能**在问题制定中使用`if`或`max()`，因为这些东西是非线性的，当问题交给求解器时，变量的值是*未知的*。而`pulp`大部分工作是制定要交付的问题……
在你的模型中，由于`limit`的值很大，排放数据似乎总是为零，但也许在更大的背景下或者你可以根据以下进行调整，这是有道理的。
#### 代码：
```python
# 工厂选择器
import pulp
data = {
'f1': (1.2,),
'f2': (1.0,),
'f3': (1.7,),
'f4': (1.8,),
'f5': (1.6,)
}
# unit_cost_b = 8
# limit_b = 100
# echarge_b = 0.004
# unit_cost_a = 5
# limit_a = 60
# echarge_a = 0.007
unit_cost = {'a': 5, 'b': 8}
limit = {'a': 60, 'b': 100}
echarge = {'a': 0.007, 'b': 0.004}
# 便利项....
factories = list(data.keys())
products = ['a', 'b']
fp = [(f, p) for f in factories for p in products]
### 问题设置
prob = pulp.LpProblem('factory_assignments', pulp.LpMinimize)
### 变量
# 如果制造该产品，则make[factory, product] == 1，否则为0...
make = pulp.LpVariable.dicts('make', fp, cat=pulp.LpBinary)
emission = pulp.LpVariable.dicts('emission', products, lowBound=0)
### 目标
# 一个便捷的表达式...
tot_unit_cost = sum(unit_cost * make[f, p] for f, p in fp)
prob += tot_unit_cost + sum(emission for p in products)
### 约束
# 限制排放大于等于表达式。它已经有一个lowBound=0，因此可以处理线性表达式中的max()。
for p in products:
prob += emission >= sum(make[f, p] * (data[f][0] - limit
) for f in factories) * echarge
* 31
# 每个工厂必须生产*某物*（只有一个东西）（这在原问题中是暗含的）
for f in factories:
prob += sum(make[f, p] for p in products) == 1
### 进行质量保证...
print(prob)
### 解决
soln = prob.solve()
for f, p in fp:
if make[f, p].varValue: # 如果变量为1，则为True
print(f'make {p} in factory {f}')
print(f'tot unit cost: {pulp.value(tot_unit_cost)}')
for p in products:
print(f'emission cost for {p} is: {emission.varValue}')
输出（截断）：
结果 - 找到最优解
目标值：25.00000000
枚举节点：0
总迭代次数：0
时间（CPU秒）：0.00
时间（墙钟秒）：0.00
打印选项已从正常更改为全部
总时间（CPU秒）：0.00（墙钟秒）：0.00
在工厂f1中制造a
在工厂f2中制造a
在工厂f3中制造a
在工厂f4中制造a
在工厂f5中制造a
tot unit cost: 25.0
a的排放成本为：0.0
b的排放成本为：0.0
[在100毫秒内完成]
<details>
<summary>英文:</summary>
This is a `pulp` implementation below. You *could* do this in `scipy` using the `scipy.optimize.MILP` pkg, but I'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.
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....
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.
#### CODE:
# factory picker
import pulp
data = {
'f1': (1.2,),
'f2': (1.0,),
'f3': (1.7,),
'f4': (1.8,),
'f5': (1.6,)
}
# unit_cost_b = 8
# limit_b = 100
# echarge_b = 0.004
# unit_cost_a = 5
# limit_a = 60
# echarge_a = 0.007
unit_cost = {'a': 5, 'b': 8}
limit = {'a': 60, 'b': 100}
echarge = {'a': 0.007, 'b': 0.004}
# conveniences....
factories = list(data.keys())
products = ['a', 'b']
fp = [(f, p) for f in factories for p in products]
### PROB SETUP
prob = pulp.LpProblem('factory_assignments', pulp.LpMinimize)
### VARS
# make[factory, product] == 1 if making that product, else 0...
make = pulp.LpVariable.dicts('make', fp, cat=pulp.LpBinary)
emission = pulp.LpVariable.dicts('emission', products, lowBound=0)
### OBJECTIVE
# a convenience expression...
tot_unit_cost = sum(unit_cost * make[f, p] for f, p in fp)
prob += tot_unit_cost + sum(emission
for p in products)
### CONSTRAINTS
# constrain the emission to GTE the expression. It already has a lowBound=0, so that
# handles the max() expression in a linear expression
for p in products:
prob += emission
>= sum(make[f, p] * (data[f][0] - limit
) for f in factories) * echarge
* 31
# each factory must produce *something* (and only 1 thing) (this is implied in the orig problem)
for f in factories:
prob += sum(make[f, p] for p in products) == 1
### QA it...
print(prob)
### SOLVE
soln = prob.solve()
for f, p in fp:
if make[f, p].varValue: # True if the variable is 1
print(f'make {p} in factory {f}')
print(f'tot unit cost: {pulp.value(tot_unit_cost)}')
for p in products:
print(f'emission cost for {p} is: {emission
.varValue}')
#### OUTPUT (truncated):
Result - Optimal solution found
Objective value: 25.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
make a in factory f1
make a in factory f2
make a in factory f3
make a in factory f4
make a in factory f5
tot unit cost: 25.0
emission cost for a is: 0.0
emission cost for b is: 0.0
[Finished in 100ms]
</details>
# 答案2
**得分**: 1
最简单的方法是使用蛮力法。如果无法将您的目标表达为线性函数，那可能是最佳选择。
示例：
```python
dims = 5
ranges = ((slice(0, 2, 1),) * dims)
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:
dims = 5
ranges = ((slice(0, 2, 1),) * dims)
x = scipy.optimize.brute(objective, ranges, finish=None)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论