CODEWITHSUNDEEP
pythonlinear-programmingpulpminimization
Codeformer
Codeformer

Reputation: 2300

Linear programming solution for minimum number of resources

I am trying to solve this problem using linear programming using Pulp in python.

We have mango packs with each having different number of mangoes. We should be able to serve the demand using the minimum number of packets and if possible serve the whole bag.

# Packet Names and the count of mangoes in each packet.
mangoe_packs = {
    "pack_1": 2,
    "pack_2": 3,
    "pack_3": 3,
    "pack_4": 2
}

For example,

Based on the demand we should get the correct packets. Ie., if the demand is 2, we give the packet with 2 mangoes. If the demand is 5, we serve packets with 2 and 3 mangoes. If your demand is 2 and we don't have any packet with 2 mangoes we can serve packet with 3 mangoes. In this case, we will have one remnant mango. Our purpose is to have the least number of remnant mangoes while serving the demand.

# Packet Names and the count of mangoes in each packet.
mangoe_packs = {
    "pack_1": 2,
    "pack_2": 3,
    "pack_3": 3,
    "pack_4": 2
    }

Based on the data provided above,

If the demand is 2, The solution is pack_2 (can be pack_4 also).

If the demand is 4, The solution is pack_2 + pack_4.

If the demand is 5, The solution is pack_1 + pack_2

I am new to Linear programming and stuck at the problem. Tried few solutions and they are not working.

I am unable to come up with the correct objective function and constraints to solve this problem. Need help with that. Thank you.

Here is the code I tried.

from pulp import *
prob = LpProblem("MangoPacks", LpMinimize)

# Number of Mangoes in each packet.
mangoe_packs = {
    "pack_1": 2,
    "pack_2": 3,
    "pack_3": 3,
    "pack_4": 2
}

# Define demand variable.
demand = LpVariable("Demand", lowBound=2, HighBound=2, cat="Integer")

pack_count =  LpVariable.dicts("Packet Count",
                                     ((i, j) for i in mangoe_packs.values() for j in ingredients),
                                     lowBound=0,
                                     cat='Integer')

pulp += (
    lpSum([
        pack_count[(pack)]
        for pack, mango_count in mangoe_packs.iteritems()])
)

pulp += lpSum([j], for pack, j in mangoe_packs.iteritems()]) == 350 * 0.05


status = prob.solve()

Thank you.

Upvotes: 0

Views: 445

Answers (2)

trincot
trincot

Reputation: 351218

Here are some considerations:

  • The variables of the problem are whether or not a pack should be opened. These variables are thus either 0 or 1 (keep closed, or open).

  • The main objective of the problem is to minimise the number of remnant mangoes. Or otherwise put: to minimise the total number of mangoes that are in the opened packs. This is the sum of the values of the input dictionary, but only of those entries where the corresponding LP variable is 1. Of course, a multiplication (with 0 or 1) can be used here.

  • In case of a tie, the number of opened packs should be minimised. This is simply the sum of the above mentioned variables. In order to combine this into one, single objective, multiply the value of the first objective with the total number of packets and add the value of this second objective to it. That way you get the right order in competing solutions.

  • The only constraint is that the sum of the number of mangoes in the opened packs is at least the number given in the input.

So here is an implementation:

def optimise(mango_packs, mango_count):
    pack_names = list(mango_packs.keys())
    prob = LpProblem("MangoPacks", LpMinimize)
    # variables: names of the mango packs. We can either open them or not (0/1)
    lp_vars = LpVariable.dicts("Open", pack_names, 0, 1, "Integer")
    # objective: minimise total count of mangoes in the selected packs (so to 
    # minimise remnants). In case of a tie, minimise the number of opened packs.
    prob += (
        lpSum([mango_packs[name]*lp_vars[name] for name in pack_names]) * len(mango_packs)
        + lpSum([lp_vars[name] for name in pack_names]) 
    )
    # constraint: the opened packs need to amount to a minimum number of mangoes
    prob += lpSum([mango_packs[name]*lp_vars[name] for name in pack_names]) >= mango_count
    
    prob.solve()

In order to visualise the result, you could add the following in the above function:

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

    # Each of the variables is printed with it's resolved optimum value
    for i, v in enumerate(prob.variables()):
        print("{}? {}".format(v.name, ("no","yes")[int(v.varValue)]))

Call the function like this:

# Packet Names and the count of mangoes in each packet.
mango_packs = {
    "pack_1": 10,
    "pack_2": 2,
    "pack_3": 2,
    "pack_4": 2
}

optimise(mango_packs, 5)

Output (when you added those print statements)

Status: Optimal
Open_pack_1? no
Open_pack_2? yes
Open_pack_3? yes
Open_pack_4? yes

See it run here -- give it some time to temporarily install the pulp module.

