4
$\begingroup$

Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount a of good b for amount c of good d.

I have made a simple table to point out what I am trying to explain:

enter image description here

In this case there are three different goods: Wood, Sand and Gras.

I also live in the village and noticed that the prices of the traders vary greatly. I have 1 wood and want to increase it by simply trading between the five dealers. But: I must not visit a dealer more than once.

There would be different routes, for example I could do Dave - Adam, which would result in +1 wood for me. A better route would be Earl - Berta - Adam, because it would mean +2 wood.

I think at that point you might already know what I am asking for. I am looking for a technique / algorithm to find the route which maximizes my input. The rules are:

  • Input good = Output good
  • Output value > Input value
  • Each node ("dealer") must not be visited more than once
  • You do not have to visit all dealers
  • Each dealer is limited to one trade ("Giving amount a of good b for amount c of good d").
  • $a\in\mathbb{R}_{>0}$ and $c\in\mathbb{R}_{>0}$
  • The benefit is calculated at the end by output - input, i.e., by the increase in the quantity of the goods that you're starting with (if you start with 1 wood, then all that matters is the number of woods you end with).
  • It is important that the input good is the same as the output good ("Input good = Output good"). If I start with wood, I need to end with wood. If I start with sand, I need to end with sand, etc.

I don't even know how such a problem is called. That means that anything like algorithm names to solve it, the general name for this kind of problem, etc. would help me to continue with my research. I have already tried approaching it by converting the table to a graph and then run path-finding algorithms. That did not work, because I wasn't sure how to weight the edges and the Longest-Path-Problem was also in my way, which is NP-Hard for non-DAGs.


The traveling salesman problem (TSP) was already mentioned. I had a look at the Wiki page of the TSP. Quote: "The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" I think my problem is very different, because:

  1. I look for the most profitable route, not the shortest.
  2. I don't have to visit every dealer ("city").
  3. I must not return to the origin, because as I said each node ("dealer") must not be visited more than once.

The "village" can get quite big. About 200 different goods and 500 dealers, so the algorithm should be able to perform good in this scenario.

The last possibility would be to brute-force, but I really want to avoid that.

$\endgroup$
  • 1
    $\begingroup$ You might find this helpful: math.stackexchange.com/questions/94414/… $\endgroup$ – Denis Pankratov May 27 '16 at 21:02
  • 1
    $\begingroup$ 1. It's not finding negative cycles in a graph (intutively, here we have multiple currencies; also, we can use each dealer's offer only once), so that Math.SE question doesn't solve this problem and isn't applicable here. 2. Bobface, about how many dealers and how many goods do you have, in the real problem you face? This may determine what kinds of algorithms to suggest. $\endgroup$ – D.W. May 28 '16 at 0:27
  • $\begingroup$ @D.W. I'd say up to 200 goods and 500 dealers. It can get quite big. Thats why I want to avoid brute-force. $\endgroup$ – thesys May 28 '16 at 6:44
  • $\begingroup$ I never said that the link solves the question. IMHO, a suggestion does not have to solve the question directly in order to be applicable. Understanding formally how this question is different from arbitrage finding can lead to either modification of that algorithm or an argument why it's NP-hard. That's one of the principles of Polya for problem solving. I wasn't interested in seeing this approach through for this problem myself, that's why I left the suggestion for the OP. $\endgroup$ – Denis Pankratov May 28 '16 at 13:49
  • $\begingroup$ The problem is easily formulated as a MIP as it is not really a TSP (no difficulties associated with subtours). Here is the complete formulation. $\endgroup$ – Erwin Kalvelagen May 28 '16 at 17:43
2
$\begingroup$

This problem is NP-Complete by reduction from Directed Hamilton Path. I use the method of the linked mathoverflow answer. Let's say $b(v)$ and $s(v)$ is the good that villager $v$ buys and sells, respectively (each villager only buys/sells one good). Then you may ask, what dealers can I visit consequtively? This is the following graph:

$$G = \langle \text{Villagers}, \{ (\sigma, \beta) | s(\sigma)=b(\beta) \rangle $$

This directed graph has an edge from $\sigma$ to $\beta$ iff $\sigma$ sells something that $\beta$ buys (using the letters $\sigma$ and $\beta$ because they sound like 's' and 'b' for seller and buyer). In this graph, you are one node called $y$ and you have a good, $s(y)$, which you want to sell. You can verify that you are looking for a route through $G$. How much profit do you make? If $\$_b(v)$ and $\$_s(v)$ are the buying and selling price of villager $v$'s goods, and you travel some route $v_1\cdots v_k$ through the village, then your profit is: (w.l.o.g. assume that you start with $1$ unit of your good)

$$ \text{Profit}(v_1\cdots v_k) = \prod_{i=1}^{k}\frac{\$_s(v_i)}{\$_b(v_i)}$$

This suffices for a reduction from Directed Hamilton Path: Take a directed graph $H=\langle V, E \rangle$, and say you want to find out whether there is a Hamilton Path starting in vertex $x$. Suppose that the $n$ vertices are villagers. Each villager $v_i$ trades his own good for his own good at a $1/1$ ratio. Now populate the village further as follows. For each edge $(\sigma,\beta)\in E$ in the graph, add a "stockbroker" villager called $\tau_{\sigma,\beta}$ who buys $\sigma$'s goods and sells the goods that $\beta$ buys at a rate of two units of $\beta$ for each unit of $\sigma$. That is, $b(\tau_{\sigma,\beta})=s(\sigma)$ and $s(\tau_{\sigma,\beta})=b(\beta)$ at $\$_b(\tau_{\sigma,\beta})=1$ and $\$_s(\tau_{\sigma,\beta})=2$. In this scenario, you are villager $x$.

If your profit problem were easy, then you could ask 'Is there a route from $x$ which makes $2^{n-1}$ profit?' Iff there is such a route in the graph I constructed, then there is a Hamilton Path in the graph I constructed it from. $\square$

So this problem is NP-Complete and in fact it is hard even to approximate. Instances of the problem that are not contrived are probably more difficult. You can also make an elegant reduction from Traveling Salesman by assigning to each villager a profit $\varepsilon(v_i)=\log\left(\frac{\$_s(v_i)}{\$_b(v_i)}\right)$, I'll leave the details up to you. If you really mean to solve this problem practically, you can look for some advice in this question here (link) and in the extensive literature on TSP and related problems. Personally, I would use a greedy algorithm which looks ahead some fixed number of steps, say $3$ steps. Or you can use an evolutionary approach, which should work just fine, too.

Here's one heuristic: given a candidate solution $v_1\cdots v_k$ computed by an evolutionary algorithm, you can check the intermediate profits halfway along the route, and quickly find the point at which you should have stopped. Fix only the last part of the path $v_j\cdots v_k$.

$\endgroup$
  • $\begingroup$ The proposed reduction doesn't work. Your formula for the profit isn't quite right. You seem to have overlooked the requirement "Each dealer is limited to one trade". Earl will give 3 grass for 1 wood; Berta will give 2 sand for 1 grass; but that doesn't mean I can turn 1 wood into 6 sand by visiting Earl then Berta. Instead, I end up with 2 grass and 2 sand. As a result, the reduction fails. $\endgroup$ – D.W. May 28 '16 at 14:43
  • $\begingroup$ @D.W. I see, I think you're right. I assumed that whereas each dealer is limited to one visit, he has unbounded stock of what he is selling, but I think your interpretation of the OP's question is more accurate. I will think of how to fix the reduction. $\endgroup$ – Lieuwe Vinkhuijzen May 28 '16 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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