CYCLUS
greedy_solver.h
Go to the documentation of this file.
1 #ifndef CYCLUS_SRC_GREEDY_SOLVER_H_
2 #define CYCLUS_SRC_GREEDY_SOLVER_H_
3 
4 #include "exchange_graph.h"
5 #include "exchange_solver.h"
7 
8 namespace cyclus {
9 
10 /// @warning Deprecated! Use the Capacity member functions defined in the
11 /// GreedySolver class.
12 // @{
13 void Capacity(cyclus::Arc const&, double, double);
14 void Capacity(boost::shared_ptr<cyclus::ExchangeNode>, cyclus::Arc const&,
15  double);
16 // @}
17 
18 /// double Capacity(const Arc& a, double u_curr_qty, double v_curr_qty) {
19 /// return 0;
20 /// }
21 
22 /// @brief A comparison function for sorting a container of Arcs by the
23 /// requester's (unode's) preference, in decensing order (i.e., most preferred
24 /// Arc first). In the case of a tie, a lexicalgraphic ordering of node ids is
25 /// used.
26 inline bool ReqPrefComp(const Arc& l, const Arc& r) {
27  int lu = l.unode()->agent_id;
28  int lv = l.vnode()->agent_id;
29  int ru = r.unode()->agent_id;
30  int rv = r.vnode()->agent_id;
31  double lpref = l.unode()->prefs[l];
32  double rpref = r.unode()->prefs[r];
33  return (lpref != rpref) ? (lpref > rpref) : (lu > ru || (lu == ru && lv > rv));
34 }
35 
36 /// @brief A comparison function for sorting a container of Nodes by the nodes
37 /// preference in decensing order (i.e., most preferred Node first). In the case
38 /// of a tie, a lexicalgraphic ordering of node ids is used.
40  int lid = l->agent_id;
41  int rid = r->agent_id;
42  double lpref = AvgPref(l);
43  double rpref = AvgPref(r);
44  return (lpref != rpref) ? (lpref > rpref) : (lid > rid);
45 }
46 
47 class ExchangeGraph;
49 
50 /// @brief The GreedySolver provides the implementation for a "greedy" solution
51 /// to a resource exchange graph.
52 ///
53 /// Given an ExchangeGraph, the greedy solver will march through each
54 /// RequestGroup in the graph, matching request nodes "greedily" with supply
55 /// nodes. Each request node will attempt to be supplied by supplier arcs as
56 /// long as those supplier arcs have some excess capacity. The possible
57 /// suppliers will be ordered by descending preference. The algorithm terminates
58 /// when one of the following conditions is met:
59 /// 1) All RequestGroups are satisfied
60 /// 2) All SupplySets are at capacity
61 ///
62 /// @warning the GreedySolver is responsible for deleting is conditioner!
64  public:
65  /// GreedySolver constructor
66  /// @param exclusive_orders a flag for enforcing integral, quantized orders
67  /// @param c a conditioner to use before solving a graph instance
68  /// @warning if a NULL pointer is passed as a conditioner argument,
69  /// conditioning will *NOT* occur
70  /// @{
71  GreedySolver();
72  explicit GreedySolver(bool exclusive_orders);
74  GreedySolver(bool exclusive_orders, GreedyPreconditioner* c);
75  /// @}
76 
77  virtual ~GreedySolver();
78 
79  /// Uses the provided (or a default) GreedyPreconditioner to condition the
80  /// solver's ExchangeGraph so that RequestGroups are ordered by average
81  /// preference and commodity weight.
82  ///
83  /// @warning this function is called during the Solve step and should most
84  /// likely not be called independently thereof (except for testing)
85  void Condition();
86 
87  /// Initialize member values based on the given graph.
88  void Init();
89 
90  /// @brief the capacity of the arc
91  ///
92  /// @throws StateError if either ExchangeNode does not have a ExchangeNodeGroup
93  /// @param a the arc
94  /// @param u_curr_qty the current quantity assigned to the unode (if solving
95  /// piecemeal)
96  /// @param v_curr_qty the current quantity assigned to the vnode (if solving
97  /// piecemeal)
98  /// @return The minimum of the unode and vnode's capacities
99  // @{
100  double Capacity(const Arc& a, double u_curr_qty, double v_curr_qty);
101  inline double Capacity(const Arc& a) { return Capacity(a, 0, 0); }
102  // @}
103 
104  /// @brief the capacity of a node
105  ///
106  /// @throws StateError if ExchangeNode does not have a ExchangeNodeGroup
107  /// @param n the node
108  /// @param min_cap whether to use the minimum or maximum capacity value. In general,
109  /// nodes that represent bids use the minimum (i.e., the capacities represents a
110  /// less-than constraint) and nodes that represent requests use the maximum
111  /// value (i.e., the capacities represents a greater-than constraint).
112  /// @param curr_qty the currently allocated node quantity (if solving piecemeal)
113  /// @return The minimum of the node's nodegroup capacities / the node's unit
114  /// capacities, or the ExchangeNode's remaining qty -- whichever is smaller.
115  /// @{
116  double Capacity(ExchangeNode::Ptr n, const Arc& a, bool min_cap,
117  double curr_qty);
118  inline double Capacity(ExchangeNode::Ptr n, const Arc& a, bool min_cap) {
119  return Capacity(n, a, min_cap, 0.0);
120  }
121  inline double Capacity(ExchangeNode::Ptr n, const Arc& a, double curr_qty) {
122  return Capacity(n, a, true, curr_qty);
123  }
124  inline double Capacity(ExchangeNode::Ptr n, const Arc& a) {
125  return Capacity(n, a, true, 0.0);
126  }
127  /// @}
128 
129  protected:
130  /// @brief the GreedySolver solves an ExchangeGraph by iterating over each
131  /// RequestGroup and matching requests with the minimum bids possible, starting
132  /// from the beginning of the the respective request and bid containers.
133  virtual double SolveGraph();
134 
135  private:
136  /// @brief updates the capacity of a given ExchangeNode (i.e., its max_qty and the
137  /// capacities of its ExchangeNodeGroup)
138  ///
139  /// @throws StateError if ExchangeNode does not have a ExchangeNodeGroup
140  /// @throws ValueError if the update results in a negative ExchangeNodeGroup
141  /// capacity or a negative ExchangeNode max_qty
142  /// @param n the ExchangeNode
143  /// @param qty the quantity for the node to update
144  void GetCaps(ExchangeNodeGroup::Ptr prs);
145  void GreedilySatisfySet(RequestGroup::Ptr prs);
146  void UpdateCapacity(ExchangeNode::Ptr n, const Arc& a, double qty);
147  void UpdateObj(double qty, double pref);
148 
149  GreedyPreconditioner* conditioner_;
150  std::map<ExchangeNode::Ptr, double> n_qty_;
151  std::map<ExchangeNodeGroup*, std::vector<double> > grp_caps_;
152  double obj_;
153  double unmatched_;
154 };
155 
156 } // namespace cyclus
157 
158 #endif // CYCLUS_SRC_GREEDY_SOLVER_H_
bool AvgPrefComp(ExchangeNode::Ptr l, ExchangeNode::Ptr r)
A comparison function for sorting a container of Nodes by the nodes preference in decensing order (i...
Definition: greedy_solver.h:39
double Capacity(const Arc &a, double u_curr_qty, double v_curr_qty)
the capacity of the arc
double Capacity(ExchangeNode::Ptr n, const Arc &a)
void Condition()
Uses the provided (or a default) GreedyPreconditioner to condition the solver&#39;s ExchangeGraph so that...
An arc represents a possible connection between two nodes in the bipartite resource exchange graph...
boost::shared_ptr< RequestGroup > Ptr
bool ReqPrefComp(const Arc &l, const Arc &r)
double Capacity(const Arc& a, double u_curr_qty, double v_curr_qty) { return 0; } ...
Definition: greedy_solver.h:26
boost::shared_ptr< ExchangeNode > Ptr
void Init()
Initialize member values based on the given graph.
boost::shared_ptr< ExchangeNodeGroup > Ptr
boost::shared_ptr< ExchangeNode > vnode() const
virtual double SolveGraph()
the GreedySolver solves an ExchangeGraph by iterating over each RequestGroup and matching requests wi...
A GreedyPreconditioner conditions an ExchangeGraph for a GreedySolver by ordering the RequestGroups a...
void Capacity(cyclus::Arc const &, double, double)
GreedySolver()
GreedySolver constructor.
taken directly from OsiSolverInterface.cpp on 2/17/14 from https://projects.coin-or.org/Osi/browser/trunk.
Definition: agent.cc:14
double AvgPref(ExchangeNode::Ptr n)
a very simple interface for solving translated resource exchanges
double Capacity(ExchangeNode::Ptr n, const Arc &a, double curr_qty)
boost::shared_ptr< ExchangeNode > unode() const
An ExchangeGraph is a resource-neutral representation of a ResourceExchange.
double Capacity(const Arc &a)
The GreedySolver provides the implementation for a "greedy" solution to a resource exchange graph...
Definition: greedy_solver.h:63
double Capacity(ExchangeNode::Ptr n, const Arc &a, bool min_cap)