Issue with Integer Linear Programming using PuLP

Question

I am trying to solve this ILP using PuLP. Problem states that we need to minimize the cost of building a warehouse. We need to decide which warehouse to build based on the lowest cost. Here is what the LP looks like

min ∑transportcost * X_i, ∑fixedcost * Y_j

[Where i & j are warehouse# = 1/2/3]

Constraints should be: X_i & Y_j should belong to 0 or 1 as they are decision variables X_i == Y_j

Here is the code I wrote

import pulp
from pulp import *
import pandas as pd
import numpy as np

n_warehouse = 3

warehouse_fixed_costs = [100, 120, 80]
cost_per_km = [3,3,3]
distances = [20, 30, 45]
transport_costs = [cost_per_km[i]*distances[i] for i in range(len(cost_per_km))]
warehouses = ['1','2','3']

model = LpProblem("Supply-Demand", LpMinimize)

transport_warehouse_dv = LpVariable.matrix("X", warehouses, cat = "Binary", lowBound = 0)
transport_warehouse_allocation = np.array(transport_warehouse_dv)

fixed_cost_warehouse_dv = LpVariable.matrix("Y", warehouses, cat = "Binary", lowBound = 0)
fixed_cost_warehouse_allocation = np.array(fixed_cost_warehouse_dv)

obj_func = lpSum(transport_costs*transport_warehouse_allocation)
obj_func += lpSum(warehouse_fixed_costs*fixed_cost_warehouse_allocation)
model += obj_func

const = lpSum(transport_warehouse_allocation) == fixed_cost_warehouse_allocation, "Warehouse decision"
model += const

model

This is the model created:

Supply-Demand:

MINIMIZE 60X_1 + 90X_2 + 135X_3 + 100Y_1 + 120Y_2 + 80Y_3 + 0

SUBJECT TO Warehouse_decision: X_1 + X_2 + X_3 - Y_1 - Y_2 - Y_3 = 0

VARIABLES 0 <= X_1 <= 1 Integer 0 <= X_2 <= 1 Integer 0 <= X_3 <= 1 Integer 0 <= Y_1 <= 1 Integer 0 <= Y_2 <= 1 Integer 0 <= Y_3 <= 1 Integer

When I solve the model I am getting optimal solution however, None of the decision variables are holding value 1. Total Cost is 0 as well. Ideally the answer should be 160 as warehouse 1 has the lowest cost.

Im not sure what I am missing. I haven't used PuLP earlier so I'm not able to figure out the reason.

Looks to me not building/shipping anything is the cheapest. You found the best solution. — Erwin Kalvelagen
– Erwin Kalvelagen, Commented Apr 24, 2021 at 3:02
As @ErwinKalvelagen has pointed out - your model seems to lack any constraint about a demand which needs to be satisfied by the warehouses so optimal solution (zero cost) is to not build any. — kabdulla
– kabdulla, Commented Apr 24, 2021 at 10:35
if X_i == Y_j then why do you need two variables? You need to add a constraint where lpSum(X_1 + X_2 + X_3) == 1 assuming you want to build only one new warehouse — Michael
– Michael, Commented Apr 24, 2021 at 21:11

Michael · Accepted Answer · 2021-04-24 21:59:04Z

2

as Erwin pointed out the cheapest option is to not build any warehouses.

You needed to add a constraint to force one warehouse to be build

"""
selects the cheapest warehouse to build

programmer: Michael R. Gibbs
"""

from pulp import LpProblem, LpMinimize, LpVariable, lpSum, PULP_CBC_CMD, value
import pandas as pd
import numpy as np

# we are building only one warehouse
warehouses_to_build = 1

# define the costs for the warehouse choices
warehouse_fixed_costs = [100, 120, 80]
cost_per_km = [3,3,3]
distances = [20, 30, 45]
transport_costs = [cost * dist for cost, dist in zip(cost_per_km,distances)]
warehouses = ['1','2','3']

model = LpProblem("Supply-Demand", LpMinimize)

# to build or not to build flag for each warehouse
build_warehouse_flag = LpVariable.matrix("build", warehouses, cat = "Binary", lowBound = 0)

# no warehouses is the cheepest choice
# this forces warehouses to be built
model += lpSum(build_warehouse_flag) == warehouses_to_build

# cost to be minimized
obj = lpSum([trans_cost * flag for trans_cost, flag in zip(transport_costs, build_warehouse_flag)])
obj += lpSum([fix_cost * flag for fix_cost, flag in zip(warehouse_fixed_costs, build_warehouse_flag)])
model += obj

print(model)

solver = PULP_CBC_CMD()
model.solve(solver)

print("------------------ build results -----------------------")
print([(flag, value(flag)) for flag in build_warehouse_flag])

answered Apr 24, 2021 at 21:59

Michael

1,9992 gold badges6 silver badges11 bronze badges

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

2 Comments

Umang Mistry Over a year ago

This is massively helpful. I didn't consider adding a flag. Thanks alot!

Michael Over a year ago

did you notice you can use this model to select 2 warehouses instead of just 1?

Collectives™ on Stack Overflow

Issue with Integer Linear Programming using PuLP

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