Entropic Decision Optimization using Amazon's Add-on Item Constraint

When we shop at Amazon, we often end up with about 23-24$ worth of stuff in our cart, short of the 25$ threshold that gives us free shipping. As far as I could remember, we could always add small items (like a box of paper-clips) to satisfy this knapsack constraint. In other words, we could reasonably approximate this discrete threshold satisfaction problem as a continuous knapsack constraint, which is amenable to "greedy" approaches.

A Tougher Knapsack Problem
Amazon has now designated many items whose values are roughly $5 or less, to be "add on" items, and is marketed as follows:
"The new Add-on program allows Amazon to offer thousands of items at a low price point that would be cost-prohibitive to ship on their own... Add-on Items ship with orders that include $25 or more of items shipped by Amazon, and you can get them delivered to your doorstep with free shipping ....Previously it was only possible for us to offer many of the items like these in large multi-pack sizes... "

Speaking purely from a personal point of view, it feels like this "benefit" actually hurts customers by placing additional restrictions (on the other hand, there may well be an incremental benefit to a section of customers) since such low-priced items cannot be used to satisfy our knapsack constraint, and we may end up purchasing a bit more than the 25-26$ we achieved before, or pay for shipping. This new 'add on item' constraint requires us to solve a discrete knapsack problem to best satisfy the free-shipping threshold. Although NP-Hard in theory, it is well-known that we can find optimal or near-optimal solutions to practical integer knapsack problems in quick time using specialized algorithms.

Entropic Decision Optimization (EDO)
This add-on constraint can be used to illustrate the EDO approach that we discussed just a couple of days ago. Consider the following heuristic algorithm:

Start with a super-set of items (wish list) we intend to purchase over the next few weeks/months. This list is constantly updated over time. Any time we want to make a purchase, assign a priority score to each item that is positively correlated with the time-sensitivity of its purchase (an item that we 'must' purchase right away goes directly into the cart). Then solve the following integer knapsack problem:

Maximize (sum of scores of chosen items)
subject to:
1) sum($ value of chosen items) ≤ 30
2) Bounds on the quantity of purchase of each item.

We picked 30$ as the RHS assuming that we can easily find a 30$ or higher-valued basket using our old "continuous" approximation. If we use a dynamic programming approach, we also get as a by-product, the solutions for a range of RHS values less than $30. Pick the solution corresponding to the smallest capacity at or exceeding $25. If we have very few choices, we can simply enumerate the possibilities.

We chose as a measure of "entropy" in our super set, the total time-sensitivity of super set, and selecting relatively time-critical items reduces entropy. Our EDO algorithm will usually do a good job of limiting the entropy in our wish list, but over time we may end up with quite a few "hot" items that never seem to fit the knapsack well and kept getting rejected, indicating that our list has reached a state of high entropy. We are forced to make suboptimal choices and stray far away from the optimal $25 target. It does feel like we are playing Tetris.