IMP  2.0.0
The Integrative Modeling Platform
domino/marina_party.py

This is a not very serious example that shows how to use domino from scratch to solve a problem. It is illustrative of creating your own type of particles, a pair score, particle states for DOMINO, a decorator, and using subset filter tables with DOMINO.

Solution of the Marina Party Problem with DOMINO:

1 ## \example domino/marina_party.py
2 ##
3 ## This is a not very serious example that shows how to use domino from scratch to
4 ## solve a problem. It is illustrative of creating your own type of particles,
5 ## a pair score, particle states for DOMINO, a decorator, and using subset filter
6 ## tables with DOMINO.
7 ##
8 ## Solution of the Marina Party Problem with DOMINO:
9 ##
10 ## - Girls attend to a party
11 ## - Each girl has dresses of different price
12 ## - There can not be repeated dresses in the party within a group of connected
13 ## people
14 ## - Girls that are friends can call each other to agree
15 ## - The objective is to maximize the total price of all dresses in the party
16 ##
17 ##
18 
19 
20 import IMP
21 import IMP.domino as domino
22 import IMP.core as core
23 import random
24 
25 
26 class SumPricePairScore(IMP.PairScore):
27 
28  def evaluate(self, pair, accum):
29  price0 = Price(pair[0]).get_price()
30  price1 = Price(pair[1]).get_price()
31  return price0+price1
32 
33  def _do_get_inputs(self, m, pis):
34  return [m.get_particle(i) for i in pis]
35 
36 class PriceStates(domino.ParticleStates):
37 
38  def __init__(self, prices):
39  self.prices = prices
40  domino.ParticleStates.__init__(self)
41 
42  def load_particle_state(self, i, particle):
43  pr = Price(particle)
44  pr.set_price(self.prices[i])
45 
46  def get_number_of_particle_states(self):
47  return len(self.prices)
48 
49 
50 class Price(IMP.Decorator):
51  price_key = IMP.IntKey("price")
52 
53  def __init__(self, p):
54  if not self.particle_is_instance(p):
55  self.setup_particle(p)
56  self.particle = p
57 
58  def setup_particle(self, p):
59  p.add_attribute(self.price_key, 0)
60  self.particle = p
61 
62  def get_price(self):
63  return self.particle.get_value(self.price_key)
64 
65  def set_price(self, x):
66  self.particle.set_value(self.price_key, int(x))
67 
68  def particle_is_instance(self, p):
69  return p.has_attribute(self.price_key)
70 
71 
72 
73 def get_total_price(states_table, subset, assignment):
74  total_price = 0
75  for i, p in enumerate(subset):
76  price_states = states_table.get_particle_states(p)
77  price_states.load_particle_state(assignment[i], p)
78  price = Price(p).get_price()
79  total_price += price
80  return total_price
81 
82 
83 def print_assignment(states_table, subset, assignment):
84  total_price = 0
85  print "########## solution assignment", assignment
86  for i, p in enumerate(subset):
87  price_states = states_table.get_particle_states(p)
88  price_states.load_particle_state(assignment[i], p)
89  price = Price(p).get_price()
90  print p.get_name(), "price", price
91 
92 
93 n_girls = 10
94 n_edges = 20
95 girls = []
96 prices = [100, 200, 400, 600, 800 ]
97 
98 
99 model = IMP.Model()
100 
101 # prepare filter tables for DOMINO
102 states_table = domino.ParticleStatesTable()
103 sampler = domino.DominoSampler(model,states_table)
104 all_possible_states = PriceStates(prices)
105 
106 
107 # set_states
108 for i in range(n_girls):
109  p = IMP.Particle(model, "girl-%d" % i)
110  pr = Price(p)
111  girls.append(p)
112  # add possible dresses
113  states_table.set_particle_states(p, all_possible_states)
114 
115  # dresses
116  if len(prices) == 1:
117  n_dresses = 1
118  else:
119  n_dresses = random.randrange(1,len(prices)+1)
120 
121  # Each girl has a selection of dresses
122  selection = random.sample(prices, n_dresses)
123  allowed_states_indices = [prices.index(price) for price in selection]
124  print p.get_name(), "prices selected",selection, "indices", allowed_states_indices
125  list_states_table = domino.ListSubsetFilterTable(states_table)
126  list_states_table.set_allowed_states(p, allowed_states_indices)
127  sampler.add_subset_filter_table(list_states_table)
128 
129 # create restraints
130 for z in xrange(n_edges):
131  # pair of friends
132  i = random.randrange(0,n_girls)
133  j = random.randrange(0,n_girls)
134  friends = IMP.ParticlePair(girls[i], girls[j])
135  # restraint
136  score = SumPricePairScore()
137  r = core.PairRestraint(score, friends)
138  model.add_restraint(r)
139  # Exclusion states. Two girls can't have same dress
140  ft = domino.ExclusionSubsetFilterTable()
141  ft.add_pair(friends)
142  sampler.add_subset_filter_table(ft)
143 
144 subset = states_table.get_subset()
145 solutions = sampler.get_sample_assignments(subset)
146 
147 if len(solutions) == 0:
148  print "There are no solutions to the problem"
149 else:
150  most_expensive = 0
151  best_solution = solutions[0]
152  for assignment in solutions:
153  total_price = get_total_price(states_table, subset, assignment)
154  if(total_price > most_expensive):
155  most_expensive = total_price
156  best_solution = assignment
157  print " There are", len(solutions), "possible solutions"
158  print "=================> BEST SOLUTION <=============="
159  print_assignment(states_table, subset, best_solution)