Formulating an Linear Programming Assignment in pulp

Question

So, here's the context of what I am trying to solve:

I want to divide cost units into two or more companies. Now, I have it solved for two companies with the following objective function:

20*x1 + 30*x2 + 100*x3 + 20*x4 + 30*x5

with the variables being Binary type.

Suppose I get the optimized solution as:

x1 = 1
x2 = 0
x3 = 0
x4 = 1
x5 = 0

this means that Company A would be responsible for unit costs x1 and x4 and Company B with the rest of the costs.

This is working fine, and I have all coded on pulp correctly. I can also use constraints to limit the maximum cost for a particular company, which is the point of all this to begin with. The coefficients's sum represent the total cost of a given project. So I use that amount as constraint to the objective function to limit the cost of Company A

Now, what I want to do is the same thing with 3 or more companies. I have no idea how to formulate the objective function or functions, as I think that it might fall into a multi objective function problem, but I'm actually not sure.

I am not very experienced in Linear Programming, so I'm sorry if I have misplaced the question. I haven't found anything that could help me accomplish this.

I would put the code, but I have way more variables and some basic data preparation before creating the function, so I created a hypothetical example to make it easier to understand.

Thanks very much for any help.

It's very broad. But if the binary-nature of binary-vars is the thing giving you trouble, consider a company * X matrix describing what company serves which unit costs (for the above: a 2 x 5 matrix of binary-variables). (and no: that's not multi-objective optimization) — sascha
– sascha, Commented Mar 26, 2018 at 11:38
How would you go about implementing a constraint that applies only to a row of the matrix? — Valberto Enoc Rodrigues
– Valberto Enoc Rodrigues, Commented Mar 26, 2018 at 17:26
This looks a bit like an assignment problem. It has really nothing to do with multi-objective optimization. — Erwin Kalvelagen
– Erwin Kalvelagen, Commented Mar 27, 2018 at 2:59
Yes I agree if the original poster @ValbertoEnocRodrigues could change the title of the question to "Formulating an Assignment problem in pulp" It will be better for future people searching for an answer. — Stuart Mitchell
– Stuart Mitchell, Commented Mar 27, 2018 at 21:50

abc · Accepted Answer · 2018-03-26 15:29:38Z

2

You can define a binary variable as follows:

x_{i,j} = 1 if Company i is responsible for Unit Cost j

and add a constraint for each unit cost j telling that exactly one company must be responsible for that cost.
Consider the following example.

# data
companies = ["company1", "company2", ...]
products = ["prod1", "prod2", ...]
cost = {"prod1": cost1, "prod2": cost2, ...}

x = pulp.LpVariable.dicts("responsability",[(company, product) for company in companies for product in products], cat=pulp.LpBinary)    
prob = pulp.LpProblem("ilp", pulp.LpMinimize)

# objective function - assuming the cost is the same for all the companies
prob += pulp.LpSum(cost[product] * sum(x[(company, product)] for company in companies) for product in products)

# each product assigned to one company
for product in products:
   prob+= pulp.LpSum(x[(company, product)] for company in companies) == 1

# additional constraints
...

edited Mar 26, 2018 at 15:29

answered Mar 26, 2018 at 15:17

abc

12k2 gold badges30 silver badges55 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Valberto Enoc Rodrigues Over a year ago

I don't know if I understood this correctly, does the code assign the unit costs for each company in the respective constraint? My goal here is to have the optimizer find the best distribution for unit costs for each company given a certain constraint of cost for them. I'm sorry if I misunderstood it.

abc Over a year ago

in the example the unit costs are referred as products. In the case of only 2 companies a binary variable is enough. With 3 or more companies you need to know to which company a unit cost is assigned. This is the goal of the variables (company_i, unit_cost_j) that has value 1 if unit_cost_j is assigned to company_i. The constraint makes sure that each unit cost is assigned to exactly one company.

Valberto Enoc Rodrigues Over a year ago

I've been trying to adapt this to my problem unsuccessfully, i'm sorry to insist, but when you say that you must know to which company a unit cost is assigned (in the case of more than 2 companies), do you mean that I have to previously assign the unit_costs before optimization? because that's what I want the optimizer to do. I also need to establish constraints based on cost, for example: company1 has to have a total cost <= than 50% of the total costs possible.

Valberto Enoc Rodrigues Over a year ago

Thanks a lot @newbie. This approach helped me a lot. I still have some to tweak the constraints a bit, but it essentially solved my problem.

Collectives™ on Stack Overflow

Formulating an Linear Programming Assignment in pulp

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related