# Writing a linear program to model balanced bin packing

Say we want to write a (MI)LP to model the following problem:

Find a parking plan for a set of cars $$K=\{1, ..., k\}$$ with lengths $$\lambda_i$$. Parking is organised in lanes $$P=\{1, ..., p\}$$. The length of a lane is the sum of the cars parking there and may not exceed a specified constant $$L$$. The goal is to balance the lengths of the parking lanes as well as possible. More specifically, we want to minimise the difference of the length of a longest and shortest line.

To me, this seems quite akin to some variant of the Bin Packing problem. Usually, however, we want the number used bins to be minimised.

Here, I am quite confused on how I could come up with an objective function that expresses the balance between the lanes/bins. My main problem is that -- as far as I understood it -- the objective function has to be linear. Thus, I couldn't use operations like max, min, absolute value etc.

Can someone help me out here with a hint?

Define a variable $$b$$ that represents the imbalance between the lengths of the parking lanes. For instance, if $$b=5$$, that means that the lengths of every pair of parking lanes differs by at most 5. Define other variables to represent the lengths of the parking lanes.

Write constraints to enforce that $$b$$ is set consistently with your other variables.

Minimize $$b$$.

• I was confused about how to describe that imbalance between the parking lanes as I cannot use an absolute value operator (which I thought I needed so that the imbalanc values do not become negative). But I think it should suffice to define the imbalance beween lanes $d_{ij}$ as the difference between the two lengths and then require $d_{ij} \leq b$ and $d_{ij} \geq -b$, right? Jan 19, 2020 at 11:51

Not exactly what you asked, but if you define $$b$$ as the maximum length reached, you can minimize $$b$$ and get something similar to what you desire.

Let's say that $$X_p$$ is a variable that represents the number of cars parked in lane $$p$$. So, you could add constraints like:

$$b \geq X_p, \forall p \in P$$

If you minimize $$b$$, and there is no other constraint that avoids that, the minimum value of $$b$$ is the value than minimizes the difference across lanes.