diff options
Diffstat (limited to 'geom_matching/wasserstein/include/auction_runner_jac.h')
-rw-r--r-- | geom_matching/wasserstein/include/auction_runner_jac.h | 235 |
1 files changed, 182 insertions, 53 deletions
diff --git a/geom_matching/wasserstein/include/auction_runner_jac.h b/geom_matching/wasserstein/include/auction_runner_jac.h index d8cada6..252ca32 100644 --- a/geom_matching/wasserstein/include/auction_runner_jac.h +++ b/geom_matching/wasserstein/include/auction_runner_jac.h @@ -26,76 +26,205 @@ derivative works thereof, in binary and source code form. */ -#ifndef AUCTION_RUNNER_JAK_H -#define AUCTION_RUNNER_JAK_H +#ifndef HERA_AUCTION_RUNNER_JAC_H +#define HERA_AUCTION_RUNNER_JAC_H -#include <unordered_set> +#ifdef WASSERSTEIN_PURE_GEOM +#undef LOG_AUCTION +#undef ORDERED_BY_PERSISTENCE +#endif -#include "auction_oracle.h" +//#define ORDERED_BY_PERSISTENCE -namespace geom_ws { +#include <unordered_set> -using AuctionOracle = AuctionOracleKDTreeRestricted; +#include "auction_oracle.h" -// the two parameters that you can tweak in auction algorithm are: -// 1. epsilonCommonRatio -// 2. maxIterNum +namespace hera { +namespace ws { // the two parameters that you can tweak in auction algorithm are: -// 1. epsilonCommonRatio -// 2. maxIterNum +// 1. epsilon_common_ratio +// 2. max_num_phases +template<class RealType_ = double, class AuctionOracle_ = AuctionOracleKDTreeRestricted<RealType_>, class PointContainer_ = std::vector<DiagramPoint<RealType_>> > // alternatively: AuctionOracleLazyHeap --- TODO class AuctionRunnerJac { public: - AuctionRunnerJac(const std::vector<DiagramPoint>& A, const std::vector<DiagramPoint>& B, const double q, const double _delta, const double _internal_p); - void setEpsilon(double newVal) { assert(epsilon > 0.0); epsilon = newVal; }; - double getEpsilon() const { return epsilon; } - double getWassersteinDistance(); - double getWassersteinCost(); - double getRelativeError() const { return relativeError; }; - static constexpr double epsilonCommonRatio { 5 }; // next epsilon = current epsilon / epsilonCommonRatio - static constexpr int maxIterNum { 25 }; // maximal number of iterations of epsilon-scaling -private: + + using Real = RealType_; + using AuctionOracle = AuctionOracle_; + using DgmPoint = typename AuctionOracle::DiagramPointR; + using IdxValPairR = IdxValPair<Real>; + using PointContainer = PointContainer_; + + const Real k_lowest_bid_value = -1; // all bid values must be positive + + + AuctionRunnerJac(const PointContainer& A, + const PointContainer& B, + const AuctionParams<Real>& params, + const std::string& _log_filename_prefix = ""); + + void set_epsilon(Real new_val); + Real get_epsilon() const { return epsilon; } + void run_auction(); + template<class Range> + void run_bidding_step(const Range& r); + bool is_done() const; + void decrease_epsilon(); + Real get_wasserstein_distance(); + Real get_wasserstein_cost(); + Real get_relative_error(const bool debug_output = false) const; +//private: // private data - std::vector<DiagramPoint> bidders, items; - const size_t numBidders; - const size_t numItems; - std::vector<IdxType> itemsToBidders; - std::vector<IdxType> biddersToItems; - double wassersteinPower; - double epsilon; - double delta; - double internal_p; - double weightAdjConst; - double wassersteinDistance; - double wassersteinCost; - std::vector<IdxValPair> bidTable; - double relativeError; + PointContainer bidders; + PointContainer items; + const size_t num_bidders; + const size_t num_items; + std::vector<IdxType> items_to_bidders; + std::vector<IdxType> bidders_to_items; + Real wasserstein_power; + Real epsilon; + Real delta; + Real internal_p; + Real initial_epsilon; + const Real epsilon_common_ratio; // next epsilon = current epsilon / epsilon_common_ratio + const int max_num_phases; // maximal number of phases of epsilon-scaling + Real weight_adj_const; + Real wasserstein_cost; + std::vector<IdxValPairR> bid_table; // to get the 2 best items - std::unique_ptr<AuctionOracle> oracle; - std::list<size_t> unassignedBidders; - std::vector< std::list<size_t>::iterator > unassignedBiddersIterators; - std::vector< short > itemReceivedBidVec; - std::list<size_t> itemsWithBids; + AuctionOracle oracle; + std::unordered_set<size_t> unassigned_bidders; + std::unordered_set<size_t> items_with_bids; + // to imitate Gauss-Seidel + const size_t max_bids_per_round; + Real partial_cost { 0.0 }; + bool is_distance_computed { false }; + int num_rounds { 0 }; + int num_phase { 0 }; + int dimension; + + size_t unassigned_threshold; // for experiments + +#ifndef WASSERSTEIN_PURE_GEOM + std::unordered_set<size_t> unassigned_normal_bidders; + std::unordered_set<size_t> unassigned_diag_bidders; + bool diag_first {true}; + size_t batch_size { 1000 }; +#ifdef ORDERED_BY_PERSISTENCE + // to process unassigned by persistence + using RealIdxPair = std::pair<Real, size_t>; + std::set<RealIdxPair, std::greater<RealIdxPair>> unassigned_normal_bidders_by_persistence; +#endif + + // to stop earlier in the last phase + const Real total_items_persistence; + const Real total_bidders_persistence; + Real unassigned_bidders_persistence; + Real unassigned_items_persistence; + Real gamma_threshold; + + + size_t num_diag_items { 0 }; + size_t num_normal_items { 0 }; + size_t num_diag_bidders { 0 }; + size_t num_normal_bidders { 0 }; + + +#endif + + + // private methods - void assignGoodToBidder(const IdxType bidderIdx, const IdxType itemsIdx); - void assignToBestBidder(const IdxType itemsIdx); - void clearBidTable(); - void runAuction(); - void runAuctionPhase(); - void submitBid(IdxType bidderIdx, const IdxValPair& itemsBidValuePair); - void flushAssignment(); + void assign_item_to_bidder(const IdxType bidder_idx, const IdxType items_idx); + void assign_to_best_bidder(const IdxType items_idx); + void clear_bid_table(); + void run_auction_phases(const int max_num_phases, const Real _initial_epsilon); + void run_auction_phase(); + void submit_bid(IdxType bidder_idx, const IdxValPairR& items_bid_value_pair); + void flush_assignment(); + Real get_item_bidder_cost(const size_t item_idx, const size_t bidder_idx) const; +#ifndef WASSERSTEIN_PURE_GEOM + Real get_cost_to_diagonal(const DgmPoint& pt) const; + Real get_gamma() const; +#endif + bool continue_auction_phase() const; + + void add_unassigned_bidder(const size_t bidder_idx); + void remove_unassigned_bidder(const size_t bidder_idx); + void remove_unassigned_item(const size_t item_idx); + +#ifndef WASSERSTEIN_PURE_GEOM + bool is_item_diagonal(const size_t item_idx) const { return item_idx < num_diag_items; } + bool is_item_normal(const size_t item_idx) const { return not is_item_diagonal(item_idx); } + bool is_bidder_diagonal(const size_t bidder_idx) const { return bidder_idx >= num_normal_bidders; } + bool is_bidder_normal(const size_t bidder_idx) const { return not is_bidder_diagonal(bidder_idx); } +#endif + + // for debug only - void sanityCheck(); - void printDebug(); - int countUnhappy(); - void printMatching(); - double getDistanceToQthPowerInternal(); -}; + void sanity_check(); + void print_debug(); + void print_matching(); + + std::string log_filename_prefix; + const Real k_max_relative_error = 2.0; // if relative error cannot be estimated or is too large, use this value + +#ifdef LOG_AUCTION + + size_t parallel_threshold { 5000 }; + bool is_step_parallel {false}; + std::unordered_set<size_t> unassigned_items; + std::unordered_set<size_t> unassigned_normal_items; + std::unordered_set<size_t> unassigned_diag_items; + std::unordered_set<size_t> never_assigned_bidders; + size_t all_assigned_round { 0 }; + size_t all_assigned_round_found { false }; + + int num_rounds_non_cumulative { 0 }; // set to 0 in the beginning of each phase + int num_diag_assignments { 0 }; + int num_diag_assignments_non_cumulative { 0 }; + int num_diag_bids_submitted { 0 }; + int num_diag_stole_from_diag { 0 }; + int num_normal_assignments { 0 }; + int num_normal_assignments_non_cumulative { 0 }; + int num_normal_bids_submitted { 0 }; + + std::vector<std::vector<size_t>> price_change_cnt_vec; + + + const char* plot_logger_name = "plot_logger"; + const char* price_state_logger_name = "price_stat_logger"; + std::string plot_logger_file_name; + std::string price_stat_logger_file_name; + std::shared_ptr<spdlog::logger> plot_logger; + std::shared_ptr<spdlog::logger> price_stat_logger; + std::shared_ptr<spdlog::logger> console_logger; + + + int num_parallel_bids { 0 }; + int num_total_bids { 0 }; + + int num_parallel_diag_bids { 0 }; + int num_total_diag_bids { 0 }; + + int num_parallel_normal_bids { 0 }; + int num_total_normal_bids { 0 }; + + int num_parallel_assignments { 0 }; + int num_total_assignments { 0 }; +#endif + +}; // AuctionRunnerJac + +} // ws +} // hera +#include "auction_runner_jac.hpp" -} // end of namespace geom_ws +#undef ORDERED_BY_PERSISTENCE #endif |