compare between two labels /objects -dominance rules

Question

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.loadF <=  label2.loadF:
            if label1.part <=  label2.part :
                if label1.cost - (label2.loadF - label1.loadF) * label1.ratePiP <=  label2.cost :
                    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.loadF >= label2.loadF:
            if label1.part >= label2.part:
                if label1.cost - (label2.loadF - label1.loadF) * label1.ratePiP >= label2.cost :
                    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.loadF: int = loadf
        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?

Answer 1

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)
    if (champ.loadF < other.loadF                   # (a)
        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
    if (other.cost + (other.loadF - champ.loadF) * other.ratePiP
        <= 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):
    """
    Discard dominated labels from 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