Implementation of Auction Algorthm via Boost Graph Library C++

Question

As I cited in previous question:

Is it possible to generate multiple custom vertices using the Bundle Properties from Boost Graph Library?
Boost Maximum Weighted Matching in undirected bipartite random graphs hangs in an infinite loop

I'm working on an application benchmark that compare the performance of the boost maximum weighted matching and auction algorithm for the transportation problem on solving the assignment problem for bipartite graphs.

Currently I've implemented a version of the auction algorithm using the bundle proprieties of boost graph library, this implementation is inspired by a vector version from github. I've done this in order to put on the same level both algorithms, to make a fair benchmark. Here it is:

#include "../include/Auction.h"
#include "../include/BipartiteGraph.h"

void auction_algorithm(Graph& graph, const int& n, duration& elapsed) {
    const Weight eps = 1;
    int unassigned_bidders = n;
    GraphProp& gp = graph[boost::graph_bundle];

    EdgeFilter any_interconnect = boost::keep_all{};
    VertexFilter bidders = [graph](V v) -> bool { return boost::get<Bidder>(&(graph)[v]); };
    VertexFilter items = [graph](V v) -> bool { return boost::get<Item>(&(graph)[v]); };

    FMap map_bidders = FMap(graph, any_interconnect, bidders);
    FMap map_items = FMap(graph, any_interconnect, items);    
    
    auto iterator_bidder = boost::make_iterator_range(boost::vertices(map_bidders));
    auto iterator_item = boost::make_iterator_range(boost::vertices(map_items));
    auto t_start = now();

    while (unassigned_bidders > 0) {

        for (auto uncasted_bidder : iterator_bidder) {
            if (gp.bidder2item[static_cast<int>(uncasted_bidder)] != -1) continue;
            Bidder* bidder = boost::get<Bidder>(&graph[uncasted_bidder]);

            
            // 1 Bid

            int id_item1 = -1;
            Weight val_item1 = -1;
            Weight val_item2 = -1;

            for (auto uncasted_item : iterator_item) {
                Item* item = boost::get<Item>(&graph[static_cast<int>(uncasted_item)]);
                Weight val = boost::get(boost::edge_weight_t(), graph, (boost::edge(uncasted_bidder, uncasted_item, graph)).first) - item->cost;

                if (val > val_item1) {
                    val_item2 = val_item1;
                    val_item1 = val;
                    id_item1 = item->id;
                }
                else if (val > val_item2) {
                    val_item2 = val;
                }
            }

            bidder->best_item = id_item1 + n;
            bidder->val_first_best_item = val_item1;
            bidder->val_second_best_item = val_item2;


            // 2 Compete

            Weight bid = bidder->val_first_best_item - bidder->val_second_best_item + eps;
            auto best_item = boost::get<Item>(&graph[bidder->best_item]);
            if (bid > best_item->high_bid) {
                best_item->high_bid = bid;
                best_item->high_bidder = bidder->id;
            }

        }


        // 3 Assign

        for (auto uncasted_item : iterator_item) {
            Item* item = boost::get<Item>(&graph[uncasted_item]);
            if (item->high_bid == -1) continue;

            item->cost += item->high_bid;

            if (gp.item2bidder[item->id] != -1) {
                gp.bidder2item[gp.item2bidder[item->id]] = -1;
                unassigned_bidders++;
            }

            gp.item2bidder[item->id] = item->high_bidder;
            gp.bidder2item[gp.item2bidder[item->id]] = item->id;
            unassigned_bidders--;
        }
    
    }

    elapsed = now() - t_start;
}



Weight perform_au(Graph& graph, duration& elapsed) {
    int n = int(boost::num_vertices(graph) / 2);
    Weight total_cost_auction = 0;

    auction_algorithm(graph, n, elapsed);

    std::cout << "\nThe matching is: ";
    for (int bidder = 0; bidder < n; ++bidder) {
        std::cout << "(" << bidder << "," << graph[boost::graph_bundle].bidder2item[bidder] << ")";
        int item = graph[boost::graph_bundle].bidder2item[bidder];
        total_cost_auction += boost::get(boost::edge_weight_t(), graph, (boost::edge(bidder, item + n, graph)).first);
    }
    std::cout << "\n";
    return total_cost_auction;
}

I have compared this to the vector implementation and notice that the latter is much faster than mine (however they return the same amount of total cost). Is it due to the complexity of the boost::get? If so, why is it so heavy?

