6
$\begingroup$

A toy problem would probably be best to explain it this. Let's say we have 100 people, each with 4 unique types of items (to simplify things, let's say it's the same four types of items for each person). For each of these people, they have a different number of each item type they need.

So for person one they have items {i1 = 10, i2 = 4, i3 = 6, i4 = 20}, and they need {n1 = 6, n2 = 7, n3 = 8, n4 = 15} respectively for those 4 items .

For person two, they have {i1 = 0, i2 = 5, i3 = 5, i4 = 10} and they need {n1 = 0, n2 = 6, n3 = 10, n4 = 14}, respectively.

For person three, they have {i1 = 50, i2 = 6, i3 = 6, i4 = 5} and they need {n1 = 55, n2 = 2, n3 = 5, n4 = 5}, respectively.

And so on up to person 100.

I'm looking for an algorithm to suggest which goods should be traded between these 100 people such that a global optimal state is reached (overall needs are optimally met). One such trade (of many) that the algorithm would make is suggesting that person 1 sell 4 units of item 1 to person 3. This way, globally, need is better met.

The soft constraint is we minimize the total number of trades (can't do unlimited number of trades). Do you know the name for this sort of optimization problem. Are there any algorithm names you can recommend? Even better yet, are there any open source libraries to handle this type of optimization you are aware of?

Thanks!

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 90% sure you can write this as a maximal matching problem with some extra (linear) constraints, or equivalently as a max flow problem with extra constraints. In either case, this can be solved via linear programming (relaxation is tight by unimodularity.) $\endgroup$
    – cdipaolo
    Commented Aug 23, 2019 at 16:13
  • 1
    $\begingroup$ Are the items divisible into fractional items? Are you trying to minimize the number of times items are traded or the number of times agents meet to trade? Is there an upper limit on the number of items an agent can hold? $\endgroup$
    – Richard
    Commented Aug 23, 2019 at 16:59
  • $\begingroup$ Thanks @cdipaolo, I'll look into "maximal matching problems". $\endgroup$
    – Slyron
    Commented Aug 23, 2019 at 17:34
  • $\begingroup$ @Richard the items aren't divisible into fractions. To clarify, I'm trying to minimize the number of times agents meet to trade, good call out there. There isn't an upper limit on the number of items an agent can hold. I should have mentioned this before, but there should be some kind of fairness constraint (don't want the first 50 people fully met and the remaining 50 hardly met). $\endgroup$
    – Slyron
    Commented Aug 23, 2019 at 17:34
  • 1
    $\begingroup$ @Slyron: Not sure if it's useful to you, but, if there's not an upper limit on holdings, there's a trivial upper bound on the number of trades of ~2N. Everyone gives all their goods to an arbitrarily chosen agent. Everyone then receives goods from the same agent. This also illustrates while a maximal matching problem probably won't work here: any time you can turn a fully-connected clique of trades into a two-stage star you no longer have a matching problem. $\endgroup$
    – Richard
    Commented Aug 23, 2019 at 17:45

1 Answer 1

Reset to default
5
$\begingroup$

This is no doubt an Optimal Transportation problem.

Optimal Transportation aka. Transportation theory mainly talks about how to allocate resources within minimal cost.

You can search for related books, blogs or simply start from the wiki page.

Also, the problem is a Linear Programming problem, or more specifically Integer Programming problem since the desired transportation plan is integer. Moreover, if the objective is to minimize the total number of transactions, the problem can be degraded into a 0-1 Binary Integer Programming problem.

Besides, since different items cannot exchange, once the transport algorithm for one item is established, your entire problem will be solved by applying the algorithm on each kind of items independently.

One more thing to mention, "Binary Programming Problem" is among the Karp's 21 NP-complete problems, which means brute-force searching and heuristic methods are perhaps the best approaches we have for now in order to obtain the optimal solution.

Lingo, an optimization solving software with matlab-like command-line interface, can be used to search for a near-optimal feasible solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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