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.
  • $\begingroup$ Do all items have to be shipped or you can refuse one which would cost more than its price ? Another point, your cost function is not continuous at 80g, is it intentional that 81g costs less than 79g ? $\endgroup$
    – Optidad
    May 12, 2019 at 20:44
  • $\begingroup$ @Vince all items have to be shipped. And yes, the rate structure is such that after a certain weight threshold, heavier packages become cheaper. $\endgroup$ May 12, 2019 at 20:47

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.