Upvotes: 2

Magnus Åhlander
Magnus Åhlander

Reputation: 1446

Here is a simple model that minimizes the total number of remnant mangoes. Instead of specifying the exact packages available the model just specifies the number of packages available per size (here 5 of size 2 and 15 of size 4):

from pulp import *

# PROBLEM DATA:
demand = [3, 7, 2, 5, 9, 3, 2, 4, 7, 5] # demand per order 
packages = [0, 5, 0, 15] # available packages of different sizes
O = range(len(demand))
P = range(len(packages))

# DECLARE PROBLEM OBJECT:
prob = LpProblem('Mango delivery', LpMinimize)

# VARIABLES    
assigned = pulp.LpVariable.dicts('assigned', 
    ((o, p) for o in O for p in P), 0, max(demand), cat='Integer') # number of packages of different sizes per order 
supply = LpVariable.dicts('supply', O, 0, max(demand), cat='Integer') # supply per order
remnant = LpVariable.dicts('remnant', O, 0, len(packages)-1, cat='Integer') # extra delivery per order

# OBJECTIVE
prob += lpSum(remnant) # minimize the total extra delivery

# CONSTRAINTS
for o in O:
    prob += supply[o] == lpSum([p*assigned[(o, p)] for p in P])
    prob += remnant[o] == supply[o] - demand[o]
    
for p in P:
    # don't use more packages than available    
    prob += packages[p] >= lpSum([assigned[(o, p)] for o in O])

# SOLVE & PRINT RESULTS
prob.solve()

print(LpStatus[prob.status])
print('obj = ' + str(value(prob.objective)))
    
print('#remnants = ' + str(sum(int(remnant[o].varValue) for o in O)))
print('demand = ' + str(demand))    
print('supply = ' + str([int(supply[o].varValue) for o in O]))    
print('remnant = ' + str([int(remnant[o].varValue) for o in O]))

If the demand cannot be fulfilled this model will be infeasible. Another option in this case would be to maximize the number of orders fulfilled with a penalty for remnant mangoes. Here is the adapted model:

from pulp import *

# PROBLEM DATA:
demand = [3, 7, 2, 5, 9, 3, 2, 4, 7, 5] # demand per order 
packages = [0, 5, 0, 5] # available packages of different sizes
O = range(len(demand))
P = range(len(packages))
M = max(demand) # a big enough number

# DECLARE PROBLEM OBJECT:
prob = LpProblem('Mango delivery', LpMaximize)

# VARIABLES    
assigned = pulp.LpVariable.dicts('assigned', 
    ((o, p) for o in O for p in P), 0, max(demand), cat='Integer') # number of packages of different sizes per order 
supply = LpVariable.dicts('supply', O, 0, max(demand), cat='Integer') # supply per order
remnant = LpVariable.dicts('remnant', O, 0, len(packages)-1, cat='Integer') # extra delivery per order

served = LpVariable.dicts('served', O, cat='Binary') # whether an order is served

diff = LpVariable.dicts('diff', O, -M, len(packages)-1, cat='Integer') # difference between demand and supply

# OBJECTIVE
# primary objective is serve orders, secondary to minimize remnants
prob += 100*lpSum(served) - lpSum(remnant) # maximize served orders with a penalty for remnants

# CONSTRAINTS
for o in O:
    prob += supply[o] == lpSum([p*assigned[(o, p)] for p in P])
    prob += diff[o] == supply[o] - demand[o]
    
for p in P:
    # don't use more packages than available    
    prob += packages[p] >= lpSum([assigned[(o, p)] for o in O])
    
for o in O:
    # an order is served if supply >= demand
    # formulation adapted from https://cs.stackexchange.com/questions/69531/greater-than-condition-in-integer-linear-program-with-a-binary-variable
    prob += M*served[o] >= diff[o] + 1
    prob += M*(served[o]-1) <= diff[o]
    prob += lpSum([assigned[(o, p)] for p in P]) <= M*served[o] 

for o in O:
    # if order is served then remnant is supply - demand
    # otherwise remnant is zero
    prob += remnant[o] >= diff[o]
    prob += remnant[o] <= diff[o] + M*(1-served[o])

# SOLVE & PRINT RESULTS
prob.solve()

print(LpStatus[prob.status])
print('obj = ' + str(value(prob.objective)))

print('#served = ' + str(sum(int(served[o].varValue) for o in O)))         
print('#remnants = ' + str(sum(int(remnant[o].varValue) for o in O)))         
print('served = ' + str([int(served[o].varValue) for o in O]))    
print('demand = ' + str(demand))    
print('supply = ' + str([int(supply[o].varValue) for o in O]))    
print('remnant = ' + str([int(remnant[o].varValue) for o in O]))

Upvotes: 1

Related Questions