Packing problem

224,130pages on
this wiki
Add New Page
Discuss this page0 Share

The applied mathematics of optimizing market baskets using information in efficient shopping list's involves what have come to be known as packing problems.

Here we will attempt to formalize one type of packing problem of interest to the pub wan movement, that of optimizing a market basket of packaged edible goods according to a norm spec à la sample grocery normspec.

Let's assume we have m product packages to choose from, and n nutrients (or chemical constituents) that have been tabulated for the m products in question. Then for each 1≤im and 1≤jn we have the following vectors and matrix:

  • q, where qi is the (non-negative integer) quantity of product i in the market basket.
  • p, where pi is the price of package i.
  • C, where cij is the amount (in kg) of nutrient/constituent j in package i.
  • m, where mj is the maxhi schema norm spec for constituent j. Numerically, minhi is -2/3, minlo is -1/3, nullo (or not specified) is 0, maxlo is 1/3 and maxhi is 2/3.

We would like to establish a vector b, where bj is the total amount of constituent j in the market basket. This is the product q N. The price P of the entire basket is the dot product p&dot;q. The vector m of maxhi parameters allows us the convenience of treating all parameters as maximized, thus if b and m of a given market basket are represented as lists in lisp, a list of expressions in the form <example> (cons (- P) (mapcar #'* b m)) </example> can be fed to the function <example> nondom </example> in dom.lsp to identify the Pareto nondominated subset of a set of market baskets.

The remaining problem, as always with packing problems, is to find efficient ways of negotiating the unmanageable combinatorial space represented by the actual consumer marketplace.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.