Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure

Recently and independently from us, Iwamasa et al. [26] also presented a general framework for solving Max-Sum Diverse Solutions (and Max-Cov Diverse Solutions; see definition in Section 5) under certain conditions on the set of feasible solutions. They show that the conditions in our Theorem 1 imply the conditions in their framework. In the full version of this paper, we show that the reverse is true as well. Thus, their conditions and our conditions are, in fact, equivalent. Their approach reduces the problem to network flow, avoiding SFM and resulting in faster algorithms for computing diverse minimum $s$-$t$ cuts and diverse stable matchings. However, in contrast to their framework, ours also supports the absolute-difference measure $d_{\mathrm{abs}}$ and thus, potentially applies to a broader range of problems.

For $k\in \mathbb{N}$, we use $[k]$ to denote the set $\{1,\mathrm{\dots },k\}$. The power set of a set $M$ is denoted by $2^M$. For any set $M$, we use the symbol $M^k$ for the cartesian product; $\{(a_1,a_2,\mathrm{\dots },a_k)|a_i\in M\}$. The disjoint union of two sets is simply their union, but with the additional information that the two sets have no elements in common.

A multiset is a set in which elements can appear multiple times. The number of times an element appears in a multiset is referred to as its multiplicity. The sum of two multisets $A$ and $B$, denoted by $A\uplus B$, is a multiset in which each element appears with a multiplicity equal to the sum of its multiplicity in $A$ and in $B$. We refer to a multiset of cardinality $k$ as a $k$-multiset. For a set $M$, we denote by $M_k$ a $k$-multiset with elements drawn from $M$.

Unlike a multiset, where elements are unordered, a tuple is a collection of possibly repeated elements that is ordered. A $k$-tuple is a tuple of $k$ elements. We denote a tuple by listing its elements within parenthesis and separated by commas; e.g., $(a,b,c,d)$. Note that the cartesian product of $k$ sets is a $k$-tuple.

A partially ordered set (poset) $P=(X,{⪯}_P)$ consists of a ground set $X$ along with a binary relation ${⪯}_P$ on $X$ that satisfies reflexivity, antisymmetry, and transitivity. When the relation ${⪯}_P$ is evident from the context, we often use the same notation for both the poset and its ground set. In case a poset is indexed by a subscript $i$, we use ${⪯}_i$ to denote its order relation. The Hasse diagram $G(P)$ of $P$, is a directed graph where each element of $X$ is represented as a node, and an edge exists from element $a$ to element $b$ if $a{⪯}_{P}b$ and no intermediate element $c$ satisfies $a{⪯}_{P}c{⪯}_{P}b$. Vertices are arranged so that edge directions are implicitly understood as pointing upward.

A poset $P^{\ast }=(X^{\ast },{⪯}_P^{\ast })$ is called a subposet of another poset $P=(X,{⪯}_P)$ if (i) $X^{\ast }\subseteq X$ and (ii) for any $x,y\in X^{\ast }$ if $x{⪯}_P^{\ast }y$ then $x{⪯}_{P}y$. If the other direction of (ii) also holds, then we call $P^{\ast }$ the subposet of $P$ induced by $X^{\ast }$, and write $P^{\ast }=P[X^{\ast }]$. Given two posets $P=(X,{⪯}_P)$ and $Q=(Y,{⪯}_Q)$, their disjoint union $P\bigsqcup Q$ is the disjoint union of $X$ and $Y$ together with relation ${⪯}_{P+Q}$ where $x{⪯}_{P+Q}y$ if one of the following conditions holds: (i) $x,y\in X$ and $x{⪯}_{P}y$, or (ii) $x,y\in Q$ and $x{⪯}_{Q}y$. Thus, the Hasse diagram of $P\bigsqcup Q$ consists of the disconnected Hasse diagrams of $P$ and $Q$ drawn together.

A chain is a subset of a poset in which every pair of elements is comparable, and an antichain is a subset of a poset in which no two (distinct) elements are comparable. For any two elements $x$ and $y$ in a chain $E$ with order relation ${⪯}_E$, we say that $x$ (resp. $y$) is a chain-predecessor (chain-successor) of $y$ if $x{⪯}_{E}y$. A poset is called a chain decomposition if the poset can be expressed as the disjoint union of chains.

