Bin packing variant

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.

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.)

• Hey Larry, thanks for the answer! I thought of doing the first, but I can't really find out a way to express the preferences. Do you have any idea? The second isn't fitting to my implementation, so it would be difficult. Feb 6 '20 at 13:35
• The first approach is tricky, because the large weights on the first objective produce numerical problems similar to what "big M" constraints produce. Feb 6 '20 at 18:51
• @dimboukosis I don't really have any other approaches -- hopefully another answer will help! Feb 7 '20 at 0:57
• @prubin Agreed. I've only ever seen this done in facility location problems, where the two objectives are similar in magnitude and you can get away with it. I don't think it's a very generalizable approach. Feb 7 '20 at 0:58
• @RenaudM. of course. I am currently running this model for a big VRP. The model is used in order to find an optimal way to load the orders in a vehicle. The computational cost for doing this double work would be really big, because it would basically run each problem twice. And I run each model many times for each vehicle. I think it would basically double my computational time, as it is the most time consuming process of the algorithm. Feb 7 '20 at 13:14

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.

• thank you for the answer. Unfortunately, I don't have a precedence issue. I don't care if a certain compartment is used before another. As you said, the compartments have different capacities, hence this isn't going to work, as an order could fit in a compartment $j$ bigger than $i$ Feb 7 '20 at 13:18

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.

• thanks for the answer. This is really helpful. I will try it out and return. Feb 7 '20 at 13:21
• I have already implemented something like the following: $$\sum_i\sum_j(c_{j}-y_{ij})+\sum_i\sum_j(j \cdot x_{ij})$$ where $x_{ij}$ is a decision variable that shows when order $i$ is in compartment $j$. Feb 7 '20 at 13:26
• Wouldn't your approach favor the rear compartments? The objective is to take advantage the front compartments. Hence your approach should be with a minus I guess. Feb 7 '20 at 13:52
• Yes you are right. You don't need to minus. You can use as (J-j) for j. J is number of j. Feb 7 '20 at 20:07