In this paper, we consider the bin covering problem with strong divisibility and rejection profit (the BC-SDRP problem, for short). Specifically, given a lot of identical bins with integer capacity L and a set \(A=\{a_{1},a_{2},\ldots ,a_{n}\}\) of n items with strongly divisible sizes, i.e., either \(s_{i}~|~s_{j}\) or \(s_{j}~|~s_{i}\) for each pair of two distinct items \(a_{i}\) and \(a_{j}\) in A and \(s_{\max }~|~L\) , where each item \(a_i\) in A has an integer size \(s_i\) and \(s_{\max }=\max \{s_{i}~|~a_{i}\in A\}\) , a bin with capacity L is called to be covered by the items if this bin receives some items with summation of sizes at least L, each item \(a_i\) in A is either put into a bin such that this bin used is covered, or rejected with rejection profit that we pay. No item can be put into more than one bin. We consider the BC-SDRP problem and its variation. (1) Given a rejection profit \(p\in \mathbb {R}^{+}\) , the BC-SDRP problem is asked to find a subset \(X\subseteq A\) and a scheme of items in X to cover some identical bins with capacity L, the objective is to maximize the number k(X) of such bins covered by items in X plus the total rejection profit \(p \cdot |A \setminus X|\) of rejected items not in X; (2) Given a rejection cardinality \(r_0\in \mathbb {Z}^{+}\) , the bin covering problem with strong divisibility and bounded rejection cardinality (the BC-SDBRC problem, for short) is asked to find a subset \(X\subseteq A\) and a scheme of items in X to cover some identical bins with capacity L under a constraint of the number of rejected items not in X at least \(r_0\) , the objective is to maximize the number k(X) of such bins covered by items in X.
As our main contributions, with the heavy aid of our exact algorithm in polynomial time provided to optimally solve the minimum cardinality bin covering problem with strong divisibility, we design two exact combinatorial algorithms to solve the BC-SDRP problem and the BC-SDBRC problem, respectively.
