I think people are being a bit too hostile. Even in professional environments, with people who are trained to do so, it can be hard to fully describe a problem so that it can be approached mathematically. If you haven’t been trained in optimization, how can you know what you need to know to be able to optimize?
Now, this is what I assume the problem is (in 2 parts)-
A) Fuel needs to put into tanks from compartments. All the fuel needs to put into the tanks. It takes a certain amount of effort to attach a compartment to a tank. You can fill part of more than 1 tank with a single compartment, but this requires detaching from the first tank then attaching to the second, something you wish to avoid if possible. Is there a way of selecting which compartments go to which tanks that reduces the total amount of times you fill a tank with a compartment?
B) The fuel in a tank is used up over time, and so it might be better to not split up a compartment’s load into multiple tanks and instead wait for a tank to depleted enough that it can be fully offload into a single tank (for example, 3000 L in a compartment, and 2990 capacity left in a tank. It is easier to just wait for 10 L from that tank to be used than to fill up another tank with the 10L)
I’ll approach A first, since B can be treated as an extension.
For anyone who has read the thread “Mathematicians: Is Linear Programming All That Useful?” and remained unconvinced of its usefulness, here is a perfect example of Linear Programming and Integer Programming.
We’ll start with an important concept in mathematical optimization in general, decision variables. Decision variables correspond either to decisions we make, or the consequences of those decisions. For this problem there are two important decision types-
Is a given compartment used to fill a given tank?
How much of a given compartment’s load is used to fill a given tank?
The first is a yes/no question. Often you describe yes/no questions mathematically with a variable that can take two values. If it is 0, that means the answer is no, and if it is 1 means yes. For this problem I used the variable y[sub]i,j[/sub] to mean that tank i has been filled by part of compartment j. For example, if any part of compartment 3 is used to fill tank 2, then y[sub]2,3[/sub] = 1. If no part of compartment 6 is used to fill tank 1 then y[sub]1,6[/sub] = 0. (I will use i to index the tank numbers and j to index the compartment numbers)
The second question is a quantitative one, it deals with litres of fuel used. There are two ways of treating this, either we have a variable corresponding to the amount of fuel from a compartment to a tank, or a variable corresponding to the proportion of a tank used. I chose the second, though it is very easy to switch to the first if wanted. This is given by x[sub]i,j[/sub], with the value corresponding to the proportion of compartment j put into tank i. For example, since there is 4400 L in compartment 1, x[sub]2,1[/sub] = 0.1 corresponds to 4400L*0.1 or 440L being put into tank 2 from compartment 1. Because it is a proportion, each x[sub]i,j[/sub] must be between 0 and 1 but can take on a fractional value.
I will use u[sub]i[/sub] to mean the amount of space left in tank i, and v[sub]j[/sub] to mean the amount of fuel in compartment j.
Now I have a way of describing what I choose to do, what do I have to do? There are two simple groups of constraint I need to have:
(1) Each compartment’s load must be put into tanks
(2) There is a capacity in each tank, fuel that goes into the tank cannot go above the volume left over.
How do we describe these mathematically? This is fairly easy, and can be described with what can be called linear constraints.
For every compartment:
All of it must be used, i.e. the sum of the proportions put into every tank is 1.
So, for compartment 4:
x[sub]1,4[/sub] + x[sub]2,4[/sub] + x[sub]3,4[/sub] == 1
So for (1), there is simply a constraint for every compartment which is a simple equality.
For every tank:
The amount of fuel put into the tank must be less than or equal to the volume left inside the tank:
So, for tank 1:
v[sub]1[/sub]x[sub]1,1[/sub] + v[sub]2[/sub]x[sub]1,2[/sub] + v[sub]3[/sub]x[sub]1,3[/sub]+v[sub]4[/sub]x[sub]1,4[/sub]+v[sub]5[/sub]x[sub]1,5[/sub] + v[sub]6[/sub]x[sub]1,6[/sub] <= u[sub]1[/sub]
For (2), for every tank there is an inequality that means we won’t overfill the tank.
In a sense, that’s it. I’ve fully described a linear program, which can be “solved” relatively easily by a linear program solver. It will produce a solution, which means giving each variable a value so that it fulfills all of the constraints. This looks a lot like the knapsack problem, but since the variables can be fractional it is actually a lot easier. However I haven’t included the last, most important bit, how good each solution is. This is called the objective function, which quantifies how good each solution is. We want to minimize the value of this objective function (you can turn a maximize into a minimize simply by multiplying the objective function by -1), and whatever solution or solutions have the lowest value out of all possible solutions are called optimal solutions, which we want to find at least one of. For our problem, we want to minimize the sum of times we fill a tank with a compartment. Even if a compartment is used a tiny bit to fill a tank it has the same setup time as fully emptying a compartment. This is why I created the y variables earlier. So:
We want to minimize the sum (over all i and j) of y[sub]i,j[/sub].
How do we make this variable work?
We need to introduce a new group of constraints, (3). This is to make the yes/no variable work. It is
For every tank/compartment (i,j) pair:
x[sub]i,j[/sub] <= y[sub]i,j[/sub]
So, if x[sub]2,3[/sub] is 1, y[sub]2,3[/sub] must be 1. If x[sub]2,3[/sub] is 0.5, y[sub]2,3[/sub] must be 1. If If x[sub]2,3[/sub] is 0, then y[sub]2,3[/sub] can be 0 or 1, but will be 0 because it wants to be as low as possible.
Now, what I have produced is no longer a Linear Program, since the y variables have to take a whole number value. Instead, this is a “Mixed Integer Linear Program”, which is sometimes shortened to Integer Program. A Linear Program solver won’t solve this, but an Integer Program solver will.
Now, does this work? How long does it take?
I wrote some code to solve this, in python using a free open source Integer Program solver.
For your initial problem, the code I put together finds a solution (tanks: compartments into that tank), with no compartment emptied into more than 1 tank:
1:4,6; 2:2, 3:1,3,5
This had an objective value of 0 (I put a -6 in the function above, since I am guaranteed to get a value of at least 6 (each compartment must emptied into a tank). Anything above 0 means the number of extra times I am forced to do)
It solved this in under a tenth of a second.
Then I solved it again and got
1:4; 2:5,6; 3:1,2,3
Once again in under a tenth of a second, with objective value of 0.
What about adding a new compartment (7) with 3000L in it?
This gives:
1:1; 2:4,5; 3:2,3,6,7
Once again under a tenth of a second, with objective value of 0.
Now, lets go back to the original 6 compartments, but then alter the amounts in each compartment. They are-
9800,6000,3500,3250,2000,1500
What does the solver find?
It tells us that we need to split up compartment 1 into more than 1 tank.
I’ll paste the results of the code:
Tank 1 space left: 0.0
Tank 2 space left: 10.0
Tank 3 space left: 0.0
Amount from Compartment 1 in Tank 1- 3090.0
Amount from Compartment 4 in Tank 1- 3250.0
Amount from Compartment 1 in Tank 2- 6710.0
Amount from Compartment 2 in Tank 3- 6000.0
Amount from Compartment 3 in Tank 3- 3500.0
Amount from Compartment 5 in Tank 3- 2000.0
Amount from Compartment 6 in Tank 3- 1500.0
Optimal Value 1.0
Time to solve: 0.350701053161
The time to solve is starting to get a bit high (for such a small problem), from a technical point of view (i.e. don’t worry if you don’t understand a word of this) there might be some inequalities you can put in to speed this up (if it was a knapsack problem then there are cover inequalities, however I don’t think they will work since the problem isn’t actually an integer knapsack problem).
Now, up till now I ignored part B) from the start of my post. Can I use Integer Programming to model that, or do I have to use something else? You can certainly try to model it with Integer Programming. Let’s assume we can deplete a tank, then we need a decision variable for each tank corresponding to the amount we deplete (let’s say z[sub]i[/sub]). Then we simply add + z[sub]i[/sub] to the right hand side of the (2) constraints. Now, how easy is it to deplete a tank? If there a maximum we can do, in which case it is a simple upper bound on the value of each z. Likewise we don’t want to rely on depletion if we don’t have to, so we have to add the z variables to the objective function. This is a hard part, which requires the people who deal with the problem to figure something out. How much depletion of a tank is preferrable to simply splitting up a compartment’s load? Is it that you’ll only do it for under 10L, or 20L, or 100L, or 1000L? Whatever the value, you simply have a co-efficient in the objective function for each Z equal to the 1 divided by the threshold.
Hopefully that wasn’t too technical, and that I got the problem right. Also I hope that I just didn’t do somebodies homework, though I doubt that.