我有一个 Python 脚本（Pulp 库），用于根据客户当前的资金水平（缺口/需求）及其在优先组中的成员身份在多个客户之间分配资金。但是，我没有收到预期的结果。 特别是，我想要：
我试过这个：
"""
MULTI-OBJECTIVE LINEAR OPTIMIZATION PROBLEM
(FG-01-2023)
---PROBLEM DESCRIPTION
#n Projects, each with its own Requirements (expressed in USD), Gap (expressed in USD) and Allocation (in USD).
Allocation represents the amount of extra resources (in USD) each project is going receiving as part of the exercise.
Initial value for Project(i) Allocation = 0
For each project we define
Project(i) GAP% = (Gap - Allocation)/Requirements
Projects are grouped by Priority (Prioritization Group) based on Vulnerability criteria (Group A is higher priority,
followed by B, C, and so on).
We are projecting to receive some additional funding, which we want to distribute among projects.
Project(i) Allocation += Portion of additional funding allocated to Project(i)
---OBJECTIVES
Allocate the entire additional funding:
- Minimize the portion of Additional Funding which is not allocated to Projects --> ideally reduce to 0
Reduce the maximum GAP% within each priority group
- Minimize the Maximum GAP% within each priority group --> Ideally, if there are sufficient funds, reduce all GAP% to 0
---CONSTRAINTS
Allocations to individual projects must be: 1) non-negative, and 2) not greater than the Project's initial Gap.
Sum of allocations to individual projects cannot be greater than the total additional funding
Allocations to Projects should not cause Max GAP% of a lower priority group to become lower than Max GAP% of a higher
priority group
---IMPLEMENTATION NOTES
This script tries to use Python's PuLP library to implement the optimization model.
Documentation: https://coin-or.github.io/pulp/
PuLP can use a variety of "solvers". The script start with the default one (CBC MILP).
A better approach may be to use a different optimization library that better supports multi-objective:
- pulp-or: Operations Research, provides --> pulp.generate_pareto_front() function
- DEAP: Distributed Evolutionary Algorithms
- PyGMO: Python Parallel Global Multiobjective Optimizer --> non_dominated_front_mo() function
- nsga2: Non-dominated Sorting Genetic Algorithm 2 --> nsga2.nsga2() function
---VERSIONS
Python 3.10
PuLP 2.7.0
---INSTRUCTIONS
The Script asks the user to import data from an input Excel file with four columns:
- Project Name
- Group
- Requirements
- GAP
It also asks for the AMOUNT to be allocated
The result can be output to console and/or exported to an Excel file named "optimization_results_(AMOUNT)_TIMESTAMP"
---OUTSTANDIG IMPLEMENTATION PROBLEMS
- The problem is reduced to a single-objective one by working on a linear combination of the two objective functions
- If clients with a GAP but no requirements ar not excluded (parameter-controlled) the model doesn't work correctly
- delta_gap is an externally imposed parameter (forces some distance between max % GAP of two consecutive prioritization
groups)
"""
"""
PACKAGES
"""
import pulp
from pulp import LpVariable, LpAffineExpression
import pandas as pd
import PySimpleGUI as sg
import datetime
import openpyxl
"""
CONFIGURATION PARAMETERS
"""
delta_gap = 1.1
"""
FUNCTIONS
"""
def select_input_file():
# Select the input file to upload
# Create a file selection dialog
layout = [[sg.Text('Select a file:')],
[sg.Input(), sg.FileBrowse()],
[sg.Checkbox('Print output to console')],
[sg.Checkbox('Save output to Excel file', default=True)],
[sg.Checkbox('Do not allocate funding to clients with 0 Requirements', default=True)],
[sg.Button('OK'), sg.Button('Cancel')]]
# Create the window
window = sg.Window('File Selection Dialog', layout)
event, values = window.read()
# Close the window
window.close()
# Get the selected file path from the values dictionary
input_file = values[0]
print_to_console = values[1]
print_to_excel = values[2]
skip_zero_requirements = values[3]
return input_file, print_to_console, print_to_excel, skip_zero_requirements
def get_additional_funding():
# Let the user indicate the amount of additional funding to be allocated
# Create a data entry dialog
layout = [[sg.Text('Enter the expected funding amount:')],
[sg.InputText(key='input')],
[sg.Button('OK'), sg.Button('Cancel')]]
# Create the window
window = sg.Window('Expected Funding', layout)
event, values = window.read()
# Close the window
window.close()
# Get the selected file path from the values dictionary
input_value = values['input']
return (input_value)
def print_to_console(output):
for line in output:
print(line)
# # Print the Problem representation in PuLP
# print('Problem Statements')
# print(lp_prob)
#
#
# # Print the Optimization Results
# print("Status:", pulp.LpStatus[lp_prob.status])
# print("Objective value:", pulp.value(lp_prob.objective))
#
# # Print the headings of the output table
# print("Project Name\tPriority Group\tRequirements\tInitial Gap\tInitial Gap %\tAllocation\tNew Gap\tNew Gap %")
# total_allocation = 0
# for i in range(n):
# # Calculate the new gap and the new gap percentage
# new_gap = gap[i] - allocation[project_names[i]].value()
# if requirements[i] == 0:
# new_gap_percentage = 0
# else:
# new_gap_percentage = new_gap / requirements[i]
#
# # Print project data on one line
# print(f"{project_names[i]}\t{priority[i]}\t{requirements[i]:>10}\t{gap[i]:>10}\t{gap_percentage[i]:>10.2f}\t{allocation[project_names[i]].value():>10}\t{new_gap:>10}\t{new_gap_percentage:>10.2f}")
# total_allocation += allocation[project_names[i]].value()
#
# print('total allocation: ' + str(total_allocation))
# #print('Final Value of the Group Decision Variables')
# #for group in priority_groups:
# # print(max_gap_percentage[group] + " - " + max_gap_percentage[group].value())
def print_to_excel(output):
# get current date and time
now = datetime.datetime.now()
# Format the date and time as a string
timestamp = now.strftime('%Y-%m-%d_%H-%M-%S')
# Create the filename with the timestamp
filename = f'optimization_results_({additional_funding})_{timestamp}.xlsx'
# Create a list of dictionaries, each containing the data for one project
project_data = []
for i in range(n):
# Calculate the new gap and the new gap percentage
new_gap = gap[i] - allocation[project_names[i]].value()
if requirements[i] == 0:
new_gap_percentage = 0
else:
new_gap_percentage = new_gap / requirements[i]
# Create a dictionary for the project data
data = {
'Project Name': project_names[i],
'Priority Group': priority[i],
'Requirements': requirements[i],
'Initial Gap': gap[i],
'Initial Gap %': gap_percentage[i],
'Allocation': allocation[project_names[i]].value(),
'New Gap': new_gap,
'New Gap %': new_gap_percentage
}
project_data.append(data)
# Create a DataFrame from the project data
df = pd.DataFrame(project_data)
# Create an ExcelWriter object
writer = pd.ExcelWriter(filename)
# Write the DataFrame to the Excel file
df.to_excel(writer, index=False)
# Get the worksheet object
worksheet = writer.sheets['Sheet1']
# Rename the worksheet to "Optimization Results"
worksheet.title = "Optimization Results"
# Hide the gridlines
worksheet.gridlines = False
# Set the header row height
worksheet.row_dimensions[1].height = 20
# Freeze the header row
worksheet.freeze_panes = 'A2'
# Make the top row bold
for cell in worksheet[1]:
cell.font = openpyxl.styles.Font(bold=True)
# Set the column widths for all columns
worksheet.column_dimensions['A'].width = 20 # Project
worksheet.column_dimensions['B'].width = 20 # Priority
worksheet.column_dimensions['C'].width = 20 # Requirements USD
worksheet.column_dimensions['D'].width = 20 # Ininitial Gap USD
worksheet.column_dimensions['E'].width = 20 # Initial Gap %
worksheet.column_dimensions['F'].width = 20 # Allocation USD
worksheet.column_dimensions['G'].width = 20 # New Gap USD
worksheet.column_dimensions['H'].width = 20 # New Gap %
# Get the number of rows in the worksheet
num_rows = worksheet.max_row
# Iterate over all the rows in the "Initial Gap" column
for row in range(2, num_rows + 1):
# Set the number format for the cell in colu,ns C, D, F, and G
worksheet[f'C{row}'].number_format = '#,##0'
worksheet[f'D{row}'].number_format = '#,##0'
worksheet[f'F{row}'].number_format = '#,##0'
worksheet[f'G{row}'].number_format = '#,##0'
# Set the number format for the cell in column E and H
worksheet[f'E{row}'].number_format = '0.00%'
worksheet[f'H{row}'].number_format = '0.00%'
# Set the filters on the header row
worksheet.auto_filter.ref = "A1:H1"
# Get the workbook object
workbook = writer.book
# Create a new worksheet
worksheet2 = workbook.create_sheet("Execution Log")
row = 1
# Iterate over the elements of the output list
for element in output:
# Check if the element is a PuLP object
if isinstance(element, pulp.LpProblem):
# Get the string representation of the object
string = str(element)
# Split the string into lines
lines = string.split('\n')
# Iterate over the lines
for line in lines:
# Write the line to the worksheet
cell = openpyxl.cell.Cell(worksheet2, value=line)
worksheet2.append([cell])
else:
# Write the element to the worksheet as-is
cell = openpyxl.cell.Cell(worksheet2, value=element)
# Write the cell to the worksheet, starting at cell A1
worksheet2.append([cell])
# Increment the row number
row += 1
# Save the changes
writer.save()
def generate_execution_log():
# Create a list to store the output lines
output = []
# Add the Problem representation in PuLP to the output
output.append('Problem Statements')
output.append(lp_prob)
# Add the Optimization Results to the output
output.append("Status:")
output.append(pulp.LpStatus[lp_prob.status])
output.append("Objective value:")
output.append(pulp.value(lp_prob.objective))
# output.append('Final Value of the Group Decision Variables')
# for group in priority_groups:
# output.append(max_gap_percentage[group] + " - " + max_gap_percentage[group].value())
# Return the output
return output
"""
DATA PREPARATION
"""
# Get full path of Excel input file, and output choices
filepath, output_to_console, output_to_excel, skip_zero_requirements = select_input_file()
# Read the Excel file into a Pandas dataframe
df = pd.read_excel(filepath)
# source = print(filepath[(len(filepath)-15): (len(filepath)-5)])
# Get amount of additional funding
additional_funding = int(get_additional_funding())
# Extract the values from the dataframe and store them in list variables
# Number of projects# Number of projects
n = len(df)
# Names of projects
project_names = df['Project'].tolist()
# Requirements, gap, and allocation for each project
requirements = df['Requirements'].tolist()
gap = df['Gap'].tolist()
allocation = [0] * n
# Priority group for each project
priority = df['Group'].tolist()
# Calculate the gap percentage for each project
gap_percentage = []
for i in range(n):
if requirements[i] == 0:
gap_percentage.append(0)
else:
gap_percentage.append((gap[i] - allocation[i]) / requirements[i])
# Create a dictionary and associate a list of project indices to each priority group
unsorted_priority_groups = {}
for k, p in enumerate(priority):
if p not in unsorted_priority_groups:
unsorted_priority_groups[p] = []
unsorted_priority_groups[p].append(k)
# Create a sorted version of the dictionary
priority_groups = {j: v for j, v in sorted(unsorted_priority_groups.items(), key=lambda item: item[0])}
"""
DECISION VARIABLES
"""
# Create a continuous Decision Variable and Affine Expression for the amount of additional funding received by each
# project
allocation = {}
allocation_expr = LpAffineExpression()
for z in range(n):
if priority[z] == 'X' or (requirements[z] == 0 and skip_zero_requirements):
# Projects in Priority Group 'X' don't get any allocation
allocation[project_names[z]] = pulp.LpVariable(f'allocation_{project_names[z]}', lowBound=0, upBound=0)
else:
# allocation is non negative and cannot be greater than the initial gap
allocation[project_names[z]] = pulp.LpVariable(f'allocation_{project_names[z]}', lowBound=0, upBound=(gap[z]*0.9))
allocation_expr += allocation[project_names[z]]
# Create a continuous Decision Variable and Affine Expression for the maximum GAP% within each priority group
#target_group_A = {}
target_group_A_expr = LpAffineExpression()
target_group_A = pulp.LpVariable(f'allocation', lowBound=0 )
target_group_A_expr += target_group_A
#project_gap_perc = {}
#project_gap_perc_expr = LpAffineExpression()
#for z in range(n):
# if priority[z] == 'X' or (requirements[z] == 0 and skip_zero_requirements):
# # Projects in Priority Group 'X' don't get any allocation
# project_gap_perc[project_names[z]] = pulp.LpVariable(f'project_gap_perc_{project_names[z]}', lowBound=0, upBound=0)
# else:
# # allocation is non negative and cannot be greater than the initial gap
# project_gap_perc[project_names[z]] = pulp.LpVariable(f'project_gap_perc{project_names[z]}', lowBound=0, upBound=gap[z]/requirements[z])
# project_gap_perc_expr += project_gap_perc[project_names[z]]
"""
LINEAR PROGRAMMING PROBLEM
"""
# Create the linear programming problem object
lp_prob = pulp.LpProblem('Multi-Objective Optimization', pulp.LpMaximize)
"""
OBJECTIVE FUNCTIONS
"""
# Define the objective function as an LpAffineExpression
obj = LpAffineExpression()
# MAXIMIZE the portion of additional funding allocated to projects
obj += allocation_expr
# MINIMIZE the Max GAP% within each group [actually Maximizing the -(Max GAP%)]
obj += -target_group_A_expr
# MINIMIZE the Max GAP% within each group [actually Maximizing the -(Max GAP%)]
#obj += -project_gap_perc_expr
# Set the Objective Function
lp_prob += obj
"""
CONSTRAINTS
"""
# Additional funding allocations to individual projects must be non-negative and not greater than the project's gap
#for v in range(n):
# lp_prob += allocation[project_names[v]] <= gap[v]
# lp_prob += allocation[project_names[v]] >= 0
# The sum of allocations to individual projects cannot be greater than the additional funding
lp_prob += pulp.lpSum([allocation[project_names[u]] for u in range(n)]) <= additional_funding
# The Max GAP % within each group >= of the GAP % of all projects in the group (proxy for dynamic max calculation)
for i, (p, group) in enumerate(priority_groups.items()):
# Get the indices of the projects in the group
group_indices = priority_groups[p] #selects the indices matching with the rows of the projects belonging to that group
# Iterate over the indices of the projects in the group
for index in group:
# Create an LpAffineExpression for the GAP% of the project
project_gap_percentage = LpAffineExpression()
if requirements[index] == 0:
project_gap_percentage += 0
else:
project_gap_percentage += (gap[index] - allocation[project_names[index]]) / requirements[index]
# Add constraint to the model
lp_prob += target_group_A == (project_gap_percentage/pow(delta_gap, i))
#for i, (p, group) in enumerate(priority_groups.items()):
# group_indices = priority_groups[p]
# for index in group[1: len(group)]:
# # Create an LpAffineExpression for the GAP% of the project
# project_gap_percentage = LpAffineExpression()
# if requirements[index] == 0:
# project_gap_percentage += 0
# else:
# project_gap_percentage += (gap[index-1] - allocation[project_names[index-1]]) / requirements[index-1]
# project_gap_percentage += (gap[index] - allocation[project_names[index]]) / requirements[index]
# # Add constraint to the model
# lp_prob += project_gap_perc[index] == project_gap_perc[index-1]
## The Max GAP % of a lower priority group should not be lower than Max GAP % of higher priority groups
#for i, (p, group) in enumerate(priority_groups.items()):
# if i == 0:
# # Skip the first group (group A)
# #lp_prob+=max_gap_percentage[p]== 0.70
# continue
# # Get the parameter for the current group (p) and the immediately preceding group (prev_p)
# prev_p = list(priority_groups.keys())[i - 1]
# lp_prob += max_gap_percentage[p] >= max_gap_percentage[prev_p] * delta_gap
"""
PROGRAMMING MODEL SOLVER
"""
# Solve the linear programming problem
lp_prob.solve()
"""
OPUTPUT
"""
execution_log = generate_execution_log()
if output_to_console:
print_to_console(execution_log)
if output_to_excel:
print_to_excel(execution_log)
import sys
sys.modules[__name__].__dict__.clear()
delta_gap 和 additional_funding 是外部参数。 我什至收到负分配并且约束并不总是满足，例如在 B 组中，C I 达到的资金缺口水平远低于 A 组的水平——有时它们显然随机地变为零。这怎么可能？
我正在尝试增加 5、2.6 和 10 亿的预算。
我正在考虑使用另一个库，有什么建议吗？
这是一个我认为可能对你有帮助的想法。我收集了一些我认为代表问题的示例数据。我不确定如何获取您的实际数据。根据您处理不同案例的方式，您可能会探索这方面的几个变体。这会尝试使用您定义的比率降低整个“差距上限”。其副产品之一是，如果优先级较低的项目存在很大差距，但“A”（高优先级项目）的差距很小，那么次要项目将获得资金以缩小比例。
您应该尝试按照评论中建议的
total_fundsimport pulp
from itertools import chain
from collections import defaultdict
# DATA
# below could be from dataframe or whatever....
# Group : Project : (current funds, requirement)
data = { 'A' : { 'z19': (50, 100),
'x40': (60, 100)},
'B' : { 'r55': (80, 84),
'm21': (100, 200),
'm22': (100, 300)},
'C' : { 'k15': (40, 400), # fully funded
'p88': (10, 20)}}
# some housekeeping to prep data...
groups = list(data.keys())
projects = []
projects_by_group = defaultdict(list)
reqts = {}
funds = {}
for grp in groups:
for project, (fund, req) in data[grp].items():
projects.append(project)
projects_by_group[grp].append(project)
reqts[project] = req
funds[project] = fund
# make some group multipliers as a convenience...
multipliers = {grp: 1.1**groups.index(grp) for grp in groups}
tot_funds = 200 # 100, 1000 ...
# LP PROBLEM
prob = pulp.LpProblem('allocation', pulp.LpMinimize)
# VARIABLES
gap_cieling_group = pulp.LpVariable.dicts('max_gap', groups)
add_funds = pulp.LpVariable.dicts('add_funds', projects, lowBound=0)
# OBJECTIVE: Minimize the "gap cieling" across all projects by minimizing A's cieling
prob += gap_cieling_group['A']
# CONSTRAINTS:
prob += pulp.lpSum(add_funds[project] for project in projects) <= tot_funds
for project in projects:
prob += add_funds[project] + funds[project] <= reqts[project]
for grp in groups:
for project in projects_by_group[grp]:
prob += gap_cieling_group[grp] >= (reqts[project] - add_funds[project] - funds[project])/reqts[project]
lesser_groups = groups[:]
lesser_groups.remove('A')
for grp in lesser_groups:
prob += gap_cieling_group[grp] == gap_cieling_group['A'] * multipliers[grp]
results = prob.solve()
for grp in groups:
print(f'{grp} gap_cieling: {gap_cieling_group[grp].value() : 0.2f} (actual: {max((reqts[project] - add_funds[project].value() - funds[project])/reqts[project] for project in projects_by_group[grp]) : 0.2f})')
for project in projects:
print(f'{project} + {add_funds[project].value() : 0.2f}')
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
command line - /Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/pulp/solverdir/cbc/osx/64/cbc /var/folders/rt/5gc2md7s7y5bw8ddt74tz5vw0000gp/T/fb4693e8b5194de2bd2fb0219286c2be-pulp.mps timeMode elapsed branch printingOptions all solution /var/folders/rt/5gc2md7s7y5bw8ddt74tz5vw0000gp/T/fb4693e8b5194de2bd2fb0219286c2be-pulp.sol (default strategy 1)
At line 2 NAME MODEL
At line 3 ROWS
At line 22 COLUMNS
At line 56 RHS
At line 74 BOUNDS
At line 78 ENDATA
Problem MODEL has 17 rows, 10 columns and 32 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 8 (-9) rows, 8 (-2) columns and 21 (-11) elements
Perturbing problem by 0.001% of 0.028415538 - largest nonzero change 7.9768843e-05 ( 0.28072262%) - largest zero change 4.2399677e-05
0 Obj 0.24862989 Primal inf 108.57674 (7)
6 Obj 0.45370575
Optimal - objective value 0.44973545
After Postsolve, objective 0.44973545, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 0.4497354497 - 6 iterations time 0.002, Presolve 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
A gap_cieling: 0.45 (actual: 0.45)
B gap_cieling: 0.49 (actual: 0.49)
C gap_cieling: 0.54 (actual: 0.54)
z19 + 5.03
x40 + 0.00
r55 + 0.00
m21 + 1.06
m22 + 51.59
k15 + 142.33
p88 + 0.00
[Finished in 93ms]