英文:
How do I use a minimization function in python with constraints?
问题
我正在尝试用Python学习优化，但遇到了一些困难。我希望有人能帮助我理解以下问题。
假设我有以下数据：
| 卡车编号 | 物品 | 数量 | 地点 |
|---|---|---|---|
| 1 | 物品1 | 2 | 地点1 |
| 2 | 物品1 | 3 | 地点2 |
| 2 | 物品2 | 3 | 地点1 |
| 3 | 物品3 | 2 | 地点2 |
| 3 | 物品2 | 2 | 地点3 |
| 4 | 物品1 | 3 | 地点2 |
| 4 | 物品3 | 2 | 地点3 |
| 5 | 物品2 | 5 | 地点3 |
| 5 | 物品1 | 5 | 地点2 |
目标是在可能的情况下配对物品/地点，以最小化卡车必须停靠的次数，通过将相似的物品配对在一起。
停靠次数 = 卡车编号的唯一地点数。
例如，如果将“物品1”从“卡车编号1”移动到“卡车编号2”，并将“卡车编号2”上的“物品1”移动到“卡车编号1”，则可以节省一次停靠。这是因为现在两辆卡车都只前往一个地点。
约束条件之一是物品必须有足够的数量来服务该地点。每种物品/地点的总可用数量如下所示：
availability = {('物品1', '地点1'): 15,
('物品1', '地点2'): 28,
('物品1', '地点3'): 18,
('物品2', '地点1'): 10,
('物品2', '地点2'): 28,
('物品2', '地点3'): 12,
('物品3', '地点1'): 8,
('物品3', '地点2'): 10,
('物品3', '地点3'): 12
}
另一个约束是，如果一个物品在卡车上，那么唯一可以更改的是它要前往的地点。
例如，“卡车编号2”上有物品[1,2]前往地点[2,1]，在移动物品/地点组合后，“卡车编号2”必须仍然装载物品[1,2]。如前所述，理想情况是“卡车编号1”和“卡车编号2”交换“物品1”，因为这样“卡车编号2”将前往相同的地点，即“地点1”。这是可以接受的，因为“物品1”在“地点1”有足够的可用数量（总共15个单位）。
我对如何设置具有动态约束的问题感到困惑。是否有人能够帮助分解这个问题？
目标和样本解决方案：
最终输出应为最佳的卡车/物品/地点组合。
对于优化前两个卡车编号后的示例输出可能如下所示：
| 卡车编号 | 物品 | 数量 | 地点 |
|---|---|---|---|
| 1 | 物品1 | 2 | 地点2 |
| 2 | 物品1 | 3 | 地点1 |
| 2 | 物品2 | 3 | 地点1 |
“卡车编号2”和“卡车编号1”交换了“物品1”，以允许“卡车编号2”前往相同的地点。目标是重新分配卡车上的所有物品，以最小化每辆卡车必须前往的地点数，同时检查“可用性”字典中是否有足够数量的物品。
英文:
I am trying to learn optimization with python and I am struggling quite a bit. I am hoping someone can help me understand the following problem.
Lets say I have the following data:
| truck_number | item | qty | location |
|---|---|---|---|
| 1 | item1 | 2 | location1 |
| 2 | item1 | 3 | location2 |
| 2 | item2 | 3 | location1 |
| 3 | item3 | 2 | location2 |
| 3 | item2 | 2 | location3 |
| 4 | item1 | 3 | location2 |
| 4 | item3 | 2 | location3 |
| 5 | item2 | 5 | location3 |
| 5 | item1 | 5 | location2 |
The goal is to pair items / locations whenever possible to minimize the number of stops the truck has to make by pairing like items together.
Number of stops = Unique locations for a truck number.
For example a stop can be saved if item1 going to location1 on truck_number 1 is moved to truck_number 2 and item1 on truck_number 2 is moved to truck_number 1. This would save one stop. This is because both trucks are now only going to one location.
Constraints
One of the constraints is that the item must have enough to service that location. The total number available for each item / location is listed as dictionary below. For example item1 only has 10 units available to go to location1.
availability = {('item1', 'location1'): 15,
('item1', 'location2'): 28,
('item1', 'location3'): 18,
('item2', 'location1'): 10,
('item2', 'location2'): 28,
('item2', 'location3'): 12,
('item3', 'location1'): 8,
('item3', 'location2'): 10,
('item3', 'location3'): 12
}
The other constraint is that if an item is on a truck, then the only thing that can change is the location it is going to.
For example truck number 2 has items [1,2] going to locations [2,1] truck_number 2 must have items [1,2] on it after shifting item / location combinations. Like stated before, the ideal scenario would have truck number 1 and truck number two switch item 1 because truck number 2 would then be going to the same location, location 1. This is ok because item1 has enough available to serve location1 (15 total units).
I am confused on how to set up a problem like this with dynamic constraints. Would anyone be able to help break down the problem?
Goal and Sample Solution
The ending output should be the optimal truck / item / location combination.
A sample output after optimizing for the first two truck numbers might look like this:
| truck_number | item | qty | location |
|---|---|---|---|
| 1 | item1 | 2 | location2 |
| 2 | item1 | 3 | location1 |
| 2 | item2 | 3 | location1 |
truck_number_2 and truck_number_1 switched item1 to allow truck_number_2 to go to the same location. The goal would be to reallocate all items on trucks to minimize the number of locations each truck has to go to, while checking to make sure there is enough of the item at the location in the availability dictionary.
答案1
得分: 2
我只翻译代码部分，以下是代码的翻译：
from io import StringIO
import numpy as np
import pandas as pd
from scipy.optimize import milp, Bounds, LinearConstraint
with StringIO('''
truck item quantity location
1 item1 2 location1
2 item1 3 location2
2 item2 3 location1
3 item3 2 location2
3 item2 2 location3
4 item1 3 location2
4 item3 2 location3
5 item2 5 location3
5 item1 5 location2
''') as f:
orders = pd.read_csv(f, sep='\t')
"""
最小化每辆卡车的唯一位置数。
卡车-物品对是固定的且唯一的。
物品-数量-位置三元组（"订单"）是固定的且不唯一的。
订单分配给卡车-物品对是可变的。
位置的每个数量之和必须小于或等于可用数量。由于物品-位置
分配永远不会改变，这对优化没有影响，因此被忽略。
决策变量：
卡车-位置之和（已优化）
卡车-位置分配（未优化）
订单-卡车分配（未优化）
"""
n_orders = len(orders)
trucks = orders.truck.unique()
n_trucks = len(trucks)
locations = orders.location.unique()
n_locations = len(locations)
items = orders.item.unique()
n_items = len(items)
n_location_costs = n_trucks * n_locations
n_assignments = n_trucks * n_orders
c = np.empty(n_trucks + n_location_costs + n_assignments, dtype=int)
c[:n_trucks] = 1 # 最小化卡车位置之和
c[n_trucks:] = 0 # 其他变量不考虑
# 所有决策变量：卡车位置之和，卡车位置分配和卡车订单分配都是整数
integrality = np.ones(n_trucks + n_location_costs + n_assignments, dtype=int)
lower = np.empty_like(c)
lower[:n_trucks] = 1 # 每辆卡车至少有一个位置
lower[n_trucks: n_trucks + n_location_costs] = 0 # 卡车-位置分配可能不存在
lower[-n_assignments:] = 0 # 每个潜在的卡车-订单分配可能不存在
upper = np.empty_like(c)
upper[:n_trucks] = n_locations # 每辆卡车最多可以有所有位置
upper[n_trucks: n_trucks + n_location_costs] = 1 # 卡车-位置分配可能存在
upper[-n_assignments:] = 1 # 每个潜在的卡车-订单分配可能存在
# 卡车位置之和 = 卡车位置分配之和
# 0 = -(卡车位置) + sum(卡车位置分配)
lb_truck_location = ub_truck_location = np.zeros(n_trucks, dtype=int)
A_truck_location = np.hstack((
-np.eye(n_trucks, dtype=int), # -(卡车位置)
np.eye(n_trucks, dtype=int).repeat(n_locations, axis=1), # sum(卡车位置分配)
np.zeros((n_trucks, n_assignments), dtype=int), # 订单分配不适用
))
# 如果卡车-位置对至少有一个订单分配，卡车-位置分配为1
# 这意味着：卡车-位置分配 >= 订单分配 / (1 + 最大可能订单)
# 0 <= (卡车-位置分配)(1 + 最大可能订单) - sum(订单分配)
order_matches_location = np.equal.outer(locations, orders.location.values).astype(int) # 2D数组：给定位置行的订单列？
order_kronecker = np.kron(np.eye(n_trucks, dtype=int), order_matches_location) # 通过位置Kronecker平铺所有卡车-订单分配
lb_location_cost_bottom = np.zeros(n_location_costs, dtype=int)
ub_location_cost_bottom = np.full(shape=n_location_costs, fill_value=np.inf)
A_location_cost_bottom = np.hstack((
np.zeros((n_location_costs, n_trucks), dtype=int), # 卡车位置之和不适用
np.eye(n_location_costs, dtype=int) * (1 + n_orders), # (卡车-位置分配)(1 + 最大可能订单)
-order_kronecker, # -sum(订单分配)
))
# 卡车-位置分配也有上限：卡车-位置分配 <= sum(订单分配)
# sum(订单分配) - 卡车-位置分配 >= 0
lb_location_cost_top = lb_location_cost_bottom
ub_location_cost_top = np.full(n_location_costs, np.inf)
A_location_cost_top = np.hstack((
np.zeros((n_location_costs, n_trucks), dtype=int), # 卡车位置之和不适用
-np.eye(n_location_costs, dtype=int), # -卡车-位置分配
order_kronecker, # sum(订单分配)
))
# 订单分配必须与卡车有唯一的（1:1）映射
lb_unique_order = ub_unique_order = np.ones(n_orders, dtype=int)
A_unique_order = np.hstack((
np.zeros((n_orders, n_trucks), dtype=int), # 卡车位置之和不适用
np.zeros((n_orders, n_location_costs), dtype=int), # 卡车-位置分配不适用
np.tile(np.eye(n_orders, dtype=int), (1, n_trucks)) # 每辆卡车的所有订单分配
))
# 物品类型的存在（无论数量或位置如何）在卡车上不得改变
order_matches_item = np.equal.outer(items, orders.item.values).astype(int)
initial_trucks = np.equal.outer(trucks, orders.truck.values).astype(int)
truck_items = order_matches_item @ initial_trucks.T
item_kronecker = np.kron(np.eye(n_trucks, dtype=int), order_matches_item)
initial_kronecker = item_kronecker[truck_items.T.ravel().astype(bool), :]
kn = initial_krone
<details>
<summary>英文:</summary>
I had to do a lot of guessing to come up with this, given how astonishingly poor your description remains. I ignore your _A sample output after optimizing for the first two truck numbers might look like this_ because it's internally inconsistent in terms of quantity. I also ignore quantity entirely, since you seem to imply that location-item-quantity triples are immutable; that means there's no sense in applying location-item-quantity constraints.
```python
from io import StringIO
import numpy as np
import pandas as pd
from scipy.optimize import milp, Bounds, LinearConstraint
with StringIO('''truck item quantity location
1 item1 2 location1
2 item1 3 location2
2 item2 3 location1
3 item3 2 location2
3 item2 2 location3
4 item1 3 location2
4 item3 2 location3
5 item2 5 location3
5 item1 5 location2
''') as f:
orders = pd.read_csv(f, sep='\t')
"""
Minimize the number of unique locations per truck.
Truck-item pairs are fixed and unique.
Item-quantity-location triples ("orders") are fixed and non-unique.
Assignment of orders to truck-item pairs is variable.
Quantity sum per location must be less than or equal to availability. Since item-location
assignments never change, this has no effect on the optimisation and is ignored.
Decision variables:
Truck-location sums (optimised)
Truck-location assignments (non-optimised)
Order-truck assignments (non-optimised)
"""
n_orders = len(orders)
trucks = orders.truck.unique()
n_trucks = len(trucks)
locations = orders.location.unique()
n_locations = len(locations)
items = orders.item.unique()
n_items = len(items)
n_location_costs = n_trucks * n_locations
n_assignments = n_trucks * n_orders
c = np.empty(n_trucks + n_location_costs + n_assignments, dtype=int)
c[:n_trucks] = 1 # truck location sums are minimized
c[n_trucks:] = 0 # nothing else is
# All decision variables: truck location sums, truck location assignments and truck order assignment are integral
integrality = np.ones(n_trucks + n_location_costs + n_assignments, dtype=int)
lower = np.empty_like(c)
lower[:n_trucks] = 1 # Every truck has at least one location
lower[n_trucks: n_trucks+n_location_costs] = 0 # Truck-location assignments might not exist
lower[-n_assignments:] = 0 # Every potential truck-order assignment might not exist
upper = np.empty_like(c)
upper[:n_trucks] = n_locations # Every truck can have at most all locations
upper[n_trucks: n_trucks+n_location_costs] = 1 # Truck-location assignments might exist
upper[-n_assignments:] = 1 # Every potential truck-order assignment might exist
# Truck location sum = sum of truck-location assignments
# 0 = -(truck_locations) + sum(truck_location_assignments)
lb_truck_location = ub_truck_location = np.zeros(n_trucks, dtype=int)
A_truck_location = np.hstack((
-np.eye(n_trucks, dtype=int), # -(truck_locations)
np.eye(n_trucks, dtype=int).repeat(n_locations, axis=1), # sum(truck_location_assignments)
np.zeros((n_trucks, n_assignments), dtype=int), # order assignments N/A
))
# truck-location assignment is 1 if there is at least one order assignment for that truck-location pair
# That means: truck_location_assignment >= order_assignments / (1 + max_possible_orders)
# 0 <= (truck_location_assignment)(1 + max_possible_orders) - sum(order_assignments)
order_matches_location = np.equal.outer(locations, orders.location.values).astype(int) # 2D array: is the given order column for this location row?
order_kronecker = np.kron(np.eye(n_trucks, dtype=int), order_matches_location) # Kronecker-tile all truck-order assignments by location
lb_location_cost_bottom = np.zeros(n_location_costs, dtype=int)
ub_location_cost_bottom = np.full(shape=n_location_costs, fill_value=np.inf)
A_location_cost_bottom = np.hstack((
np.zeros((n_location_costs, n_trucks), dtype=int), # Truck-location sums N/A
np.eye(n_location_costs, dtype=int)*(1 + n_orders), # (truck_location_assignment)(1 + max_possible_orders)
-order_kronecker, # -sum(order_assignments)
))
# Truck-location assignments also have an upper limit: truck_location_assignment <= sum(order_assignments)
# sum(order_assignments) - truck_location_assignment >= 0
lb_location_cost_top = lb_location_cost_bottom
ub_location_cost_top = np.full(n_location_costs, np.inf)
A_location_cost_top = np.hstack((
np.zeros((n_location_costs, n_trucks), dtype=int), # Truck-location sums N/A
-np.eye(n_location_costs, dtype=int), # -truck_location_assignment
order_kronecker, # sum(order_assignments)
))
# Order assignments must have a unique (1:1) mapping to trucks
lb_unique_order = ub_unique_order = np.ones(n_orders, dtype=int)
A_unique_order = np.hstack((
np.zeros((n_orders, n_trucks), dtype=int), # Truck-location sums N/A
np.zeros((n_orders, n_location_costs), dtype=int), # Truck-location assignments N/A
np.tile(np.eye(n_orders, dtype=int), (1, n_trucks)) # All order assignments for each truck
))
# The presence of an item type (regardless of quantity or location) on a truck must not change
order_matches_item = np.equal.outer(items, orders.item.values).astype(int)
initial_trucks = np.equal.outer(trucks, orders.truck.values).astype(int)
truck_items = order_matches_item @ initial_trucks.T
item_kronecker = np.kron(np.eye(n_trucks, dtype=int), order_matches_item)
initial_kronecker = item_kronecker[truck_items.T.ravel().astype(bool), :]
kn = initial_kronecker.shape[0]
lb_truck_item = np.ones(kn, dtype=int)
ub_truck_item = np.full(kn, np.inf)
A_truck_item = np.hstack((
np.zeros((kn, n_trucks), dtype=int),
np.zeros((kn, n_location_costs), dtype=int),
initial_kronecker,
))
all_lb = np.concatenate((lb_truck_location, lb_location_cost_bottom, lb_location_cost_top, lb_unique_order, lb_truck_item))
all_ub = np.concatenate((ub_truck_location, ub_location_cost_bottom, ub_location_cost_top, ub_unique_order, ub_truck_item))
all_A = np.vstack (( A_truck_location, A_location_cost_bottom, A_location_cost_top, A_unique_order, A_truck_item))
result = milp(
c=c, integrality=integrality, bounds=Bounds(lb=lower, ub=upper),
constraints=LinearConstraint(lb=all_lb, A=all_A, ub=all_ub),
)
print(result.message)
assert result.success
truck_location_sums = result.x[:n_trucks]
truck_location_assignments = result.x[n_trucks: n_trucks+n_location_costs].reshape((n_trucks, -1))
truck_order_assignments = result.x[-n_assignments:].reshape((n_trucks, -1))
print('Locations per truck:')
print(truck_location_sums.astype(int))
print()
print('Truck-location assignments:')
print(truck_location_assignments.astype(int))
print()
print('Truck-order assignments:')
print(truck_order_assignments.astype(int))
orders['new_truck'] = np.broadcast_to(trucks, (n_orders, n_trucks))[truck_order_assignments.astype(bool).T]
print(orders)
Optimization terminated successfully. (HiGHS Status 7: Optimal)
Locations per truck:
[1 1 1 1 2]
Truck-location assignments:
[[0 1 0]
[1 0 0]
[0 0 1]
[0 1 0]
[0 1 1]]
Truck-order assignments:
[[0 1 0 0 0 0 0 0 0]
[1 0 1 0 0 0 0 0 0]
[0 0 0 0 1 0 1 0 0]
[0 0 0 1 0 0 0 0 1]
[0 0 0 0 0 1 0 1 0]]
truck item quantity location new_truck
0 1 item1 2 location1 2
1 2 item1 3 location2 1
2 2 item2 3 location1 2
3 3 item3 2 location2 4
4 3 item2 2 location3 3
5 4 item1 3 location2 5
6 4 item3 2 location3 3
7 5 item2 5 location3 5
8 5 item1 5 location2 4
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论