I'm using the g++ compiler on a Ubuntu machine and to compile the application I run the following line in my console:

g++ -std=c++2a -o ../bin/app BipartiteGraph.cpp MaximumWeightedMatching.cpp Auction.cpp AuctionArray.cpp Main.cpp

I share the link of my github repository so you can have a look at the whole project.

PS: If you have any suggestions for speeding up the algorithm, that would be great!

UPDATE: 09/08/2022

Requirement: Make the auction algorithm generic like the style of the Boost Graph Library. This is the last implementation that I've made.

UPDATE: 10/08/2022

I've made a class that maintain the all stuff like it was before with the Bundle Properties:

UPDATE: 14/08/2022

Actual version

Weight perform_au(const Graph& graph, Duration& elapsed, int& n_iteration_au, bool verbose)
{
    int n = int(boost::num_vertices(graph) / 2);
    std::vector<int> assignments(n);

    Auction<Graph, Weight> auction_problem(n);
    auto t_start = now();
    auction_problem.auction_algorithm(graph, assignments);
    elapsed = now() - t_start;

    std::cout << " Finished \nThe matching is: ";
    for (int bidder = 0; bidder < n; ++bidder)
        std::cout << "(" << bidder << "," << assignments[bidder] << ")";
    std::cout << "\n";

    if (verbose) auction_problem.printProprieties();
    n_iteration_au = auction_problem.getNIterationAu();

    return auction_problem.getTotalCost(graph);
}



#ifndef _AA_H
#define _AA_H

#include <vector>
#include <unordered_map>
#include <boost/graph/adjacency_list.hpp>


template<typename T>
using AdjacencyIterator = boost::graph_traits<T>::adjacency_iterator;


template<typename Graph, typename Type>
class Auction
{
    private:
        struct Bidder {
            int best_item = -1;
            double val_first_best_item = -1;
            double val_second_best_item = -1;
        };

        struct Item {
            double cost = 0;
            int high_bidder = -1;
            double high_bid = -1;
        };

        int n_iteration_au = 0;
        int vertices = 0;

        std::unordered_map<int, Bidder> unassigned_bidder;
        std::unordered_map<int, Bidder> assigned_bidder;
        std::unordered_map<int, Item> item_map;
        
        bool is_assignment_problem(const Graph& graph);
        void auctionRound(const Graph& graph, const double& eps, const auto& vertex_idMap);
        
    public:
        void auction_algorithm(const Graph& graph, std::vector<int>& ass);
        int getNIterationAu();
        Type getTotalCost(const Graph& graph);
        void printProprieties();
        Type getMaximumEdge(const Graph& graph);
        void reset();

        Auction(int vertices)
        {
            this->vertices = vertices;
            for (int i : boost::irange(0, vertices))
            {
                this->unassigned_bidder.insert(std::make_pair(i, Bidder{}));
                this->item_map.insert(std::make_pair(i, Item{}));
            }
        }
};


template<typename Graph, typename Type>
inline int Auction<Graph, Type>::getNIterationAu() { return n_iteration_au; }


template<typename Graph, typename Type>
Type Auction<Graph, Type>::getMaximumEdge(const Graph& graph)
{
    Type max = 0;
    typedef boost::graph_traits<Graph>::edge_iterator edge_iterator;

    std::pair<edge_iterator, edge_iterator> ei = boost::edges(graph);
    for (edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter)
        if (boost::get(boost::edge_weight_t(), graph, *edge_iter) > max)
            max = boost::get(boost::edge_weight_t(), graph, *edge_iter);
        
    return max;
}


template<typename Graph, typename Type>
inline Type Auction<Graph, Type>::getTotalCost(const Graph& graph)
{
    Type total_cost_auction = 0;
    for (int bidder = 0; bidder < vertices; ++bidder) 
        total_cost_auction += boost::get(boost::edge_weight_t(), graph, (boost::edge(bidder, assigned_bidder[bidder].best_item + vertices, graph)).first);
    return total_cost_auction;
}


template<typename Graph, typename Type>
bool Auction<Graph, Type>::is_assignment_problem(const Graph& graph)
{
    for (auto v1 : boost::make_iterator_range(boost::vertices(graph)))
    {
        AdjacencyIterator<Graph> ai, a_end;
        boost::tie(ai, a_end) = boost::adjacent_vertices(v1, graph);
        if (ai == a_end) return false;
        else
            for (auto v2 : boost::make_iterator_range(ai, a_end))
                if ((v1 < vertices && v2 < vertices) || (v1 > vertices && v2 > vertices))
                    return false;
    }

    return true;
}


