IMP logo
IMP Reference Guide  2.11.1
The Integrative Modeling Platform
version 2.11.1
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
4 # to 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 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 from __future__ import print_function
20 import IMP
21 import IMP.domino
22 import IMP.core
23 import random
24 import sys
25 
26 IMP.setup_from_argv(sys.argv, "marina party")
27 
28 class SumPricePairScore(IMP.PairScore):
29 
30  def evaluate_index(self, m, pair, accum):
31  price0 = Price(m.get_particle(pair[0])).get_price()
32  price1 = Price(m.get_particle(pair[1])).get_price()
33  return price0 + price1
34 
35  def do_get_inputs(self, m, pis):
36  return IMP.get_particles(m, pis)
37 
38 
39 class PriceStates(IMP.domino.ParticleStates):
40 
41  def __init__(self, prices):
42  self.prices = prices
43  IMP.domino.ParticleStates.__init__(self)
44 
45  def load_particle_state(self, i, particle):
46  pr = Price(particle)
47  pr.set_price(self.prices[i])
48 
49  def get_number_of_particle_states(self):
50  return len(self.prices)
51 
52 
53 class Price(IMP.Decorator):
54  price_key = IMP.IntKey("price")
55 
56  def __init__(self, p):
57  if not self.get_is_setup(p):
58  self.setup_particle(p)
59  self.particle = p
60 
61  def setup_particle(self, p):
62  p.add_attribute(self.price_key, 0)
63  self.particle = p
64 
65  def get_price(self):
66  return self.particle.get_value(self.price_key)
67 
68  def set_price(self, x):
69  self.particle.set_value(self.price_key, int(x))
70 
71  def get_is_setup(self, p):
72  return p.has_attribute(self.price_key)
73 
74 
75 def get_total_price(states_table, subset, assignment):
76  total_price = 0
77  for i, p in enumerate(subset):
78  price_states = states_table.get_particle_states(p)
79  price_states.load_particle_state(assignment[i], p)
80  price = Price(p).get_price()
81  total_price += price
82  return total_price
83 
84 
85 def print_assignment(states_table, subset, assignment):
86  total_price = 0
87  print("########## solution assignment", assignment)
88  for i, p in enumerate(subset):
89  price_states = states_table.get_particle_states(p)
90  price_states.load_particle_state(assignment[i], p)
91  price = Price(p).get_price()
92  print(p.get_name(), "price", price)
93 
94 
95 n_girls = 10
96 n_edges = 20
97 girls = []
98 prices = [100, 200, 400, 600, 800]
99 
100 
101 model = IMP.Model()
102 
103 # prepare filter tables for DOMINO
104 states_table = IMP.domino.ParticleStatesTable()
105 sampler = IMP.domino.DominoSampler(model, states_table)
106 all_possible_states = PriceStates(prices)
107 
108 
109 # set_states
110 for i in range(n_girls):
111  p = IMP.Particle(model, "girl-%d" % i)
112  pr = Price(p)
113  girls.append(p)
114  # add possible dresses
115  states_table.set_particle_states(p, all_possible_states)
116 
117  # dresses
118  if len(prices) == 1:
119  n_dresses = 1
120  else:
121  n_dresses = random.randrange(1, len(prices) + 1)
122 
123  # Each girl has a selection of dresses
124  selection = random.sample(prices, n_dresses)
125  allowed_states_indices = [prices.index(price) for price in selection]
126  print(p.get_name(), "prices selected", selection, "indices", allowed_states_indices)
127  list_states_table = IMP.domino.ListSubsetFilterTable(states_table)
128  list_states_table.set_allowed_states(p, allowed_states_indices)
129  sampler.add_subset_filter_table(list_states_table)
130 
131 # create restraints
132 rs = []
133 for z in range(n_edges):
134  # pair of friends
135  i = random.randrange(0, n_girls)
136  j = random.randrange(0, n_girls)
137  friends = IMP.ParticlePair(girls[i], girls[j])
138  # restraint
139  score = SumPricePairScore()
140  rs.append(IMP.core.PairRestraint(model, score, friends))
141  # Exclusion states. Two girls can't have same dress
142  ft = IMP.domino.ExclusionSubsetFilterTable()
143  ft.add_pair(friends)
144  sampler.add_subset_filter_table(ft)
145 sampler.set_restraints(rs)
146 
147 subset = states_table.get_subset()
148 solutions = sampler.get_sample_assignments(subset)
149 
150 if len(solutions) == 0:
151  print("There are no solutions to the problem")
152 else:
153  most_expensive = 0
154  best_solution = solutions[0]
155  for assignment in solutions:
156  total_price = get_total_price(states_table, subset, assignment)
157  if(total_price > most_expensive):
158  most_expensive = total_price
159  best_solution = assignment
160  print(" There are", len(solutions), "possible solutions")
161  print("=================> BEST SOLUTION <==============")
162  print_assignment(states_table, subset, best_solution)