For a poset $P=(X,{⪯}_P)$, an ideal is a set $U\subseteq X$ where $u\in U$ implies that $v\in U$ for all $v{⪯}_{P}u$. In terms of its Hasse diagram $G(P)=(X,E)$, a subset $U$ of $X$ is an ideal if and only if there is no incoming edge from $U$. We use $𝒟(P)$ to denote the family of all ideals of $P$. If $x{⪯}_{P}y$ in the poset, then the closed interval from $x$ to $y$, denoted by $[x,y]$, is the poset with ground set $\{z\in X|x{⪯}_{P}z{⪯}_{P}y\}$ together with relation ${⪯}_P$.

Now we introduce the notion of componentwise order. Let $(X_i,{⪯}_i)$, $i\in [r]$ be posets, with $r$ a positive integer, and let $Y\subseteq X_1\times \mathrm{\cdots }\times X_r$. The componentwise order on $Y$ is an order relation $⪯$ defined as follows: Given two tuples $(a_1,a_2,\mathrm{\dots },a_r)$ and $(b_1,b_2,\mathrm{\dots },b_r)\in Y$, we write $(a_1,a_2,\mathrm{\dots },a_r)⪯(b_1,b_2,\mathrm{\dots },b_r)$ iff $a_i{⪯}_i{b}_i$ for all $i\in [r]$. Note that we drop the subscript in $⪯$ whenever the order relation is a component-wise order. If the posets $(X_i,{⪯}_i)$, $i\in [r]$, are all the same poset $(X,⪯)$, we use ${⪯}^r$ to denote the componentwise order on $X^r$ and refer to it as the product order.

A lattice is a poset $L=(X,⪯)$ in which any two elements $x,y\in X$ have a (unique) greatest lower bound, or meet, denoted by $x\wedge y$, as well as a (unique) least upper bound, or join, denoted by $x\vee y$. We can uniquely identify $L$ by the tuple $(X,\vee ,\wedge )$. The bottom, or minimum, element in the lattice $L$ is denoted by $0_L:={\bigwedge }_{x\in L}x$. Likewise, the top, or maximum, element of $L$ is given by $1_L:={\bigvee }_{x\in L}x$. A lattice $L^{\prime }$ is a sublattice of $L$ if $L^{\prime }\subseteq L$ and $L^{\prime }$ has the same meet and join operations as $L$. In this paper we only consider distributive lattices, which are lattices whose meet and join operations satisfy distributivity; that is, $x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$ and $x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)$, for any $x,y,z\in L$. Note that a sublattice of a distributive lattice is also distributive. Every chain is a distributive lattice with $\max$ as join ($\vee$) and $\min$ as meet ($\wedge$).

Suppose we have a collection $L_1,\mathrm{\dots },L_k$ of lattices $L_i=(X_i,{\vee }_i,{\wedge }_i)$ with $i\in [k]$. The (direct) product lattice $L_1\times \mathrm{\dots }\times L_k$ is a lattice with ground set $X=\{(x_1,\mathrm{\dots },x_k):x_i\in L_i\}$ and join $\vee$ and meet $\wedge$ operations acting component-wise; that is, $x\vee y=(x_1{\vee }_1{y}_1,\mathrm{\dots },x_k{\vee }_k{y}_k)$ and $x\wedge y=(x_1{\wedge }_1{y}_1,\mathrm{\dots },x_k{\wedge }_k{y}_k)$ for any $x,y\in X$. The lattice $L^k$ is the product lattice of $k$ copies of $L$, and is called the $k$-th power of $L$. If $L$ is a distributive lattice, then $L^k$ is also distributive.

A crucial notion in this paper is that of join-irreducibles. An element $x$ of a lattice $L$ is called join-irreducible iff $x\ne 0_L$ and it cannot be expressed as the join of two elements $y,z\in L$ with $y,z\ne x$. In a lattice, any element is equal to the join of all join-irreducible elements lower than or equal to it. The set of join-irreducible elements of $L$ is denoted by $J(L)$. Note that $J(L)$ is a poset whose order is inherited from $L$. Due to Birkhoff’s representation theorem – a fundamental tool for studying distributive lattices – every distributive lattice $L$ is isomorphic to the lattice $𝒟(J(L))$ of ideals of its poset of join-irreducibles, with union and intersection as join and meet operations. See Figure 1 for an illustration.

Hence, a distributive lattice $L$ can be uniquely recovered from $J(L)$ and can thus be represented as the Hasse diagram of its poset of join-irreducibles, denoted by $G(J(L))$. We refer to $G(J(L))$ as a compact representation of $L$, since $J(L)$ is usually exponentially smaller than $L$. This representation is useful when designing algorithms, as the size of $G(J(L))$ is $O({|J(L)|}^2)$, while $L$ can have as many as $2^{|J(L)|}$ elements. Keep in mind, however, that Theorem 2 only guarantees the existence of such a compact representation; it does not provide a method to efficiently find the set $J(L)$.

