IMP logo
IMP Reference Guide  develop.27926d84dc,2024/04/22
The Integrative Modeling Platform
version 20240422.develop.27926d84dc
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
5 # particles, a pair score, particle states for DOMINO, a decorator, and using
6 # subset filter 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 
29 class SumPricePairScore(IMP.PairScore):
30 
31  def evaluate_index(self, m, pair, accum):
32  price0 = Price(m.get_particle(pair[0])).get_price()
33  price1 = Price(m.get_particle(pair[1])).get_price()
34  return price0 + price1
35 
36  def do_get_inputs(self, m, pis):
37  return IMP.get_particles(m, pis)
38 
39 
40 class PriceStates(IMP.domino.ParticleStates):
41 
42  def __init__(self, prices):
43  self.prices = prices
44  IMP.domino.ParticleStates.__init__(self)
45 
46  def load_particle_state(self, i, particle):
47  pr = Price(particle)
48  pr.set_price(self.prices[i])
49 
50  def get_number_of_particle_states(self):
51  return len(self.prices)
52 
53 
54 class Price(IMP.Decorator):
55  price_key = IMP.IntKey("price")
56 
57  def __init__(self, p):
58  if not self.get_is_setup(p):
59  self.setup_particle(p)
60  self.particle = p
61 
62  def setup_particle(self, p):
63  p.add_attribute(self.price_key, 0)
64  self.particle = p
65 
66  def get_price(self):
67  return self.particle.get_value(self.price_key)
68 
69  def set_price(self, x):
70  self.particle.set_value(self.price_key, int(x))
71 
72  def get_is_setup(self, p):
73  return p.has_attribute(self.price_key)
74 
75 
76 def get_total_price(states_table, subset, assignment):
77  total_price = 0
78  for i, p in enumerate(subset):
79  price_states = states_table.get_particle_states(p)
80  price_states.load_particle_state(assignment[i], p)
81  price = Price(p).get_price()
82  total_price += price
83  return total_price
84 
85 
86 def print_assignment(states_table, subset, assignment):
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",
127  allowed_states_indices)
128  list_states_table = IMP.domino.ListSubsetFilterTable(states_table)
129  list_states_table.set_allowed_states(p, allowed_states_indices)
130  sampler.add_subset_filter_table(list_states_table)
131 
132 # create restraints
133 rs = []
134 for z in range(n_edges):
135  # pair of friends
136  i = random.randrange(0, n_girls)
137  j = random.randrange(0, n_girls)
138  friends = IMP.ParticlePair(girls[i], girls[j])
139  # restraint
140  score = SumPricePairScore()
141  rs.append(IMP.core.PairRestraint(model, score, friends))
142  # Exclusion states. Two girls can't have same dress
143  ft = IMP.domino.ExclusionSubsetFilterTable()
144  ft.add_pair(friends)
145  sampler.add_subset_filter_table(ft)
146 sampler.set_restraints(rs)
147 
148 subset = states_table.get_subset()
149 solutions = sampler.get_sample_assignments(subset)
150 
151 if len(solutions) == 0:
152  print("There are no solutions to the problem")
153 else:
154  most_expensive = 0
155  best_solution = solutions[0]
156  for assignment in solutions:
157  total_price = get_total_price(states_table, subset, assignment)
158  if(total_price > most_expensive):
159  most_expensive = total_price
160  best_solution = assignment
161  print(" There are", len(solutions), "possible solutions")
162  print("=================> BEST SOLUTION <==============")
163  print_assignment(states_table, subset, best_solution)