5
\$\begingroup\$

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.
enter image description here
\$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?

\$\endgroup\$
7
  • 2
    \$\begingroup\$ We cannot review this code as it does not have enough context. Please include any calling code, plus the definition for Label. \$\endgroup\$
    – Reinderien
    Feb 13 at 0:17
  • \$\begingroup\$ (This seems to return None in some, if not most cases: intentionally so?) \$\endgroup\$
    – greybeard
    Feb 13 at 10:25
  • 1
    \$\begingroup\$ The part multiplying label2.maxP by label1.ratePiP in particular begs explanation. Please don't remove the docstrings. \$\endgroup\$
    – greybeard
    Feb 13 at 10:39
  • \$\begingroup\$ @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 \$\endgroup\$
    – sos
    Feb 13 at 12:48
  • 1
    \$\begingroup\$ (Don't prematurely accept an answer: while "acceptance can be shifted", a question with an accepted answer doesn't get quite the same attention.) \$\endgroup\$
    – greybeard
    Feb 14 at 22:51
6
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ (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.) \$\endgroup\$
    – greybeard
    Feb 13 at 19:57
  • \$\begingroup\$ 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) \$\endgroup\$
    – sos
    Feb 14 at 15:23
  • \$\begingroup\$ 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! \$\endgroup\$
    – sos
    Feb 14 at 15:26
  • \$\begingroup\$ 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 \$\endgroup\$ Feb 15 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.