Bin packing variant

Question

I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume with the optimum way through the compartments.
I have created a model, which works almost perfectly, where I try to minimize the wastage (from all the compartments, not only the used).
Now let's say that I have a preference in using as front compartments as possible, namely if the 2nd compartment and the 8th compartment have 1000lt capacity, then I want to use the 2nd compartment. I want this to happen only when the wastage of the one solution is equal to the other.

Hence, If I have a solution with wastage 1100 lt and the 2nd compartment is empty, but I have another solution with wastage 1100lt and the 8th compartment is empty, I want the model to extract the second.

Is there a way to model preference constraints, without diverging from the original objective (minimizing wastage)?

EDIT
Let me explain a little more about my objective. Right now the objective is

$$\sum_i\sum_j(c_{j}-y_{ij})$$

Where $c_{j}$ is the capacity of each compartment $j$ and $y_{ij}$ is the assigned quantity of element $i$ in compartment $j$. If we assume that the new part of the objective function is to be found (I'm counting on you), then I can replace the function above with:

$$M\cdot\sum_i\sum_j(c_{j}-y_{ij})+\mu\cdot F$$

Where $M$ is going to be a big number and $\mu$ a small number. $F$ would be the second objective.

Answer 1

It sounds like you are describing what is sometimes called a hierarchical decision-making problem -- we want to optimize some objective, but among all solutions that are optimal for that objective, we want to optimize some secondary objective.

One approach for such problems is to put both objectives into the objective function, but with a large weight on the first objective. The weight should be large enough that a solution that's suboptimal for the first objective can't "cheat" its way into optimality by optimizing the second objective. This is usually possible with binary variables but might not be possible with continuous ones; I haven't thought it through.

Another approach is to first solve the problem with only the first objective (minimize waste) and without the second objective (tank preference) and get the optimal objective function value -- call it $z^*$. Then add a constraint requiring the waste minimization to equal $z^*$, and replace the objective function with the tank-preference objective. Now you are optimizing the tank preference but ensuring that the solution will still be optimal for the first objective.

(Essentially this is a special case of multi-objective optimization.)

Answer 2

If I understand you correctly (and I'm not betting on that), you could accomplish what you want using binary variables and some added constraints. Add a binary variable $z_j$ for each compartment $j$, together with the constraints $$c_j z_j \ge \sum_i y_{ij} \ge \epsilon z_j \quad \forall j$$ and $$z_k \le z_j \quad \forall j,k: j < k \wedge c_j = c_k.$$ Here $\epsilon>0$ is the minimum amount of cargo you would consider putting in a compartment. The first constraint forces $z_j=0$ if you leave compartment $j$ empty and $z_j=1$ if you use it. The second constraint, restricted to pairs of compartments with equal capacity, says that you cannot use the higher index compartment unless you have used the lower index compartment. Thus compartment $j$ cannot be empty unless compartment $k$ is also empty.

Note that this deals only with the question of where empty compartments of equal capacity would go; it does not address empty compartments of differing capacities, nor the question of whether cargo in a partially full compartment $k$ could be moved to a partially full compartment $j$ of lower index.

Answer 3

I assume your objective minimization. This can be work

$$\sum_i\sum_j m\cdot j\cdot(c_{j}-y_{ij})$$

But you should need fine tuning for m based on importance of waste capacity and sequence.