Advanced modelling techniques: "Redundant" variables
Introducing "redundant" variables to make models more transparent
Motivational example
For a couple of months I was working in Oujda, Morocco. I have decided to visit my friend, Jacques in Capetown. As I haven't been to Africa many times before, I decided to travel by car, so that I can see more of that beautiful continent. A friend, Alae-Eddine was kind enough to lend me his car for this trip, so the only thing I'll had to pay for is the petrol for the journey. Naturally, I wanted to reduce the cost of the trip as much as possible, thus I planned in advance where and how much to refuel the car.
The trip was 11000 km long, and there were 22 petrol stations along the way, where I could buy petrol for different prices. The following table shows the petrol stations, their distance from Oujda, and the price of 1 liter of petrol there.
| Petrol station | Distance from Oujda (km) | Price of petrol (Dh/l) |
|---|---|---|
| Algeria1 | 320 | 100 |
| Algeria2 | 840 | 90 |
| Algeria3 | 1350 | 70 |
| Algeria4 | 2000 | 80 |
| Algeria5 | 2580 | 100 |
| Algeria6 | 3170 | 90 |
| Niger1 | 3560 | 120 |
| Niger2 | 4080 | 130 |
| Nigeria1 | 4660 | 140 |
| Nigeria2 | 5180 | 120 |
| Cameroon | 5500 | 150 |
| Gabon | 5950 | 160 |
| Congo1 | 6749 | 110 |
| Congo2 | 6990 | 130 |
| Angola1 | 7440 | 120 |
| Angola2 | 7960 | 130 |
| Angola3 | 8410 | 120 |
| Namibia1 | 8730 | 140 |
| Namibia2 | 9250 | 150 |
| Namibia3 | 9770 | 130 |
| SouthAfrica1 | 10350 | 140 |
| SouthAfrica2 | 10670 | 120 |
The tank of the car could hold at most 70 liters of petrol, and in average, it consumed 7.5 liters of petrol for 100 km.
Although I was eager to minimize my costs, I wanted to be safe, i.e., I did not want to get to a petrol station with an empty tank. My safety measure was to always have petrol enough for an additional 50 km. Finally, when I started in Oujda, the tank was full.
The question is straightforward: where and how much did I fill the tank of the car to get to Capetown with minimal costs?
The first mathematical model
Sets and parameters
There is only one relevant set in this problem, the set of petrol stations. We can simply define it like this:
set Stations;
Now we can introduce the next two parameters that are given for all stations:
param petrolPrice{Stations};
param distance{Stations};
And we also have some "global" parameters that are specific to our car ride:
param initialTank;
param tankCapacity;
param totalDistance;
param fuelConsumption;
Variables
There is only one variable needed: the amount of fuel we fill into our tank at each station:
var fill{Stations} >= 0;
Constraints
The first constraint must express, that we have enough fuel to get to a station plus the safety measure. All the fuel we have filled into our tank so far, plus what we initially had must be enough for that distance. This could be expressed by the following constraint:
s.t. Has_to_meet_safety_measure {s in Stations}:
(initialTank + sum {s2 in Stations: distance[s2] < [s]} fill[s2]) * (100 / fuelConsumption) >= distance[s]+safetyMeasure;
where the term initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] summarizes how much fuel we had put into our tank so far (including the initial amount), which has to be multiplied by 100/fualConsumption to get the distance allowed by that amount.
The RHS is simply the distance of the station plus the safety measure.
Note, the filter distance[s2] < distance[s] makes the sum go over only of the previous stations.
A similar constraint must be added to specify, that we should have enough fuel to get to the final destination:
s.t. Need_to_reach_final_destination:
(initialTank + sum {s in Stations} fill[s]) * (100 / fuelConsumption) >= totalDistance;
Finally, we can not overfill the tank:
s.t. Can_not_overfill{s in Stations}:
initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s] * (fuelConsumption / 100) + fill[s] <= tankCapacity;
This constraint is similar to the first one: the LHS summarizes how much fuel is in the tank before leaving the petrol station (initial + filled previously - consumed + filled now), and the RHS is simply the capacity of our tank.
Objective function
The objective function is simply the minimization of the total cost:
minimize TotalCost:
sum{s in Stations} fill[s]*fuelPrice[s];
Some fancy output
To have a nice output this could be added:
printf "Total cost: %g\n\n",TotalCost;
for{s in Stations}
{
printf "%14s (%5g km, %3g Dh/l): %5.2g + %5.2g ---> %5.2g l\n",s,distance[s],fuelPrice[s],
initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s] * (fuelConsumption / 100),
fill[s],
initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s] * (fuelConsumption / 100) + fill[s]
;
}
The overall modell
The overall modell looks like this:
param totalDistance; #km
param fuelConsumption; # l / 100 km
param tankCapacity; # l
param initialTank, default tankCapacity; # l
param safetyMeasure; # km
set Stations;
param distance{Stations}; # km
param fuelPrice{Stations}; # Dh / l
var fill{Stations} >= 0;
s.t. Has_to_meet_safety_measure {s in Stations}:
(initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2]) * (100 / fuelConsumption) >= distance[s]+safetyMeasure;
s.t. Can_not_overfill{s in Stations}:
initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s] * (fuelConsumption / 100) + fill[s] <= tankCapacity;
s.t. Need_to_reach_final_destination:
(initialTank + sum {s in Stations} fill[s]) * (100 / fuelConsumption) >= totalDistance;
minimize TotalCost:
sum{s in Stations} fill[s]*fuelPrice[s];
solve;
printf "Total cost: %g\n\n",TotalCost;
for{s in Stations}
{
printf "%14s (%5g km, %3g Dh/l): %5.2g + %5.2g ---> %5.2g l\n",s,distance[s],fuelPrice[s],
initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s] * (fuelConsumption / 100),
fill[s],
initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s] * (fuelConsumption / 100) + fill[s]
;
}
With the following data file
param totalDistance := 11000; param fuelConsumption := 7.5; param tankCapacity := 70; param safetyMeasure := 50; set Stations:= Algeria1 Algeria2 Algeria3 Algeria4 Algeria5 Algeria6 Niger1 Niger2 Nigeria1 Nigeria2 Cameroon Gabon Congo1 Congo2 Angola1 Angola2 Angola3 Namibia1 Namibia2 Namibia3 SouthAfrica1 SouthAfrica2; param: distance fuelPrice:= Algeria1 320 100 Algeria2 840 90 Algeria3 1350 70 Algeria4 2000 80 Algeria5 2580 100 Algeria6 3170 90 Niger1 3560 120 Niger2 4080 130 Nigeria1 4660 140 Nigeria2 5180 120 Cameroon 5500 150 Gabon 5950 160 Congo1 6479 110 Congo2 6990 130 Angola1 7440 120 Angola2 7960 130 Angola3 8410 120 Namibia1 8730 140 Namibia2 9250 150 Namibia3 9770 130 SouthAfrica1 10350 140 SouthAfrica2 10670 120 ;
The solution
After solving this simple model, we get the following output:
Total cost: 84572.7
Algeria1 ( 320 km, 100 Dh/l): 46 + 0 ---> 46 l
Algeria2 ( 840 km, 90 Dh/l): 7 + 35 ---> 42 l
Algeria3 ( 1350 km, 70 Dh/l): 3.8 + 66 ---> 70 l
Algeria4 ( 2000 km, 80 Dh/l): 21 + 49 ---> 70 l
Algeria5 ( 2580 km, 100 Dh/l): 26 + 21 ---> 48 l
Algeria6 ( 3170 km, 90 Dh/l): 3.7 + 66 ---> 70 l
Niger1 ( 3560 km, 120 Dh/l): 41 + 29 ---> 70 l
Niger2 ( 4080 km, 130 Dh/l): 31 + 39 ---> 70 l
Nigeria1 ( 4660 km, 140 Dh/l): 26 + 16 ---> 43 l
Nigeria2 ( 5180 km, 120 Dh/l): 3.8 + 66 ---> 70 l
Cameroon ( 5500 km, 150 Dh/l): 46 + 24 ---> 70 l
Gabon ( 5950 km, 160 Dh/l): 36 + 7.2 ---> 43 l
Congo1 ( 6479 km, 110 Dh/l): 3.8 + 66 ---> 70 l
Congo2 ( 6990 km, 130 Dh/l): 32 + 5.8 ---> 38 l
Angola1 ( 7440 km, 120 Dh/l): 3.8 + 66 ---> 70 l
Angola2 ( 7960 km, 130 Dh/l): 31 + 6.5 ---> 38 l
Angola3 ( 8410 km, 120 Dh/l): 3.8 + 66 ---> 70 l
Namibia1 ( 8730 km, 140 Dh/l): 46 + 24 ---> 70 l
Namibia2 ( 9250 km, 150 Dh/l): 31 + 12 ---> 43 l
Namibia3 ( 9770 km, 130 Dh/l): 3.7 + 66 ---> 70 l
SouthAfrica1 (10350 km, 140 Dh/l): 26 + 1.2 ---> 28 l
SouthAfrica2 (10670 km, 120 Dh/l): 3.7 + 21 ---> 25 l
A different way of modelling the problem
If an IT person would look at the above code, he/she would probably consider it a bit ugly, as the term initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] repeats a couple of times thourough the model.
In case of such redundancy in a computer code, the programmer would probably introduce a function, that can be called from different places.
In modelling we can do something similar: we can introduce additional variables, that represent
var fuelAtArrival{Stations};
These variables will denote, how much fuel we have when we arrive to a station.
However, these variables do not present a decision, they are calculated based on other "real" decision variables and parameters in equality constraints, like the one below:
s.t. set_fuelAtArrival{s in Stations}:
fuelAtArrivaml[s] = initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s]/100*fuelConsumption;
We will refer to these kind of variables as Now some of the constraints, outputs can be simplified:
s.t. Has_to_meet_safety_measure {s in Stations}:
fuelAtArrival[s] * (100 / fuelConsumption) >= safetyMeasure;
s.t. Can_not_overfill{s in Stations}:
fuelAtArrival[s] + fill[s] <= tankCapacity;
and:
for{s in Stations}
{
printf "%14s (%5g km, %3g Dh/l): %5.2g + %5.2g ---> %5.2g l\n",s,distance[s],fuelPrice[s],
fuelAtArrival[s], fill[s], fuelAtArrival[s] + fill[s]
;
}
If we look at the first constraint from above, it can even be eliminated and moved to a lower bound for the variable:
var fuelAtArrival{Stations} >= safetyMeasure / 100 * fuelConsumption;
Final look
So, the final version looks like this:
param totalDistance; #km
param fuelConsumption; # l / 100 km
param tankCapacity; # l
param initialTank, default tankCapacity; # l
param safetyMeasure; # km
set Stations;
param distance{Stations}; # km
param fuelPrice{Stations}; # Dh / l
var fill{Stations} >= 0;
var fuelAtArrival{Stations} >= safetyMeasure / 100 * fuelConsumption;
s.t. set_fuelAtArrival{s in Stations}:
fuelAtArrival[s] = initialTank + sum {s2 in Stations: distance[s2] < distance[s]} fill[s2] - distance[s]/100*fuelConsumption;
s.t. Can_not_overfill{s in Stations}:
fuelAtArrival[s] + fill[s] <= tankCapacity;
s.t. Need_to_reach_final_destination:
(initialTank + sum {s in Stations} fill[s]) * (100 / fuelConsumption) >= totalDistance;
minimize TotalCost:
sum{s in Stations} fill[s]*fuelPrice[s];
solve;
printf "Total cost: %g\n\n",TotalCost;
for{s in Stations}
{
printf "%14s (%5g km, %3g Dh/l): %6.3f + %6.3f ---> %6.3f l\n",s,distance[s],fuelPrice[s],
fuelAtArrival[s], fill[s], fuelAtArrival[s] + fill[s]
;
}
The same data section can be used, and the output is exactly the same as above.
Readability / maintainability over performance?
One could rightfully raise their voice, and complain, that we made a bad deal, as our model now has twice as many variables and thus, solving it will be slower. That is theoretically true, however:
- Adding a few continuous variables does not really make the problem that much harder to solve.
- A good solver will probably realize this, and exclude them.
- Some languages may support this explicitely, like defined variables in AMPL
- Sometimes, especially for easy-to-solve problems with complicated constraints, a maintainable code is much more important.
- If the model gets extended, these variables may come in handy.
Excercise for you
The model could be transformed a bit further as well based on the following idea: the fuel level in the tank at a station is simply the level when leaving the fuelAtArrival[s] values based on this idea.
A bit of help: in the model, it will be important to refer to the previous station, that is difficult with the above set and parameter definitions. Changing the form of the input data to the following can solve this issue:
param stationCount;
set Stations:=1..stationCount;
param stationName{Stations} symbolic;
and in the data section:
param stationCount := 22;
param:
stationName distance fuelPrice :=
1 Algeria1 320 100
2 Algeria2 840 90
3 Algeria3 1350 70
4 Algeria4 2000 80
...