template<typename Graph, typename Type>
inline void Auction<Graph, Type>::printProprieties()
{
    for (auto& bidder : assigned_bidder)
        std::cout << "|Bidder:" << bidder.first << "|Best item:" << bidder.second.best_item << "|Value first best item:" << bidder.second.val_first_best_item << "|Value second best item:" << bidder.second.val_second_best_item << "|\n";
    for (auto& item : item_map)
        std::cout << "|Item:" << item.first << "|Cost:" << item.second.cost << "|Higher bidder:" << item.second.high_bidder << "|Higher bid:" << item.second.high_bid << "|\n";
}


template<typename Graph, typename Type>
void Auction<Graph, Type>::auctionRound(const Graph& graph, const double& eps, const auto& vertex_idMap)
{
    for (auto& bidder : unassigned_bidder)
    {

        int id_item1 = -1;
        double val_item1 = -1;
        double val_item2 = -1;

        AdjacencyIterator<Graph> ai, a_end;
        boost::tie(ai, a_end) = boost::adjacent_vertices(vertex_idMap[bidder.first], graph);

        for (auto item : boost::make_iterator_range(ai, a_end)) // itero iniziando da quelli che hanno meno vertici?
        {
            double val = (boost::get(boost::edge_weight_t(), graph, (boost::edge(bidder.first, static_cast<int>(item), graph)).first)) // * (vertices))
                - item_map[static_cast<int>(item) - vertices].cost;
            if (val > val_item1)
            {
                val_item2 = val_item1;
                val_item1 = val;
                id_item1 = static_cast<int>(item) - vertices;
            }
            else if (val > val_item2) val_item2 = val;
        }

        bidder.second.best_item = id_item1;
        bidder.second.val_second_best_item = val_item2;
        bidder.second.val_first_best_item = val_item1;

        double bid = bidder.second.val_first_best_item - bidder.second.val_second_best_item + eps;

        if (item_map.find(bidder.second.best_item) != item_map.end())
        {
            if (bid > item_map[bidder.second.best_item].high_bid)
            {
                item_map[bidder.second.best_item].high_bid = bid;
                item_map[bidder.second.best_item].high_bidder = bidder.first;
            }
        }

    }
    
    for (auto& item : item_map)
    {
        if (item.second.high_bid == -1) continue;

        item.second.cost += item.second.high_bid;
        int id_to_remove = -1;

        for (auto& ass_bidr : assigned_bidder)
        {
            if (ass_bidr.second.best_item == item.first)
            {
                id_to_remove = ass_bidr.first;
                break;
            }
        } 
                
        if (id_to_remove != -1)
        {
            unassigned_bidder.insert(std::make_pair(id_to_remove, assigned_bidder[id_to_remove]));
            assigned_bidder.erase(id_to_remove);
        }

        assigned_bidder.insert(std::make_pair(item.second.high_bidder, unassigned_bidder[item.second.high_bidder]));
        unassigned_bidder.erase(item.second.high_bidder);

    }
}


template<typename Graph, typename Type>
void Auction<Graph, Type>::auction_algorithm(const Graph& graph, std::vector<int>& ass)
{
    if (!is_assignment_problem(graph)) throw("Not an assignment problem");

    auto vertex_idMap = boost::get(boost::vertex_index, graph);


    double eps = static_cast<double>(1.0 / (vertices + 1));


        while (unassigned_bidder.size() > 0)
        {
            auctionRound(graph, eps, vertex_idMap);

            n_iteration_au += 1;
        }

    for (auto& a : assigned_bidder) ass[a.first] = a.second.best_item;

}

#endif

All questions concerning the speed of a C++ program should be accompanied by 1) Compiler used, 2) Compiler optimizations used when building the application. If you are running an unoptimized or "debug" build, then whatever timing information you are gathering is basically meaningless. — PaulMcKenzie, Jul 28 '22 at 08:17

sehe · Accepted Answer · 2022-07-28T17:08:39.187

0

Why would it not be heavy.

Again,

FMap map_bidders = FMap(graph, any_interconnect, bidders);
FMap map_items = FMap(graph, any_interconnect, items);

Just "wishing" things to be a property map doesn't make them so.

Also, your filter predicates:

