I am trying to solve a hypothetical linear problem using PuLP. The problem aims at minimizing the costs of an operation over a 5 year horizon while maximizing product shape and condition. The problem must generate 5 costs, one for each year while optimizing the system as a whole and the operations of each year.
total_cost = [(var_cost[year] + fix_cost[year] + cost_new_sensors[year]) for year in range(0,5)]
The total_cost involves maintaining three types of sensors:
# units price_new fixed_cost_per_unit_per_yr variable_costs_pr_yr_pr_unit
sensor_type_a 300 $50 rent + insurance power + maint
sensor_type_b 900 $75 rent + insurance power + maint
sensor_type_c 1500 $90 maint + insurance -
"Very poor".For sensor_type_a:
[50, 55, 55, 55, 60][ 1.0, 1.2, 1.2, 1.8, 2.0]10+.05*each_measurement. Price goes up by 1% per year$500 for the total number of sensors + each_measurement*2.45. Price goes up by 2% year_
exposure(# of measurements) category
<=100 excellent
250 good
400 poor
>=400 very poor
For sensor_type_b:
[60, 65, 65, 70, 75][ 1.1, 1.3, 1.4, 1.7, 2.0]10+.08*each_measurement. Price goes up by 1% per year$500 for the total number of sensors + each_measurement*2.65. Price goes up by 1.5% year_
exposure(# of measurements) category
<=200 excellent
350 good
500 poor
>=500 very poor
For sensor_type_c:
[5000, 5100, 5200, 5300, 5400][ 1.1, 1.3, 1.4, 1.7, 2.0]_
exposure(# of measurements) category
<=300 excellent
450 good
600 poor
>=600 very poor
My objective function/equation is one of minimization:
problem = pulp.LpProblem(’Cost Minimization’, pulp.LpMinimize)
My constraints:
I am having troubles setting up the constraint functions. Here is what I am conceptually thinking of doing (mix of pseudo and python):
problem += sum([fixed_costs[yr][a] + var_costs[yr][a]
for a in sensor_type_a
for yr in years])
problem += sum([fixed_costs[yr][b] + var_costs[yr][b]
for a in sensor_type_b
for yr in years])
problem += sum([fixed_costs[yr][c] + var_costs[yr][c]
for a in sensor_type_c
for yr in years])
problem += sum(sensor_type_[a].condition('very poor') + \
sensor_type_[b].condition('very poor') + \
sensor_type_[c].condition('very poor')) <= 12%
problem += sum(sensor_type_[a].average_condition(yr) + \
sensor_type_[b].average_condition(yr) + \
sensor_type_[c].average_condition(yr) >=
sensor_type_[a].average_condition(yr-1) + \
sensor_type_[b].average_condition(yr-1) + \
sensor_type_[c].average_condition(yr-1)
Question:
If I'm not on the right track with my pseudo+python, how can I setup my constraints properly to solve the problem?
Note that I have a table for each item filled in for each variables with the proper categories and data points
Edit to reflect on the comments below:
In total there are 2,700 units or locations to be measured. I have a table of the following nature:
unit_ID actual_2013 forecasted_2014 forecasted_2015 forecasted_2016 forecasted_2017
1 25 30 40 35 50
2 400 430 460 480 50
n x_1 x_2 x_3 x_4 x_5
The model cannot change the make up of sensor types for this year however, it should be able to model it adequately for future years. Meaning that include the cost of replacement etc, to get better sensors and a reduced overall cost.
Units are interchangeable.
Here's how I'd approach this.
First, you want to keep the model formulation separate from the code implementation in PuLP or otherwise.
If you get the formulation right, it becomes much easier to implement. (You rightly mention that there are some tricky constraints in your problem.)
One final suggestion before we look at the formulation: You have quite a complex and detailed set of costs and constraints. I suggest getting the base formulation and the LP solution working, and then layering in the constraints and detailed costs (rentals, maintenance etc.) Otherwise, you will spend an enormous amount of time debugging and verifying your model.
We have three types of sensors s = {a, b, c}.
We have a time horizon of 5 years = t = {1..5}
We have around 2700 locations l = {1..2700}
Main Decision variable - Deciding which sensory type goes on which location
Let `X_lst` be 1 if the unit at location l gets assigned a sensor of type `s` in year `t`
0 otherwise
Let `N_st` be the total number of sensors of type s used in year t
X and N are decision variables.
We are also given lots of 'constants' (These are your input tables.)
Let E_lt be the total number of exposures in location l in year t.
(Note that E_lt is given or forecast outside the problem. The IP output does not decide this.
One final set of decision variables are needed:
Let Y_lst_ctype be 1 if at the end of time period t, sensor type s in location l ends up being of condition ctype based on the number of exposures it sensed in that year.
ctype can be one of {Excellent, Good, Poor, VeryPoor}
By our notation Y_2b2_poor represents the decision-variable that sensor type b attached to unit 2, at the end of the 2nd year ends up in poor condition.
Now, let's start modeling the numerous constraints that you have mentioned:
Cover Constraint Every location must have a sensor in every year. (sum over s) X_lst = 1 for each t, for each location l.
Total Number Constraint For each sensor type, in each year, we have an equation for the total number.
N_st = X_1st + X_2st + ... + X_2700st for each sensor type s, and for each time period t
(These constraints are sometimes referred to as 'definitional' constraints. They make sure that N and X are internally consistent.)
Starting conditions
N_a1 <= 300
N_b1 <= 900
N_c1 <= 1500
Sensor Condition Related Constraints
These are a bit tricky, and that's why we had to introduce so many 0/1 type Y variables.
Each sensor can only end up in one condition
Y_lst_excellent + Y_lst_good + Y_lst_poor + Y_lst_verypoor = 1
Now we have a write a bunch of linear constraints that ascertain the condition of the sensor based on number of exposures.
Trick We have to use the big-M method to make sure that the model assigns it the right condition.
For sensor type a
E_lt x X_lat <= 100 + M (1- Y_lat_good)
E_lt x X_lat <= 250 + M (1- Y_lat_poor)
E_lt x X_lat <= 400 + M (1- Y_lat_verypoor)
If you study this, you will see that depending on the number of exposures experienced, the correct condition gets assigned, while still keeping everything linear. (M is some big number)
Do this for the sensor types b and c also.
Limiting Percentage to Very Poor Condition
Y_1st + Y_2st + Y_3st + ... + Y_2700st <= 0.12 x Nst (for each sensor type s, year t)
You have already listed it, so I'll just mention the contour that the objective function will take.
Min sum_all_cots x X_lst where the sum will have components related to rent, maintenance and replacement.
Final Note To be super-accurate, you also need a decision-variable that decides whether to keep or replace with new a sensor at each location.
R_lst = 1 if location l gets a NEW sensor of type s at the end of year t
And depending on the 'replace vs retail' cost trade-offs, you'd add more constraints. But the model is complicated as such, so I didn't write out those constraints.
You have to translate into your Python model and write out the formulation to see if it makes sense. Try it on a trivial problem, and keep adding more constraints and variables.
Hope that helps you move forward.