这个PulP分配优化问题为什么不能按预期工作?

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

Why does this PulP allocation optimization problem doenst work as expected?

问题

The code you've provided appears to be related to linear programming and optimization, specifically using the PuLP library in Python. Your goal is to allocate employees to appointments in a way that minimizes the number of employees assigned to appointments. You're facing an issue where the optimization is not producing the desired results.

Without going into the specific code implementation, it's important to note that your objective function seems to be based on the total number of appointments assigned to employees, which may not align with your desired outcome. If you want to minimize the number of employees assigned to appointments, you might need to reformulate your objective function.

Instead of using prob += lpSum(empl_appo_count[emp] for emp in employee_dict), you should consider formulating an objective function that minimizes the number of employees assigned to appointments. This would involve modifying the coefficients and constraints in your linear programming model.

It's a complex optimization problem, and the solution may require adjustments to the constraints and objective function based on your specific requirements. You may also want to consider different optimization algorithms or approaches if the linear programming approach doesn't yield the desired results.

If you need further assistance with the code or specific adjustments to your linear programming model, please provide more details about your constraints and objectives, and I can try to offer more guidance.

英文:

i'm developing a Python Programm to allocate employees to different appointments.
I'm trying to reach an allocation, where most of employees are not allocatet to appointments. Only if nessesary (because there are more appointments at one timeslot) more employees should work on the the appointments.
My Programm looks like that:

    prob = LpProblem("equally_employee_allocation",LpMinimize)

    #Dictionary mit Mitarbeitern, solange diese nicht im Urlaub sind. (inkl allen weiteren Informationen)
    employee_dict = get_employees(date)
    employee_count = len(employee_dict)

    #Dict aller Slots und wie viele Terminen zu diesem Zeitslot bearbeitet werden müssen
    slot_appo_dict = get_slot_appo_dict(date)

    #Binärvariablen, welche angeben, ob ein Mitarbeiter einem Termin zugeteilt wurde, oder nicht.
    empl_appo_bin = LpVariable.dicts("employ_appoi_bin", (slot_appo_dict, employee_dict),cat=LpBinary)

    #Variable, welche die Anzahl der Termine des jeweiligen Mitarbeiters angibt
    empl_appo_count= LpVariable.dicts("employ_appoi_count", employee_dict, cat=LpInteger, lowBound= 0)



    ##### Zielfunktion #####
    prob+=lpSum(empl_appo_count[emp] for emp in employee_dict)

    ##### Nebenbedingungen #####


    #Die Anzahl der aufgeteilten Mitarbeiter auf einen Slot muss der denen der gebuchten Termine entsprechen:
    for slot in slot_appo_dict:
        prob += lpSum(empl_appo_bin[slot][e] for e in employee_dict) == slot_appo_dict[slot]

    for empl in employee_dict:
        # Die Anzahl der zugewiesenen Termine von Mitarbeiter M:
        prob += empl_appo_count[empl] == lpSum(empl_appo_bin[slot][empl] for slot in slot_appo_dict)

        #elastic Constraint: Abweichung von der durchschnittlichen Anzahl der bearbeiteten Termine wird bestraft
        flex_constraint1 = LpConstraint(e=empl_appo_count[empl], name=f"equal_allocation{empl}", sense=LpConstraintEQ, rhs= 1)
        prob.extend(flex_constraint1.makeElasticSubProblem(penalty=1, proportionFreeBound=0))




    prob.writeLP("data/low_allocation.lp")
    prob.solve()

I think this lines does'nt do what i want:

        #elastic Constraint: Abweichung von der durchschnittlichen Anzahl der bearbeiteten Termine wird bestraft
        flex_constraint1 = LpConstraint(e=empl_appo_count[empl], name=f"equal_allocation{empl}", sense=LpConstraintEQ, rhs= 0)
        prob.extend(flex_constraint1.makeElasticSubProblem(penalty=1, proportionFreeBound=0))

The result with 4 Employees and 12 Appointments (all at different times) should be, that only one Employee works on every Appointment.

