Minimize shipping cost based on weight and price constraints

Question

I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows:

1. There is a limit on the max price of the combined package (say $15)
2. The cost of the package is determined using the following table:
   1. If total weight of package is < 30 grams, cost is 7.5
   2. If total weight of package is >= 30g and <80g, cost is 7.5 + (weight - 30)x0.075
   3. If total weight of package is >= 80g, cost is 7.5 + (weight - 30)x0.055

There is no limitation on the number of packages these items can be combined into as long they remain under the total price threshold.

I looked at the knapsack problem, but there are 2 major differences between the knapsack problem and my problem:

1. One is that we are not maximizing the weight or price of the items combined, instead we want to minimize a calculated variable that can only be determined after the combination.
2. Also, there isn't a direct correlation between weight and shipping cost.

Answer 1

Since the objective function is piecewise linear, the problem can be formulated as an integer linear program.

Given items with prizes $p_1,\ldots,p_n$ and weights $w_1,\ldots,w_n$, define binary variables $x_i$ for $i\in[n]$ where $x_i=1$ if item $i$ selected. For each of the three segments a binary variable $\delta_k$ selects the active segment, and the convex combination of $(\lambda_1,\lambda_2)$, $(\lambda_2,\lambda_3)$, or $(\lambda_4,\lambda_5)$ defines the point in the first, second, or third segment, respectively. Note that $\lambda_3=1$ and $\lambda_4=1$ are different, since your objective function is not continuous at $80$. Auxiliary variables $w$ and $c$ hold the total weight and cost. Finally $W=\sum_{i\in[n]} w_i$ is an upper bound on the maximum weight.

With this you can \begin{align} \text{min.}\quad & c,\\ \text{s.t.}\quad & \delta_1 + \delta_2 + \delta_3 = 1,\\ & \lambda_1+\lambda_2 = \delta_1,\\ & \lambda_2+\lambda_3 = \delta_2,\\ & \lambda_4+\lambda_5 = \delta_3,\\ & w = 30\lambda_2+80(\lambda_3+\lambda_4)+W\lambda_5,\\ & c = 7.5\lambda_1+7.5\lambda_2+11.25\lambda_3+10.25\lambda_4+(7.5+0.055(W-30))\lambda_5,\\ & \sum_{i\in[n]} p_ix_i \leq 15,\\ & \sum_{i\in[n]} w_ix_i = w,\\ & x_i\in\{0,1\}, i\in[n],\\ & \delta_1,\delta_2,\delta_3\in\{0,1\},\\ & \lambda_1,\lambda_2,\lambda_3,\lambda_4,\lambda_5\geq 0,\\ & w,c\geq 0. \end{align}

For, say, about 100 items I guess a standard solver can find the optimal solution in a few minutes.

(From your question it is not clear me if you want to select a subset of the items that can be sent at optimal cost, or minimize the total cost for all packages to send all items. For the latter you can extend the model by using variables $x_{ij}$ that indicate if item $i$ goes to the $j$th package, use similar constraints to define the cost for each package, and then minimize the total cost.)