Fund Allocation with constraints

user_14331660 0
Viewed 178

I am trying to solve a problem to determine the government grant allocation with various constraints. The problem is best described as:

Government has decided to issue financial help of total 1,800,000. They have invited the applications for the same. They have decided on some constraints on how they want to allocate the fund. The constraints are:

  1. Maximum limit on amount that can be allocated as per financial status of the applicant.

    Rich = 300,000

    Middle class = 500,000

    Poor = 1,000,000

  2. Maximum limit on amount that can be allocated as per gender of the applicant.

    Male = 800,000

    Female = 1,000,000

They received the applications with different mix. Government cannot allocate more money that the application received.

+--------------------+------------------+-----------------------------+------------------------+
| Applicant Category | Applicant Gender | Total Applications Received | Amount to be allocated |
+--------------------+------------------+-----------------------------+------------------------+
| Rich               | Male             | 200,000                     |                        |
| Middle class       | Female           | 400,000                     |                        |
| Middle class       | Male             | 350,000                     |                        |
| Poor               | Female           | 650,000                     |                        |
| Poor               | Male             | 750,000                     |                        |
+--------------------+------------------+-----------------------------+------------------------+

In above example, total amount of applications by Rich Male is 200,000. So government cannot allocate more than 200,000 against such category. Government can allocate less than that if that helps increase the total disbursed amount across all these rows.

Middle-class males have requested for total 400,000 and middle-class female have requested for 350,000. However total money that can be disbursed among middle-class category 500,000. Which means it cannot fully allocate to these buckets and has to settle for less.

Middle-class female have requested 400,000 and poor female have requested 650,000. However total money that can be disbursed among all female is 1,000,000 which means these two buckets cannot be fully allocated too.

"Amount to be allocated" column in the above table is what algorithm has to determine. Something like - what is the maximum amount that can be assigned to each entries in the table that would allow us to disburse maximum amount in total, that does not violate any of the constraints and "Amount to be allocated" amount should not be more than "Total Applications Received"?

For example, if let's say we allocate 700,000 to poor male entry then it needs to be debited from male and poor categories both. After allocating 700,000 to poor-male, remaining amount for male becomes 100,000 (800,00-700,000) and poor becomes 300,000 (1,000,000-700,000). Subsequent allocation to other entries now has to take modified constraints into account and ensure the limits are not breached.

The aim is to determine the amount that government can allocate to each combinations of the category and gender to maximize the total amount disbursed.

I am bit new to linear programming however reading through the online help, I could determine the constraints I can put on each category individually.

x (rich) <= 300,000
y (middle class) <= 500,000
z (poor) <= 1,000,000
p (male) <= 800,000
q (female) <= 1,000,000

However I am not able to formulate the restrictions on the applications received by the government. For example, 200,000 applications received by rich male does not translate into (x + p) <= 200,000

pulp linear-programming python
2 Answers

We can formulate the above problem in the form of linear equation as follows:

Let Rm = Rich Male
    Rm = Rich Female 
    Mm = Middleclass Male
    Mf = Middleclass Female
    Pm = Poor Male
    Pf = Poor Female

Objective: Maximize: Rm + Rf + Mm + Mf + Pm + Pf

Subject to:

1) Rm + Rf <= 300,000
2) Mm + Mf <= 500,000
3) Pm + Pf <= 1,000,000

4) Rm + Mm + Pm <= 800,000
5) Rf + Mf + Pf <= 1,000,000

6) Rm <= 200,000
7) Mm <= 350,000
8) Pm <= 750,000
9) Rf <= 0
10) Mf <= 400,000
11) Pf <= 650,000

The constraints 6-11 can be changed depending on the input data.
Solving this we get:

Rm = 200,000
Mm = 250,000
Pm = 350,000
Rf = 0
Mf = 250,000
Pf = 650,000

So a total of 1,70,000 can be disbursed among the applicants according to the given data

user_95458980

Code:

from pulp import *
import pandas as pd

# Problem Data

df = pd.DataFrame({'economic': ['rich', 'middle', 'middle', 'poor', 'poor'],
                   'gender': ['male', 'female', 'male', 'female', 'male'],
                   'received': [200000, 400000, 350000, 650000, 750000]})

max_by_economic = {'rich': 300000, 'middle':500000, 'poor':1000000}
max_by_gender = {'male': 800000, 'female':500000, 'poor':1000000}
max_total = 1800000

# Implementation
prob = LpProblem("allocation", LpMaximize)

alloc_vars = LpVariable.dicts('alloc_vars', df.index)

# Objective
prob += lpSum([alloc_vars[i] for i in df.index])

# Bounds
for i in df.index:
    prob += alloc_vars[i] <= df.received[i]


# Constraints
for status in max_by_economic:
    prob += lpSum([alloc_vars[i] for i in df.index if df['economic'][i] == status]) <= max_by_economic[status]

for gender in max_by_gender:
    prob += lpSum([alloc_vars[i] for i in df.index if df['gender'][i] == gender]) <= max_by_gender


prob += lpSum([alloc_vars[i] for i in df.index]) <= max_total


prob.solve()

# Load results into dataframe                  
df['allocation'] = [alloc_vars[i].varValue for i in df.index]
print(df)

Returns:

  economic  gender  received  allocation
0     rich    male    200000    200000.0
1   middle  female    400000    150000.0
2   middle    male    350000    350000.0
3     poor  female    650000    250000.0
4     poor    male    750000    750000.0
user_49886010
Related