MIP Modeling

From this post:

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:

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.

It is possible to model this with a linear Mixed Integer Programming (MIP) model. I tried this quickly. The optimal solution is:

----     65 VARIABLE x.L  trade                t1          t2          t3          t4 Adam                                                1 Berta                                   1 Carl                        1 Dave            1 ----     65 VARIABLE y.L  number of trades (only integer multiples)                t1          t2          t3          t4 Adam                                                4 Berta                                   4 Carl                        4 Dave            1 ----     65 VARIABLE inv.L  current inventory               t1          t2          t3          t4          t5 wood                                               4           4 sand           4                       8 gras                       4

I.e. we visit Dave,Carl,Berta and Adam (in that sequence). The final inventory is 4 pieces of wood. In the fifth period we don't do anything.

The complete MIP model is below. It is built around an assignment problem structure, which makes sure we visit at most one dealer each period, and that we do not revisit dealers.

Extensions:

• The data for a trades can be fractional (1.3 grass for 2.4 wood).
• The multiples of a trade are in the model restricted to integers. We can easily allow any trade size > 0 by making y a continuous variable. We may need to change equation xy2 to \(y_{p,t} \ge 0.01 x_{p,t}\).
• We can easily apply limits on each trade, in the form of a capacity constraint. We already applied a fixed upper bound of 100 on each trade. This can be made part of the input instead (and can be made different for each trade).