Let $f:X\to ℝ$ be a real-valued function on a lattice $L=(X,⪯)$. We say that $f$ is submodular on $L$ if $f(x\wedge y)+f(x\vee y)\le f(x)+f(y)$, for all $x,y\in X$. If $-f$ is submodular in $L$, then we say that $f$ is supermodular in $L$ and just modular if $f$ is both sub and supermodular. The submodular function minimization problem (SFM) on lattices is, given a submodular function $f$ on $L$, to find an element $x\in L$ such that $f(x)$ is minimum. An important fact that we use in our work is that the sum of submodular functions is also submodular. Also, note that minimizing $f$ is equivalent to maximizing $-f$. It is known that a submodular function on a distributive lattice $L$ can be minimized in polynomial time in $|J(L)|$ – the number of join-irreducibles of $L$ [20, 27, 36, 4].

We now establish the first of the four lemmas.

By property 2 of Theorem 1, $L=(\mathrm{\Gamma },⪯)$ is a distributive lattice. Now, let $L^k=({\mathrm{\Gamma }}^k,{⪯}^k)$ be the $k$-th power of $L$. We know that the product of distributive lattices is distributive; hence $L^k$ is a distributive lattice. Moreover, since ${\mathrm{\Gamma }}_{\mathrm{lr}}^k\subseteq {\mathrm{\Gamma }}^k$, the poset $L^{\ast }$ is a sublattice of $L^k$. As any sublattice of a distributive lattice is itself distributive, the lemma follows. $◀$

Following the proof of the Distributivity Lemma, we now establish an equivalence between the costs of maximum diversity solutions in the sets ${\mathrm{\Gamma }}^k$ and ${\mathrm{\Gamma }}_{\mathrm{lr}}^k$. (Note that this is the same as establishing the equivalence between the sets ${\mathrm{\Gamma }}_k$ and ${\mathrm{\Gamma }}_{\mathrm{lr}}^k$, since a $k$-multiset over $\mathrm{\Gamma }$ has the same diversity as each of its up to $n!$ permutations – each a $k$-tuple – in ${\mathrm{\Gamma }}^k$.) For this, we use the notion of element multiplicity. Let $C\in {\mathrm{\Gamma }}^k$ be a $k$-tuple of solutions. The multiplicity ${\mu }_e(C)$ of an element $e\in E$, with respect to $C$, is the number of feasible solutions in $C$ that contain $e$. Since a feasible solution contains no repeated elements, ${\mu }_e(C)$ is also the number of times $e$ appears in the multiset sum of the solutions in $C$. An immediate consequence of property 1 of Theorem 1 is the following.

Let $X=(x_1,\mathrm{\dots },x_r)$ and $Y=(y_1,\mathrm{\dots },y_r)$, with $x_i,y_i\in E_i$ and $i\in [r]$, where $E_i$ is the $i$-th chain in the chain decomposition of $E$. By property 1, we know that the meet and join of two elements $L$ are given by componentwise minimum and maximum. That is,

Hence, if $x_i=y_i$, the element $x_i$ appears twice in the multiset sum $X\uplus Y$ and twice in the sum $(X\wedge Y)\uplus (X\vee Y)$. If $x_i\ne y_i$, then $x_i$ appears in either the join or the meet of $X$ and $Y$, and similarly for element $y_i$. Finally, if an element $e\in E$ is not in $X\cup Y$, then it is neither the minimum nor maximum of any entry and therefore cannot appear in $(X\wedge Y)\cup (X\vee Y)$. Since this holds for each $i\in [k]$, the observation is proven. $◀$

Observation 5 implies that the join and meet operations of the lattice $L$ of feasible solutions preserve element multiplicities. Consequently, any $k$-tuple in ${\mathrm{\Gamma }}^k$ can be reordered into a left-right ordered form while preserving element multiplicities, as stated in the following claim (see the proof in the full version).

Now, consider the pairwise-sum diversity measure introduced in Section 1. We can rewrite it directly in terms of the multiplicity as

which results from observing that ${\sum }_{e\in E}{\mu }_e(C)=k\cdot r$, for any $C\in {\mathrm{\Gamma }}^k$, with $r$ the cardinality of each solution in $C$. This formulation highlights that maximizing $d_{\mathrm{sum}}$ depends only on the distribution of elements across feasible solutions, rather than their specific ordering within a tuple $C$. Since the terms outside the latter summation in Eq. (1) are constant, the following lemma is an immediate consequence of Claim 6.