But instead of that it Allocates:
Empl 1 - 2 Appointments
Empl 2 - 9 Appointments
Empl 3 - 1 Appointments
Empl 4 - 0 Appointments

Objective Value is 24

What am i doing wrong? Or Maybe you have an idea, how to formulate the problem in a better way?

I hope, you can Help!
Thank you!

I tried changing sense, penalty, proportionFreeBound and rhs in different ways... Only thing i reached was an unbounded problem, althoug the lower bound is 0.

Example
There are 12 Appointments. Employee 1 should get all of the apointments (12). Only if there are more than one appointments at the same time, employee 2 should get the second one (empl 3 the 3rd and so on...) After that, Employee 1 should get the rest.

答案1

得分: 0

以下是已翻译的代码部分:

要做到这一点的概念是使用指示变量,指示员工在所讨论的日期是否有任何任务。为了使其工作,您需要引入一个“大M”约束(Google它)。基本上,您可以将二进制指示变量与适当大的数字相乘,以使新添加的约束中的逻辑有效。

您的代码中有一些不必要的额外内容,我已将它们注释掉。

#### 代码:

    from pulp import *
    
    prob = LpProblem("equally_employee_allocation", LpMinimize)
    
    # 员工字典,只要员工不在休假中(包括所有其他信息)
    employee_list = ['Bob', 'Sam', 'Hans', 'Gertrude']
    employee_count = len(employee_list)
    
    # 所有时间段和需要处理的约会数的字典
    #               时间段:约会数
    slot_appo_dict = {	1: 1,
    					2: 1,
    					3: 3,
    					4: 2,
    					5: 2,
    					6: 1}
    
    M = len(slot_appo_dict.keys())  # 每个员工可能的分配最大数量(每个时间段)
    
    # 二进制指示变量,指示员工是否分配给了某个约会
    empl_appo_bin = LpVariable.dicts("employ_appoi_bin", (slot_appo_dict, employee_list), cat=LpBinary)
    
    # 下面的部分是不需要的
    # 每个员工的约会数量变量
    # empl_appo_count = LpVariable.dicts("employ_appoi_count", employee_list, cat=LpInteger, lowBound=0)
    
    # 表示员工是否工作的“指示”变量,为1表示员工工作,为0表示否
    employee_works = LpVariable.dicts("works", employee_list, cat=LpBinary)
    
    ##### 目标函数 #####
    # 最小化工作的员工数量
    prob += sum(employee_works[e] for e in employee_list)
    
    ##### 约束条件 #####
    
    # 每个时间段的分配员工数量必须等于约会数:
    for slot in slot_appo_dict:
    	prob += lpSum(empl_appo_bin[slot][e] for e in employee_list) == slot_appo_dict[slot]
    
    for empl in employee_list:
    	# 不需要的部分
    	# 员工的约会数量等于分配给他们的时间段数
    	# prob += empl_appo_count[empl] == lpSum(empl_appo_bin[slot][empl] for slot in slot_appo_dict)
    
    	prob += sum(empl_appo_bin[slot][empl] for slot in slot_appo_dict) <= M * employee_works[empl]
    
    	# 我不确定您在这里尝试做什么,但不需要:
    	# #弹性约束:与平均约会数量的偏差会受到惩罚
    	# flex_constraint1 = LpConstraint(e=empl_appo_count[empl], name=f"equal_allocation{empl}", sense=LpConstraintEQ, rhs=1)
    	# prob.extend(flex_constraint1.makeElasticSubProblem(penalty=1, proportionFreeBound=0))
    
    	
    res = prob.solve()
    
    for slot in slot_appo_dict:
    	for employee in employee_list:
    		if empl_appo_bin[slot][employee].varValue:  # 如果varValue == 1,则为真...
    			print(f'员工 {employee} 被分配到时间段 {slot}')

这是您提供的代码的翻译版本。

英文:

