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≤i≤m and 1≤j≤n 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˙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.