1
$\begingroup$

As an analogy, lets say I have $k$ buckets and $n$ items I want to put into these buckets. So we have binary variables $x_{ij}$ ($1 \leq i \leq n$, $1 \leq j \leq k$), whether or not we put the $i^{th}$ item into the $j^{th}$ bucket. Each item has weight $W_{i}$ and volume $V_{i}$ and each bucket has the same weight limit $WL$ and volume limit $VL$. So I have constraints as follows:

$\sum W_i x_{i1} \leq WL$

.

.

.

$\sum W_i x_{ik} \leq WL$

and

$\sum V_i x_{i1} \leq VL$

.

.

.

$\sum V_i x_{ik} \leq VL$

and

$\sum x_{1j} = 1$

.

.

.

$\sum x_{nj} = 1$

Now I am trying to figure out the best objective function. I need a linear objective function that minimizes the number of containers I use (equivalent to minimizing the rank of the matrix $\{x_{ij}\}$, I believe) and a way to ensure the distribution of the items produces as close to uniform distribution of the weight across the chosen containers as possible.

My only idea currently is to simply find the minimum number of containers with one objective function, then run the linear program with another objective function (and a number of containers reduced to the minimum previously found) that ensures an approximately uniform distribution of the weight across the containers. My ideas for the objective functions are as follows:

Objective function to minimize containers:

$Min\{\sum_j \sum_i 10^{j-1} x_{i1}\}$

Objective function to minimize "variance" of weight:

$Min\{\sum_j | \frac{\sum_i W_i}{k} - \sum W_ix_{ij}|\}$

I understand that this second objective function isn't truly linear and I saw the trick here to convert an objective function with an absolute value into a linear objective function, but I am not entirely sure how/if that works with a sum (I haven't thought too hard about it but I have run out of time for this week, I'll still be keeping up with this question though).

Now, it was my choice to use linear programming in the first place, so if this is not a reasonable tool for this problem I am certainly open to any other ideas that are computationally reasonable, but I am mainly interested in finding a way to

  1. minimize the number of containers

  2. uniformly distribute the weight across the containers as much as possible

with the above constraints.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You can try introducing binary decision variables $y_j, j=1,\dots,k$ to model the decision of whether to "open" a bin or not ($y_j=1$ if bin $j$ is used, and $0$ otherwise).

Then, you can write your objective of minimizing the total number of containers as $$\min \sum_{j=1}^k y_j$$

...and you only need to link the binary variables to your weight and volume constraints by ensuring that you can fill up the container only if you've decided to use the container: $$ \sum_i V_i x_{ij} \le (VL)y_j, \forall j=1,\dots,k \\ \sum_i W_i x_{ij} \le (WL)y_j, \forall j=1,\dots,k.$$

You can also read on the Bin Packing Problem (BPP) for which various formulations exist.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.