IMP  2.2.1
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
22 import IMP.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 
37 class PriceStates(IMP.domino.ParticleStates):
38 
39  def __init__(self, prices):
40  self.prices = prices
41  IMP.domino.ParticleStates.__init__(self)
42 
43  def load_particle_state(self, i, particle):
44  pr = Price(particle)
45  pr.set_price(self.prices[i])
46 
47  def get_number_of_particle_states(self):
48  return len(self.prices)
49 
50 
51 class Price(IMP.Decorator):
52  price_key = IMP.IntKey("price")
53 
54  def __init__(self, p):
55  if not self.get_is_setup(p):
56  self.setup_particle(p)
57  self.particle = p
58 
59  def setup_particle(self, p):
60  p.add_attribute(self.price_key, 0)
61  self.particle = p
62 
63  def get_price(self):
64  return self.particle.get_value(self.price_key)
65 
66  def set_price(self, x):
67  self.particle.set_value(self.price_key, int(x))
68 
69  def get_is_setup(self, p):
70  return p.has_attribute(self.price_key)
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.kernel.Model()
100 
101 # prepare filter tables for DOMINO
102 states_table = IMP.domino.ParticleStatesTable()
103 sampler = IMP.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.kernel.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 = IMP.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.kernel.ParticlePair(girls[i], girls[j])
135  # restraint
136  score = SumPricePairScore()
137  r = IMP.core.PairRestraint(score, friends)
138  model.add_restraint(r)
139  # Exclusion states. Two girls can't have same dress
140  ft = IMP.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)