Lemma 7 tells us that in order to solve Max-Sum $k$-Diverse Solutions, we do not need to optimize over the set of $k$-element multisets of $\mathrm{\Gamma }$. Instead, we can optimize over the set ${\mathrm{\Gamma }}_{\mathrm{lr}}^k$ of $k$-tuples that are in left-right order. Moreover, it follows from Eq. (1) that maximizing $d_{\mathrm{sum}}$ is equivalent to minimizing

Hence, solving Max-Sum $k$-Diverse Solutions reduces to minimizing ${\widehat{d}}_{\mathrm{sum}}(C)$ in the lattice $L^{\ast }$. All we have left to do to complete the reduction to SFM is show that ${\widehat{d}}_{\mathrm{sum}}(C)$ is submodular in the lattice $L^{\ast }$.

We begin with two claims regarding the multiplicity function ${\mu }_e(C)$ on $L^{\ast }$. These claims rely crucially on property 1 of Theorem 1. Their proofs can be found in the full version of the paper. We use $E(C)$ to denote the set of elements ${\bigcup }_{X\in C}X$ for a tuple $C\in {\mathrm{\Gamma }}^k$.

We observe that Claim 8 holds in the lattice $L^k$, not just in the sublattice $L^{\ast }$ of left-right ordered $k$-tuples. In contrast, Claim 9 is specific to the sublattice $L^{\ast }$. The following proposition is an immediate consequence of these two claims and the convexity of the square function.

Proposition 10 states that, for each element $e\in E$, the square of the multiplicity function ${\mu }_e$ is submodular in the lattice $L^{\ast }$. Then, taking the sum of ${\mu }_e{(C)}^2$ over all elements $e\in E$ is also a submodular function; that is

Each sum in this inequality corresponds to the definition of ${\widehat{d}}_{sum}$ applied to the arguments $C_1\vee C_2$, $C_1\wedge C_2$, $C_1$ and $C_2$, respectively. Hence, we obtain the following.

While Lemmas 4, 7, and 11 already demonstrate the reduction of Max-Sum $k$-Diverse Solutions to SFM, this reduction alone does not guarantee an efficient algorithm. To complete the proof of Theorem 1, it remains to show that a compact representation of the left-right ordered lattice $L^{\ast }$ exists and can be constructed efficiently. By Birkhoff’s representation theorem, we need only specify the set of join-irreducibles of $L^{\ast }$ to obtain a compact representation in $O({|J(L^{\ast })|}^2)$ time. This is done in the following lemma, whose proof can be found in the full version of this work.

With Lemma 12, a compact representation of $L^{\ast }$ can be constructed in polynomial time. It is also clear that, given a $k$-tuple, the function ${\widehat{d}}_{\mathrm{sum}}$ can be evaluated efficiently. Then, by Theorem 3 and Lemmas 4, 7, 11, and 12, the proof of Theorem 1 is complete.

The following lemma is an immediate consequence of Claim 6, which states that any $k$-tuple in ${\mathrm{\Gamma }}^k$ can be reordered into a left-right ordered form while preserving element multiplicities.

Let $C\in {\mathrm{\Gamma }}^k$ be an arbitrary $k$-tuple of solutions, and let $\widehat{C}\in {\mathrm{\Gamma }}_{\mathrm{lr}}^k$ be its reordering into left-right order by the algorithm of Claim 6. For a feasible solution $X\in \mathrm{\Gamma }$, let $X(\mathrm{\ell })$ denote its $\mathrm{\ell }$-th component.

Consider the $k$-tuples $C(\mathrm{\ell })=(X_1(\mathrm{\ell }),\mathrm{\dots },X_k(\mathrm{\ell }))$ and $\widehat{C}(\mathrm{\ell })=({\widehat{X}}_1(\mathrm{\ell }),\mathrm{\dots },{\widehat{X}}_k(\mathrm{\ell }))$, where $X_i\in C$, ${\widehat{X}}_i\in \widehat{C}$ for all $i\in [k]$. These represent the $\mathrm{\ell }$-th component of each solution in $C$ and $\widehat{C}$, respectively. Now, define the function $f_{\mathrm{\ell }}:E_{\mathrm{\ell }}^k\to ℝ$ as:

