Optimization trading items - min cost max flow

Question

There is n items, . I have n items, but some duplicates and some are missing, I need to have exactly one of each item. There is given a trade-table that tells which items can be traded for others. For example:

Item	Item For
1	2
2	5
4	3

There is infinite stock of trade items in trade-table. But for each trade, you need to pay 1$.

Now we want to know which items to trade so that in the end we have each item exactly once and we minimize needed trades (cost). And if it's not possible then we should detect that it is not possible.

Example:

, we have and the trade-table is: . We need to trade 2x i1 to i2 and 1x i2 to i3.

Solve the problem using max flow min cost algorithm. I'm not in particular interested in time complexity.

How do I construct the graph/flow network?

Answer 1

How do I construct the graph/flow network?

Such a network needs sources. The sources are the duplicate items. The output from each source has a capacity equal to the number of spares ( count - 1 )

The network needs sinks. The missing items are the sinks. The input to each sink has a capacity if 1

The trade table provides the rest of the links, each with an infinite capacity.

So, for your example,

Apply the Edmonds-Karp algorithm to get your answer https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm Note that is convenient to have just one source and once sink, so connect a common source to all item sources and all the item sinks to a common sink.

The problem is not feasible if the calculated flow into any sink is zero

The total cost is the total calculated flow through the internal links ( all graph links NOT connected to a source or a sink )

---

FYI here is some C++ code that solves this problem using the above algorithm and the PathFinder graph theory library

Construct the example:

void generate1()
{
    // initial holding of each item
    cHold::add("1", 3);
    cHold::add("2", 0);
    cHold::add("3", 0);
    cHold::add("4", 1);

    // possible trades
    cTrade::add("2", "1");
    cTrade::add("3", "2");
}

Construct the graph/flow network

void cFlowGraph::make()
{
    // setup flow graph
    gd.g.clear();
    gd.g.directed();

    // setup link capacity storage
    int maxLinkCount = cItem::count() * cItem::count();
    const int infinite = 2e9;
    gd.edgeWeight.resize(maxLinkCount, infinite);

   
    for (cHold *hold : cHold::get())
    {
        if (hold->count() > 1)
        {
            // source
            // create links from holdings with spare items into trading graph
            std::string name = "source_" + hold->name();
            gd.g.add(
                "all_source",
                name);
            int ie = gd.g.add(
                name,
                hold->name());
            gd.edgeWeight[ie] = hold->count() - 1;
        }
        else if (!hold->count())
        {
            // sink
            // create links from trading graph to empty holdings
            int ie = gd.g.add(
                hold->name(),
                "sink_" + hold->name());
            gd.edgeWeight[ie] = 1;
            gd.g.add(
                "sink_" + hold->name(),
                "all_sink");
        }
    }

    // create the trading links
    for (cTrade *trade : cTrade::get())
    {
        gd.g.add(
            trade->giveName(),
            trade->getName());
    }
}

Calculate the flows through the graph

void cFlowGraph::calculate()
{
    vLinkFlow.clear();
    vLinkFlow.resize(gd.g.edgeCount(), 0);
    gd.startName = "all_source";
    gd.endName = "all_sink";

    //Apply Edmonds-Karp algorithm using Pathfinder method
    flows(
        gd,
        vLinkFlow);

    displayLinks();
}

Check feasability:

bool cFlowGraph::isFeasible()
{
    // check that every flow into an item sink is 1
    // meaning that the missing item was found
    for (auto &link : gd.g.edgeList())
    {
        if (gd.g.userName(link.second).find("sink_") == 0)
            if (flow( link ) != 1)
                return false;
    }
    return true;
}

Display required trades

void cFlowGraph::displayTrades()
{
    std::cout << "\n";
    for (auto &link : gd.g.edgeList())
    {
        if (isTrade(link))
            std::cout << "trade " << gd.g.userName(link.first)
                      << " - > " << gd.g.userName(link.second)
                      << " times " << flow( link )
                      << "\n";
    }
}

Put this all together and the output is

 flow 2 in   all_source -> source_1
 flow 2 in     source_1 -> 1
 flow 2 in            1 -> 2
 flow 1 in            2 -> sink_2
 flow 1 in            2 -> 3
 flow 1 in       sink_2 -> all_sink
 flow 1 in            3 -> sink_3
 flow 1 in       sink_3 -> all_sink

trade 1 - > 2 times 2
trade 2 - > 3 times 1

The complete application code is at https://github.com/JamesBremner/trader