问题
我正在使用 LINGO（我有建模数学问题的经验）和 Or-tools 实现一个广义分配问题，但结果不同。
我的作业问题的简要说明
我有一组需要建造的房屋（在模型中称为“对象”）。每个房子都需要一套资源。为了提供这些资源，有 3 个供应商。资源成本因供应商而异。
该模型应将这些供应商分配给房屋，以最小化分配的总成本。
模型
参数
- resource_cost_per_supplier[i,j] ：供应商j的资源i的成本。
- resource_cost_factor_per_object[i,j]：表示对象所需资源的矩阵（成本因子 > 0）。此外，它还包含对象j所需资源i的成本因子。该因素是根据对象建造期间资源使用的持续时间以及其他合同因素计算得出的。
- vendor_budget_limit[j] : 供应商j的供应商预算限制。每个供应商都有一个不应超过的预算限制（在合同中）。
- Supplier_budget_tolerance_margin_limit[j] : 供应商j的供应商预算容差边际限制。对于模型的工作，我必须创建这个公差边际，将其应用于供应商预算限制，以创建一个可接受的供应商成本范围。
- object_demand_attended_per_supplier[i,j]：表示供应商i是否拥有对象j所需的所有资源的二进制矩阵。
变量
- x[i,j] : 指示供应商i是否 (1) 或不 (0) 分配给对象j的二进制变量。
- 供应商成本[j] ：表示供应商j在市场份额中的成本的变量其值由下式给出：
- total_cost：表示市场份额总成本的变量。其值由下式给出：
目标函数
最小 Z = 总成本
约束
1 - 确保每个对象j只有一个供应商i。
2 - 对于每个供应商i，您所有任务的成本总和必须大于或等于您的预算限制减去公差边际。
3 - 对于每个供应商j，您所有任务的成本总和必须小于或等于您的预算限制加上公差边际。
4 -如果供应商i不能提供对象 j 的所有资源，则确保供应商i不会分配给对象j。
5 - 确保变量x对于每个供应商i和对象j都是二进制的。
代码
或工具 (Python)
from __future__ import print_function
from ortools.linear_solver import pywraplp
import pandas as pd
import numpy
###### [START] parameters ######
num_objects = 252 #Number of objects
num_resources = 35 #Number of resources (not every object will use all resources. It depends of the type of the object and other things)
num_suppliers = 3 #Number of suppliers
resource_cost_per_supplier = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/resource_cost_per_supplier.csv', index_col = 0).to_numpy()
resource_cost_factor_per_object = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/resource_cost_factor_per_object.csv', index_col = 0).to_numpy()
object_demand_attended_per_supplier = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/object_demand_attended_per_supplier.csv', index_col = 0).to_numpy()
supplier_budget_limit = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/supplier_budget_limit.csv', index_col = 0)['budget_limit'].values
supplier_budget_tolerance_margin_limit = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/supplier_budget_tolerance_margin_limit.csv', index_col = 0)['tolerance_margin'].values
###### [END] parameters ######
###### [START] variables ######
#Assignment variable
x = {}
supplier_cost = []
#Total cost of market share
total_cost = 0
###### [END] variables ######
def main():
#Declare the solver
solver = pywraplp.Solver('GeneralizedAssignmentProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
#Assignment variable
#x = {}
#Ensure that the assignment variable is binary
for i in range(num_suppliers):
for j in range(num_objects):
x[i, j] = solver.BoolVar('x[%i,%i]' % (i,j))
#Assigning an expression to each supplier_cost element
for j in range(num_suppliers):
supplier_cost.append(solver.Sum(solver.Sum(resource_cost_per_supplier[i,j] * resource_cost_factor_per_object[i,k] * x[j,k] for k in range(num_objects)) for i in range(num_resources)))
#Total cost of market share
total_cost = solver.Sum(supplier_cost[j] for j in range(num_suppliers))
#Objective function
solver.Minimize(total_cost)
###### [START] constraints ######
# 1 - Ensure that each object will have only one supplier
for j in range(num_objects):
solver.Add(solver.Sum([x[i,j] for i in range(num_suppliers)]) == 1)
# 2 - For each supplier j, the sum of the cost of all your allocations must be greater than or equal to your budget limit minus the tolerance margin
for j in range(num_suppliers):
solver.Add(supplier_cost[j] >= total_cost * (supplier_budget_limit[j] - supplier_budget_tolerance_margin_limit[j]))
# 3 - For each supplier j, the sum of the cost of all your allocations must be less than or equal to your budget limit plus the tolerance margin
for j in range(num_suppliers):
solver.Add(supplier_cost[j] <= total_cost * (supplier_budget_limit[j] + supplier_budget_tolerance_margin_limit[j]))
# 4 - Ensure that a supplier i will not assigned to an object j if the supplier i can not supply all resources demanded by object j
for i in range(num_suppliers):
for j in range(num_objects):
solver.Add(x[i,j] - object_demand_attended_per_supplier[i,j] <= 0)
###### [END] constraints ######
solution = solver.Solve()
#Print the result
if solution == pywraplp.Solver.OPTIMAL:
print('------- Solution -------')
print('Total cost =', round(total_cost.solution_value(), 2))
for i in range(num_suppliers):
print('-----')
print('Supplier', i)
print('-> cost:', round(supplier_cost[i].solution_value(), 2))
print('-> cost percentage:', format(supplier_cost[i].solution_value()/total_cost.solution_value(),'.2%'))
print('-> supplier budget limit:', format(supplier_budget_limit[i], '.0%'))
print('-> supplier budget tolerance margin limit:', format(supplier_budget_tolerance_margin_limit[i], '.0%'))
print('-> acceptable range: {0} <= cost percentage <= {1}'.format(format(supplier_budget_limit[i] - supplier_budget_tolerance_margin_limit[i], '.0%'), format(supplier_budget_limit[i] + supplier_budget_tolerance_margin_limit[i], '.0%')))
# print('-> objects: {0}'.format(i))
else:
print('The problem does not have an optimal solution.')
#Generate a result to consult
assignment_result = pd.DataFrame(columns=['object','supplier','cost','assigned'])
for i in range(num_suppliers):
for j in range(num_objects):
assignment_result = assignment_result.append({'object': j, 'supplier': i, 'cost': get_object_cost(j, i), 'assigned': x[i, j].solution_value()}, ignore_index=True)
assignment_result.to_excel('assignment_result.xlsx')
def get_object_cost(object_index, supplier_index):
object_cost = 0.0
for i in range(num_resources):
object_cost = object_cost + resource_cost_factor_per_object[i,object_index] * resource_cost_per_supplier[i,supplier_index]
return object_cost
#Run main
main()
语言
model:
title: LINGO;
data:
!Number of objects;
num_objects = @OLE('LINGO_input.xlsx',num_objects);
!Number of resources (not every object will use all resources. It depends of the type of the object and other things);
num_resources = @OLE('LINGO_input.xlsx',num_resources);
!Number of suppliers;
num_suppliers = @OLE('LINGO_input.xlsx',num_suppliers);
enddata
sets:
suppliers/1..num_suppliers/:supplier_budget_limit,supplier_tolerance_margin_limit,supplier_cost;
resources/1..num_resources/:;
objects/1..num_objects/:;
resources_suppliers(resources,suppliers):resource_cost_per_supplier;
resources_objects(resources,objects):resource_cost_factor_per_object;
suppliers_objects(suppliers,objects):x,object_demand_attended_supplier;
endsets
data:
resource_cost_per_supplier = @OLE('LINGO_input.xlsx',resource_cost_per_supplier[cost]);
resource_cost_factor_per_object = @OLE('LINGO_input.xlsx',resource_cost_factor_per_object[cost_factor]);
supplier_budget_limit = @OLE('LINGO_input.xlsx',supplier_budget_limit[budget_limit_percentage]);
supplier_tolerance_margin_limit = @OLE('LINGO_input.xlsx',supplier_budget_tolerance_margin_limit[budget_tolerance_percentage]);
object_demand_attended_supplier = @OLE('LINGO_input.xlsx',object_demand_attended_per_supplier[supply_all_resources]);
enddata
!The array 'supplier_cost' was created to store the total cost of each supplier;
@FOR(suppliers(j):supplier_cost(j)= @SUM(resources(i):@SUM(objects(k):resource_cost_per_supplier(i,j)*resource_cost_factor_per_object(i,k)*x(j,k))));
!Total cost of market share;
total_cost = @SUM(suppliers(i):supplier_cost(i));
!Objective function;
min = total_cost;
!Ensure that each object will have only one supplier;
@FOR(objects(j):@SUM(suppliers(i):x(i,j))=1);
!For each supplier j, the sum of the cost of all your assignments must be greater than or equal to your budget limit minus the tolerance margin;
@FOR(suppliers(j):supplier_cost(j) >= total_cost*(supplier_budget_limit(j)-supplier_tolerance_margin_limit(j)));
!For each supplier j, the sum of the cost of all your assignments must be less than or equal to your budget limit plus the tolerance margin;
@FOR(suppliers(j):supplier_cost(j) <= total_cost*(supplier_budget_limit(j)+supplier_tolerance_margin_limit(j)));
!Ensure that a supplier j will not assigned to an object k if the supplier j can not supply all resources demanded by object k;
@FOR(suppliers(j):@FOR(objects(k):x(j,k)-object_demand_attended_supplier(j,k)<=0));
!Ensure that the assignment variable is binary;
@FOR(suppliers(i):@FOR(objects(j):@BIN(x(i,j))));
data:
@OLE('LINGO_input.xlsx',output[assigned])=x;
@OLE('LINGO_input.xlsx',objective_function_value)=total_cost;
@OLE('LINGO_input.xlsx',supplier_cost)=supplier_cost;
enddata
结果
下图是 Or-Tools 和 LINGO 的对比结果。我强调两个实现使用的数据完全相同，我检查了所有数据几次。
请注意，两种实现之间存在 1.876,20 的差异。使用分支定界算法的 LINGO 找到了比 Or-Tools 更好的解决方案。差异是由如下所示的分配不一致引起的。
关于算法的处理时间，LINGO 大约需要 14 分钟，而 Or-Tools 不到 1 分钟。
两个实现中使用的所有数据都在这个存储库中：https ://github.com/hrassis/divisao-mercado 。LINGO 使用的数据在文件夹 input_lingo 中，而 Or-Tools 使用的数据在文件夹 input_prototype 中。另外我上传了验证报告。