# compare between two labels /objects -dominance rules

I have a function dominates() that seems to be the bottleneck of my algorithm (after profiling it). the function is as follows:

def dominates(self, label1: Label, label2: Label):
"""
compares two labels based on dominance rules
:param label1:  label object
:param label2:  label object
:return: label2 if label2 is dominated by label1, else returns label1 if label1 is dominated by label2 else returns None
"""
if label1.cost - label1.maxP * label1.ratePiP <= label2.cost - label2.maxP * label2.ratePiP:
if label1.part <=  label2.part :
if label1.cost - (label2.loadF + label2.maxP - label1.loadF) * label1.ratePiP <= label2.cost - label2.maxP * label2.ratePiP :
if all(l1 <=l2 for l1,l2 in zip(label1.custk, label2.custk)):
return label2
else:
if label1.part >= label2.part:
if label1.cost - (label2.loadF + label2.maxP - label1.loadF) * label1.ratePiP >=label2.cost - label2.maxP * label2.ratePiP:
if all(l1>= l2 for l1, l2 in zip(label1.custk, label2.custk)):
return label1


Here is the definition for the label class (it is basically a container of information):

class Label(object):
def __init__(self, node, loadf=None, cost=None, part=None, custk=None, ratePiP=None, maxP=None,
rdp=None, route=None, previous_label=None, ):
self.node: int= node
self.cost: float= cost
self.part: int= part
self.custk = custk  # array.array
self.ratePiP: float = ratePiP
self.maxP: int = maxP
self.previous_label : Label= previous_label
self.rdp: List[str]= rdp
self.route = route  # array.array


These dominance rules come from a paper A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem and the dominance rules are stated there (see picture). It will be long to explain the math behind those conditions and not useful for this post.

$$\T_i^{part} \$$ can take either 0 or 1 (0 more often than 1).
In case $$\T_i^{part}\$$ is equal to 0, then $$\T_i^{maxP}\$$ and $$\T_i^{ratePiP}\$$ are equal to 0.
if $$\T_i^{part} \$$ takes 1, then $$\T_i^{maxP}\$$ takes non-negative integer values while $$\T_i^{ratePiP}\$$ can take any value in R.
The function is called multiple times in the function discard_dominated() below:

def discard_dominated(self, ULj):
"""
:param ULj: list of untreated labels associated with the same vertex
:return: list of non-dominated labels in ULj
"""
dom = self.dominates
to_remove = [dom(label2, label1) for ind, label2 in enumerate(ULj) for label1 in ULj[ind + 1:]]
to_remove = set(to_remove)
return [lab for lab in ULj if lab not in to_remove]


This function is also called many times in a while loop.
label.cost and label.ratePiP are floats and label.part and label.loadF and label.maxP are integers while label.custk is array.array full of 0 and 1.
I tried to first compute the conditions and save them in local variables and check them (if first condition and second condition and ...) but it was taking more time.
For one small instance that I am testing my algorithm on, the len(ULj) is between 10 and 80 and the length of the removed labels (len(to_remove)) is between 1 and 57 and have most of the time a length less than 10. however for larger instances I would expect that these numbers would be much larger than this. Also the elements of the list ULj are unique by construction.
The number of calls is quite high (25,000,000+ times) and have done my best to reduce it. I am now testing on small instances and it does not seem ok for me to have that much time spent on this function (28971 ms) for small instances. Any idea how to speed it up?

• We cannot review this code as it does not have enough context. Please include any calling code, plus the definition for Label. Feb 13 at 0:17
• (This seems to return None in some, if not most cases: intentionally so?) Feb 13 at 10:25
• The part multiplying label2.maxP by label1.ratePiP in particular begs explanation. Please don't remove the docstrings. Feb 13 at 10:39
• @greybeard exactly if the first set of conditions is true then label2 is dominated and it is returned (to be removed from another list) and if the second set of conditions is true then label1 is dominated and is returned, otherwise, we cannot conclude anything and none of the labels is dominated by the other thus the function returns None
– sos
Feb 13 at 12:48
• (Don't prematurely accept an answer: while "acceptance can be shifted", a question with an accepted answer doesn't get quite the same attention.) Feb 14 at 22:51

You use a docstring to good effect. I'd think it great if you followed the rules closely:

"""
<whatever sums up this module>.

Dominance as defined in Desaulniers/Rakke/Coelho:
"A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem"
"""

def dominates(self, label1: Label, label2: Label):
"""
Compare two labels based on dominance rules.

:param label1:  label object
:param label2:  label object
:return: label2 if label2 is dominated by label1,
else returns label1 if label1 is dominated by label2,
else returns None
"""
pass


(I'd probably return a truth value, name the method dominated(), or reverse the logic to get dominator().)

Let me suggest rewriting

$$\text{(f) }T_1^{cost} - (T_2^{loadF} + T_2^{maxP} - T_1^{loadF})T_1^{ratePiP} \le T_2^{cost} - T_2^{maxP} T_2^{ratePiP}$$ adding $$\T_2^{maxP} T_1^{ratePiP}\$$ to both sides turns multiplication of different measures, one from each label
into scaling differences in loadF by $$\T_1^{ratePiP}\$$ and differences in ratePiP by $$\T_2^{maxP}\$$:

$$\text{(f) }T_1^{cost} + (T_1^{loadF} - T_2^{loadF})T_1^{ratePiP} \le T_2^{cost} + (T_1^{ratePiP} - T_2^{ratePiP})T_2^{maxP}$$ Denoted like this, conditions (e) and (f) look dependant on the signum of $$\(T_1^{ratePiP} - T_2^{ratePiP})T_2^{maxP}\$$: if negative, (f) implies (e), else (e) implies (f).
(If $$\T_2^{maxP}\$$ was known to be non-negative, comparing rates would suffice.)

One thing nagging me is dominates in case of all equals.

Ordering the evaluation of conditions by increasing cost looks prudent; another criterion is more selective first. (One more place where code documentation/review context was valuable: what is Label.part?).
I'd try and get rid of some of the indentation levels. For readability, I'd prefer and here over return None.
The top if-statement and the else-statement look symmetrical enough to be duplicated code: a maintenance nightmare if nothing else. You can get rid of that introducing roles.

def dominates(self, label1: Label, label2: Label):
"""
Compare two labels based on dominance rules.

:param label1:  label object
:param label2:  label object
:return: label2 if label2 is dominated by label1,
else returns label1 if label1 is dominated by label2,
else returns None
"""
champ, other = (label2, label1                  # (c)
) if label1.part <= label2.part else (label1, label2)
or champ.cost - champ.maxP * champ.ratePiP  # (d)
< other.cost - other.maxP * other.ratePiP):
return None
scaled_rate_delta = (other.ratePiP - champ.ratePiP) * champ.maxP
<= champ.cost + min(0, scaled_rate_delta)                   # (e)&(f)
and all(lo <= lc for lo, lc in zip(other.custk, champ.custk))):  # (b)
return champ

return None


I hope some calls can be obviated excluding inferiors from further competition:

def discard_dominated(self, ULj):
"""

:param ULj: collection of untreated labels associated with the same vertex
:return: collection of non-dominated labels in ULj
"""
survivors = set()  # no domination within this set
for sample in ULj:
# casualties = { dominates(sample, veteran) for veteran in survivors }
casualties = set()
for veteran in survivors:  # allows "early out"
inferior = dominates(sample, veteran)
if inferior is sample:
break     # casualties empty (really?)
if inferior:  # is veteran/not None
casualties += veteran
else:
survivors += sample
survivors -= casualties  # not dead sure this belongs in else
return survivors

• (Without a test harness, I've more likely gotten at least one negation wrong than all of them right: anybody confident to know better please correct.) Feb 13 at 19:57
• in case of equality, both labels are equivalent and one should remain, the other is discarded (hence return label2 in my first function). I tried your code but it takes even more time. However, I will see what I can do with your insights regarding (e) and (f)
– sos
Feb 14 at 15:23
• also T_2^maxP is non-negative and T2^part can take either 0 or 1, and takes 0 more times than 1. also if T2^part is 0 then T2^ratePiP and T2maxP are equal to 0 which means the conditions (d) (e) and (f) are reduced to T_1^cost <=T_2^cost. I will see if this will speed up my function!
– sos
Feb 14 at 15:26
• Not sure about this one because function calls overheads but other, champ = sorted((label1, label2), key=operator.attrgetter('part')) might be more readable than your ternary Feb 15 at 11:57