# 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 '20 at 11:51