2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hexaly
    Commented Nov 18, 2020 at 14:18
  • 1
    $\begingroup$ 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). $\endgroup$
    – prubin ♦
    Commented Nov 18, 2020 at 23:38
  • $\begingroup$ @LocalSolver updated $\endgroup$
    – Anisotropic
    Commented Nov 18, 2020 at 23:44
  • $\begingroup$ Thanks for the update, @Anisotrropic. Your problem is much clearer now. $\endgroup$
    – Hexaly
    Commented Nov 19, 2020 at 14:17

1 Answer 1

Reset to default
2
$\begingroup$

Since the discount function is arbitrary, it is difficult to reduce it to a maximum matching problem in a bipartite graph. On the other hand, your problem can be viewed as a set cover problem, having enumerated all the subsets of items the shopper can buy. For each feasible subset, you can compute the utility and the discounted price. Then the shopper wants to pick subsets of items in such a way to reach a certain level of overall utility while minimizing the overall price.

A client of ours was interested in the same problem as you. He modeled the problem as described above. Then the main difficulty in solving the problem efficiently in practice comes from the huge number of feasible subsets to enumerate and then the size of the resulting set cover problem to solve.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.