I am looking for an analogy to the problem I am facing or better yet a paper or even code.
I have:
Nodes from set A and B.
Edges are from a single A to many B.
I am framing a max bipartite matching problem where the edge weights change at thresholds. If I have 9 edges between a single node in A and 9 nodes of B, and then a new edge is incorporated into that node A, all of its edge weights should be discounted by a factor.
I am having some trouble with finding relevant literature about this problem.
My objective function is a shopper wanting to purchase as many things that they can to make them happy
while minimizing the cost
of the order. Happiness can be a function of the full set of items. Some customers might be happier with a diverse set of products, some just want one thing.
They make a purchase where prices change depending on the composition of the items ordered. In my case there is a discount
given for buying more than a number of items in a certain category
.
A shopper has a utility for any given item and the store is offering discounts for certain families of items. e.g. buy 5 chocolate bars and get a dollar off.
So I can buy 4 Hershey's bars and it's $5.
But if I buy 4 Hershey's bars and a snickers (extra 80 cents), I can get the whole set of candy bars for $1 off and be better off in terms of me being more happy and paying less.
Limits:
There are <100 A nodes. (Shopper)
There are < 10,000 B nodes (Items)
There should be a max of 3 discount factors for 3 categories of items (total of 9). e.g. -
More than 5 candy bars --> Get 1 free
More than 50 candy bars --> Get 5 free
More than 100 candy bars --> Get some other item for free
More than 2 cases of soda --> get one free
More than 10 cases of soda --> get 4 free
More than 20 cases of soda --> get 6 free
Any node will have a maximum degree of ~1000.