EdgeFilter any_interconnect = boost::keep_all{};
VertexFilter bidders = [graph](V v) -> bool { return boost::get<Bidder>(&(graph)[v]); };
VertexFilter items = [graph](V v) -> bool { return boost::get<Item>(&(graph)[v]); };

FMap map_bidders = FMap(graph, any_interconnect, bidders);
FMap map_items = FMap(graph, any_interconnect, items);

They...

copy the entire graph(!), twice
uselessly get<> a variant element, just to discard it and return bool

Slightly better:

VertexFilter bidders = [&graph](V v) -> bool {
    return graph[v].which() == 0;
};
VertexFilter items = [&graph](V v) -> bool {
    return graph[v].which() == 1;
};

FMap map_bidders = FMap(graph, {}, bidders);
FMap map_items = FMap(graph, {}, items);

But it's all kind of useless. I'm not suprised this stuff takes time, because you know your graph is structured (N bidders)(N items), so

auto iterator_bidder = boost::make_iterator_range(vertices(map_bidders));
auto iterator_item = boost::make_iterator_range(vertices(map_items));

~~Could~~Should just be:

auto [b,e] = vertices(graph);
auto iterator_bidder = boost::make_iterator_range(b, b + n);
auto iterator_item   = boost::make_iterator_range(b + n, e);

And even those are overkill, since your vertex descriptor is integral anyways:

auto const bidders = boost::irange(0, n);
auto const items   = boost::irange(n, 2 * n);

I'll read some more later (family time first), because I'm already noticing more (e.g. why is listS used as the edge container selector?).

Will post here when done.

edited Jul 28 '22 at 17:08

answered Jul 28 '22 at 16:42

sehe

374,641
47
450
633

So the overhead that I was encountering was introduced by the accessing in the useless data structure, simplifying it by specifying only the range of vertices, the algorithm benefits and speed up the computation. Correct? – zulle99 Jul 28 '22 at 20:48
That's a little short. Also, this is literally always true in performance analysis. TBH I think the algorithm you compare with is just better (lower overhead), but that really doesn't tell you anything interesting (like, could the perf of the BGL algorithm be improved). I'll continue my analysis at a later time. – sehe Jul 28 '22 at 21:47
I was wondering also if it is the case to switch to adjacent_matrix since the function to get a specific edge is constant O(1) instead of adjacent_list that takes O(|V|). The drawback is about the storage of the bipartite graph since I don't have any connection within the two parts. It would be great if exist a sort for adjacent_matrix for bipartite graph that ignore the connection within parts. – zulle99 Jul 29 '22 at 06:22
Why is `eps` not adaptive in your `auction_algorithm`? It is in `auction` (the array version) – sehe Jul 29 '22 at 16:20
1

It is useless since the bidders are already assigned after the first iteration – zulle99 Jul 29 '22 at 20:30
1

Aw. I ran out of time and into my vacation. I did look a bit more bit it mostly looks like the array solution strictly does less work. And the fact that totals seem to match is perhaps just a side effect of uniformly distributed weights. I’m not sure that the comparison are menaingful/fair. That’s where I stopped because it’s always quite funny to optimize the wrong problem. – sehe Aug 08 '22 at 09:46
1

Aside from that I would probably have some tweaks that make the auction algorithm on the BGL graph behave more like the array version, but the merit is dubious: I’d go for the array version unless you have other reasons to stick with the BGL approach. I, instead, you want to run the BGL algorithm on the array representation, we might be able to come up with a good wrapper that satisfies the concept requirements. – sehe Aug 08 '22 at 09:47
Ok thanks a lot. However I got a little tip from my professor and he said that the auction algorithm must be implemented like the BGL, so the structure that maintains the graph and the way to access it must be generic, like typically the Graph structure is a template parameter of the algorithm. – zulle99 Aug 08 '22 at 11:33
Ah. That’s one reason. I’ll get back to it end of the week – sehe Aug 08 '22 at 12:33
I've made some updates, moreover I'm trying to solve the assignemnt problem in a non fully connected graph, but I notice the maximum_weighted_matching do not solve correctly the problem, like my implementation of the auction because it could happend that for example a bidder during the process of auction see its itmes becoming so expensive that it can't make any bid since others have a higher bid for all its items. – zulle99 Aug 12 '22 at 10:28
Hi, any updates from you? In any case I would like to thank you for your support, I will reserve a part of the report to thank you. – zulle99 Aug 16 '22 at 18:39

Implementation of Auction Algorthm via Boost Graph Library C++

1 Answers1