The concept that will help you do this is the use of an indicator variable that indicates whether an employee has any assignments on the day in question. In order to make that work, you need to introduce a "big M" constraint (google it). Basically you can multiply the binary indicator variable by a suitably large number to make the logic work in the new constraint I added.

There were a few extra things in your code that were not needed, so I commented them out.

Code:

from pulp import *

prob = LpProblem(&quot;equally_employee_allocation&quot;,LpMinimize)

#Dictionary mit Mitarbeitern, solange diese nicht im Urlaub sind. (inkl allen weiteren Informationen)
employee_list = [&#39;Bob&#39;, &#39;Sam&#39;, &#39;Hans&#39;, &#39;Gertrude&#39;]
employee_count = len(employee_list)

#Dict aller Slots und wie viele Terminen zu diesem Zeitslot bearbeitet werden m&#252;ssen
#               slot : appts
slot_appo_dict = {	1: 1,
					2: 1,
					3: 3,
					4: 2,
					5: 2,
					6: 1}

M = len(slot_appo_dict.keys())  # the max number of possible assignments per employee (every slot)

#Bin&#228;rvariablen, welche angeben, ob ein Mitarbeiter einem Termin zugeteilt wurde, oder nicht.
empl_appo_bin = LpVariable.dicts(&quot;employ_appoi_bin&quot;, (slot_appo_dict, employee_list),cat=LpBinary)

# this below is NOT needed
#Variable, welche die Anzahl der Termine des jeweiligen Mitarbeiters angibt
# empl_appo_count= LpVariable.dicts(&quot;employ_appoi_count&quot;, employee_list, cat=LpInteger, lowBound= 0)

# an &quot;indicator&quot; variable that is 1 if employee works *any* shift and 0 otherwise
employee_works = LpVariable.dicts(&quot;works&quot;, employee_list, cat=LpBinary)

##### Zielfunktion #####
# minimize the number of employees who are working:
prob+= sum(employee_works[e] for e in employee_list)

##### Nebenbedingungen #####


#Die Anzahl der aufgeteilten Mitarbeiter auf einen Slot muss der denen der gebuchten Termine entsprechen:
for slot in slot_appo_dict:
	prob += lpSum(empl_appo_bin[slot][e] for e in employee_list) == slot_appo_dict[slot]

for empl in employee_list:
	# not needed
	# Die Anzahl der zugewiesenen Termine von Mitarbeiter M:
	# prob += empl_appo_count[empl] == lpSum(empl_appo_bin[slot][empl] for slot in slot_appo_dict)

	prob += sum(empl_appo_bin[slot][empl] for slot in slot_appo_dict) &lt;= M * employee_works[empl]

	# I&#39;m not sure what you are trying to do here, but it is not needed:
	# #elastic Constraint: Abweichung von der durchschnittlichen Anzahl der bearbeiteten Termine wird bestraft
	# flex_constraint1 = LpConstraint(e=empl_appo_count[empl], name=f&quot;equal_allocation{empl}&quot;, sense=LpConstraintEQ, rhs= 1)
	# prob.extend(flex_constraint1.makeElasticSubProblem(penalty=1, proportionFreeBound=0))

	
res = prob.solve()

for slot in slot_appo_dict:
	for employee in employee_list:
		if empl_appo_bin[slot][employee].varValue:  # will be true if varValue == 1...
			print(f&#39;employee {employee} is assigned to slot {slot}&#39;)

Output:

Result - Optimal solution found

Objective value:                3.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.01
Time (Wallclock seconds):       0.01

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.01

employee Bob is assigned to slot 1
employee Sam is assigned to slot 2
employee Bob is assigned to slot 3
employee Sam is assigned to slot 3
employee Hans is assigned to slot 3
employee Bob is assigned to slot 4
employee Sam is assigned to slot 4
employee Bob is assigned to slot 5
employee Sam is assigned to slot 5
employee Bob is assigned to slot 6

huangapple
  • 本文由 发表于 2023年6月12日 21:48:07
  • 转载请务必保留本文链接:https://go.coder-hub.com/76457316.html
匿名

发表评论

匿名网友

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

确定