By Claim 6, the multiplicity of each element in $C(\mathrm{\ell })$ is preserved in $\widehat{C}(\mathrm{\ell })$, implying that $f_{\mathrm{\ell }}(C(\mathrm{\ell }))=f_{\mathrm{\ell }}(\widehat{C}(\mathrm{\ell }))$. Since the absolute-difference diversity measure decomposes as:

it follows that $d_{\mathrm{abs}}(\widehat{C})=d_{\mathrm{abs}}(C)$. In particular, this holds for tuples that achieve maximum diversity. $◀$

In this case, the Submodularity Lemma actually becomes a Modularity Lemma. First, consider the function $f_{\mathrm{\ell }}^{\prime }:{\mathrm{\Gamma }}_{\mathrm{lr}}^2\to ℝ$ defined by $f_{\mathrm{\ell }}^{\prime }(X_1,X_2)=\Vert X_1(\mathrm{\ell })-X_2(\mathrm{\ell })\Vert$, where $X_1⪯X_2$, $\mathrm{\ell }\in [r]$, and $X(\mathrm{\ell })$ denotes the $\mathrm{\ell }$-th component of a solution $X\in \mathrm{\Gamma }$. We can rewrite the absolute difference diversity measure as:

If we can establish that $f_{\mathrm{\ell }}^{\prime }(\cdot )$ is modular in $L$, then, because the sum of modular functions is modular, $d_{\mathrm{abs}}$ would also be modular. We prove this in the following lemma.

We prove that, for any two $C_1,C_2\in {\mathrm{\Gamma }}_{\mathrm{lr}}^2$, the function $f_{\mathrm{\ell }}^{\prime }(\cdot )$ is modular in the lattice $({\mathrm{\Gamma }}_{\mathrm{lr}}^2,{⪯}^2)$, where $⪯$ is the componentwise order of the poset $L$ of feasible solutions. Since the sum of modular functions is modular, and $d_{\mathrm{abs}}$ can be written as a sum of functions $f_{\mathrm{\ell }}^{\prime }(\cdot )$ over all $\mathrm{\ell }\in [r]$, the modularity of $d_{\mathrm{abs}}$ follows.

Let $C_1=(X_1,X_2)$ and $C_2=(Y_1,Y_2)$. By definition, the join ($\vee$) and meet ($\wedge$) of $C_1$ and $C_2$ are given by componentwise maximum and minimum. Then, for each $\mathrm{\ell }\in [r]$,

Consider an arbitrary $\mathrm{\ell }\in [r]$. Because $C_1$ and $C_2$ are each in left-right order, we have: $X_1(\mathrm{\ell })⪯X_2(\mathrm{\ell })$ and $Y_1(\mathrm{\ell })⪯Y_2(\mathrm{\ell })$. Consider then the intervals $I_X=[X_1(\mathrm{\ell }),X_2(\mathrm{\ell })]$ and $I_Y=[Y_1(\mathrm{\ell }),Y_2(\mathrm{\ell })]$. Without loss of generality, assume that $X_2(\mathrm{\ell })⪯Y_2(\mathrm{\ell })$. There are three possibilities for the interaction of $I_X$ and $I_Y$: (i) the intervals are disjoint (i.e., $I_X\cap I_Y=\mathrm{\varnothing }$), they overlap (i.e., $I_X\cap I_Y\ne \mathrm{\varnothing }$), or (iii) one is contained in the other (i.e., $I_X\subset I_Y$). We now compare the sums $f_{\mathrm{\ell }}^{\prime }(C_1\wedge C_2)+f_{\mathrm{\ell }}^{\prime }(C_1\vee C_2)$ and $f_{\mathrm{\ell }}^{\prime }(C_1)+f_{\mathrm{\ell }}^{\prime }(C_2)$ in each of these cases.

In cases (i) and (ii), we have that $X_1(\mathrm{\ell })⪯Y_1(\mathrm{\ell })$ and $X_2(\mathrm{\ell })⪯Y_2(\mathrm{\ell })$. Hence,

and thus, modularity is satisfied.

In case (iii), we have $Y_1(\mathrm{\ell })⪯X_1(\mathrm{\ell })$ and $X_2(\mathrm{\ell })⪯Y_2(\mathrm{\ell })$. Then:

which again satisfies modularity.

Therefore, the function $f_{\mathrm{\ell }}^{\prime }(\cdot )$ is modular in $({\mathrm{\Gamma }}_{\mathrm{lr}}^2,{⪯}^2)$, and the lemma is proved. $◀$

By replacing the Cost-Equivalence and Submodularity lemmas of Section 3 with Lemmas 29 and 30 above, the proof of (the second half of) Theorem 28 is complete.