IMP  2.3.1
The Integrative Modeling Platform
marina_party.py
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
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)
A base class for Keys.
Definition: kernel/Key.h:46
Maintain an explicit list of what states each particle is allowed to have.
Sample best solutions using Domino.
Definition: DominoSampler.h:32
A class to store an fixed array of same-typed values.
Definition: Array.h:33
Do not allow two particles to be in the same state.
Abstract class for scoring object(s) of type ParticlePair.
Class to handle individual model particles.
Basic functionality that is expected to be used by a wide variety of IMP users.
Applies a PairScore to a Pair.
Definition: PairRestraint.h:29
Divide-and-conquer inferential optimization in discrete space.
Class for storing model, its restraints, constraints, and particles.
Definition: kernel/Model.h:73