I'm trying to find literature on what I'm sure is a well-understood mathematical problem, but am struggling for terminology.

Let's say I have a number of items each of which is either shiny or matte, black or white, and heavy or light (e.g. a given item might be matte, black, and light). I also have customer orders for commodities that specify a number and specification (e.g. "I want 30 items that are black", "I want 12 items than are light and matte", "I want 10 items, regardless of their features").

My goal is to fill as much of each order as possible, and where several orders can be fulfilled by the same subset of available items - where they are, so to speak, competing for the same items - to give each order a share of the contested items proportional to the size of the order (i.e. items should be divided "fairly"). If it simplifies the problem, it is fine to allocate fractions of an item (an allocation of items to order need not be integer-valued).

Is there a name for such problems? How can they be solved? Linear programming, perhaps?

  • $\begingroup$ Have you seen any of the literature on fair division? This may be a little different than what you are looking for, but perhaps useful anyway. $\endgroup$ – Nate Eldredge Dec 24 '18 at 0:50
  • $\begingroup$ This is a linear programming problem. Just define variables for each of the 8 possible products. Set resource constraints. Add one more variable for the minimum fraction allocated to each order. I'm on mobile so can't write the details but any introductory book on linear program will have similar problems. $\endgroup$ – ericf Dec 27 '18 at 5:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.