Constrain the maximum allocation size using Mixed Integer Programming

Question

I have 2 facilities, each has a pipeline and installation cost. I also have 16 customers to be serviced, each customer has a service cost. I want to assign each facility a maximum of 10 customers such that the cost of pipeline, installation and service costs are minimized.

I have implemented the following code but it is not working properly. It is supposed to assign each facility to the number of Customers it should serve and returns the minimum costs. However, the output assign the wells to all facilities (i think).

Your help is much appreciated:

import numpy as np
from pulp import *
import random 
CUSTOMERS = range(1,17) ## generate random Customer Ids
FACILITY =['FAC 1','FAC 2'] # Number and Name of Facilities
randomCosts = random.sample(range(90, 100), 2) ## Generate Random Installation Costs 
actcost = dict(zip(FACILITY, randomCosts)) ## Assign installation cost to each facility
randompipelineCost = random.sample(range(5, 20), 2) ## Generate Random pipeline Costs
pipelineCost = dict(zip(FACILITY, randompipelineCost))## Assign pipeline cost to each facility
sizeOfPlatforms = [10,10] ## Size of Platforms
maxSizeOfPlatforms = dict(zip(FACILITY, sizeOfPlatforms)) ## Assign Size to each Facility
serviceRandom=[] 
serviceCosts = {}
for facility in FACILITY: ## Generate Random Service Costs for each customer
   serviceRandom=[]
   for i in range (16):
     serviceRandom.append(random.randrange(1, 101, 1))
   service = dict(zip(CUSTOMERS, serviceRandom))
   serviceCosts[facility]=service

print 'CUSTOMERS', CUSTOMERS
print 'FACILITY', FACILITY
print 'Facility Cost', actcost 
print 'pipeline Cost',pipelineCost 
print 'service Cost', serviceCosts 

prob = LpProblem("FacilityLocation",LpMinimize)


##Decision Variables

use_facility = LpVariable.dicts("UseFacility", FACILITY,0,1,LpBinary)

use_customer = LpVariable.dicts("UseCustomer",[(i,j) for i in CUSTOMERS for j in FACILITY],1)

## Objective Function 

prob += lpSum(actcost[j]*use_facility[j] for j in FACILITY) + lpSum(pipelineCost[j]*use_facility[j] for j in FACILITY)+ lpSum(serviceCosts[j][i]*use_customer[(i,j)] for i in CUSTOMERS for j in FACILITY)

# Constraints 

for j in FACILITY: 
   prob += lpSum(use_customer[(i,j)] for i in CUSTOMERS) <= maxSizeOfPlatforms[j]


for j in FACILITY: 
   prob += lpSum(use_facility[j] for j in FACILITY) <=1.0 ##Constraint 1 

##Solution 

prob.solve() 
print ("Status:", LpStatus[prob.status])

TOL = 0.00001 


## print Decision Variables
for i in FACILITY: 
   if use_facility[i].varValue > TOL:
     print("Establish Facility at Site",i)

for v in prob.variables():
  print(v.name,"=", v.varValue)


##optimal Solution
print ("The cost of production in dollars for one year=", value(prob.objective))

Thanks. I updated the question to include what is it supposed to do and what is it doing right now. — M.Khaled
– M.Khaled, Commented Aug 29, 2018 at 2:39

abc · Accepted Answer · 2018-08-29 05:48:33Z

There are 4 different problems.

1)

use_customer = LpVariable.dicts("UseCustomer",[(i,j) for i in CUSTOMERS for j in FACILITY],1)

This is equivalent to say each variable is fractional and should be greater than one. That is, your are setting lowBound=1. I guess that you would like to say here that the variable is binary:

use_customer = LpVariable.dicts("UseCustomer",[(i,j) for i in CUSTOMERS for j in FACILITY], cat=LpBinary)

2)

The second problem is that you don't constraint the customer to be assigned to at least a facility (at least because since the problem is a minimization problem and yours costs are strictly positive a customer will never be assigned to more than one facility, but in the follows I will assume exactly one)

for i in CUSTOMERS: 
     prob += lpSum(use_customer[(i,j)] for j in FACILITY) == 1.0

3)

I'm not sure to have understood what you would like to say here:

for j in FACILITY: 
   prob += lpSum(use_facility[j] for j in FACILITY) <=1.0 ##Constraint 1

Each time you are summing all the facilities and constraining the sum of their values to be at most one. I guess it is a mistake.

4)

Finally, you don't link the variables use_facility and use_customer together. That is, a variable use_facility will never have value grater than 0. As it is binary I assume use_facility[j] represents the activation cost. You need thus to add in order to activate a facility, that is facility j is activated if at least one customer uses it:

for j in FACILITY:
    for i in CUSTOMERS:
        prob += use_facility[j] >= lpSum(use_customer[(i,j)])

Putting all together:

##Decision Variables

use_facility = LpVariable.dicts("UseFacility", FACILITY, cat=LpBinary)

use_customer = LpVariable.dicts("UseCustomer",[(i,j) for i in CUSTOMERS for j in FACILITY], cat=LpBinary)

## Objective Function 

prob += lpSum(actcost[j]*use_facility[j] for j in FACILITY) + lpSum(pipelineCost[j]*use_facility[j] for j in FACILITY)+ lpSum(serviceCosts[j][i]*use_customer[(i,j)] for i in CUSTOMERS for j in FACILITY)


# Constraints 
for j in FACILITY: 
   prob += lpSum(use_customer[(i,j)] for i in CUSTOMERS) <= maxSizeOfPlatforms[j]

for i in CUSTOMERS: 
   prob += lpSum(use_customer[(i,j)] for j in FACILITY) == 1

for j in FACILITY:
    for i in CUSTOMERS:
        prob += use_facility[j] >= lpSum(use_customer[(i,j)])

Thank you very much, solved my problem and gave me a clear explanation of how to formulate the constraints.
@M.Khaled You should accept an answer which resolved your problem by checking the box left to the answer.

Collectives™ on Stack Overflow

Constrain the maximum allocation size using Mixed Integer Programming

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related