# Maximum bipartite matching with breakpoints in edge weight function

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.

• Hello @Anisotropic. Welcome to OR SE. Could you be more specific in the definition of the objective function of your maximum matching problem? Thank you very much in advance. Nov 18, 2020 at 14:18
• It would help to know (approximately) how many discount factors (including 1.0 for the undiscounted case) you have, the maximum number of edges incident at any node in A, and the cardinality of A (to get a sense of whether a model is likely to be computationally tractable).
– prubin
Nov 18, 2020 at 23:38
• @LocalSolver updated Nov 18, 2020 at 23:44
• Thanks for the update, @Anisotrropic. Your problem is much clearer now. Nov 19, 2020 at 14:17