1 Introduction↩︎

Let \(\mathcal{G}:=(\mathcal{I},\mathcal{A})\) be a directed acyclic graph where \(\mathcal{I}:= \{1,2,\dots,n\}\) is a set of \(n\) items, which are the vertices of \(\mathcal{G}\), and \(\mathcal{A}\) is its set of \(m\) arcs. An arc \((i,j) \in \mathcal{A}\) models the fact that item \(j\) precedes item \(i\), i.e., item \(i\) can be selected only if item \(j\) is selected as well. Each item \(i \in \mathcal{I}\) is associated to a (possibly negative) integer profit \(p_i\in\mathbb{Z}\) and a positive integer weight \(w_i\in\mathbb{Z}_{>0}\). Finally, let \(c \in\mathbb{Z}_{>0}\) be the positive integer capacity of a knapsack. Given these input data, the pckp asks for selecting a subset of items with maximum total profit such that their total weight does not exceed the knapsack capacity and they satisfy the precedence constraints induced by the arcs of the graph \(\mathcal{G}\). 1 shows a pckp instance and an optimal solution of the problem.

The pckp is NP-complete ([1], [2]) and it is a relevant generalization of the classical kp. The reader is referred to [3], [4] for comprehensive books on models and algorithms of the classical kp and its variants. The pckp arises naturally in many applications like investment planning ([5]), production planning ([6], [7]) and network design ([8]). Moreover, in the context of open pit mining problems, the pckp plays an important role, since it corresponds to the cpit ([9], [10]) with a single resource and a single time period.

The relaxed pckp without the capacity constraint is known in the literature as the mcp, see e.g., [11]. This problem asks for selecting a maximum-profit subset of items such that they satisfy the precedence constraints. The mcp is also referred to by different names in the mining literature such as upit [9] or the Open-Pit Mining Problem [12]. The mcp can be solved in polynomial time and efficient specialized algorithms have been developed. The related literature is extensive, we refer the interested reader to, e.g., [12]–[17].

We assume that \(\mathcal{G}\) does not contain directed cycles, since all items in such a cycle can be merged into a single one. We also assume that the knapsack capacity is strictly smaller than the total weight of all items. Otherwise, the capacity constraint is redundant, and the pckp reduces to the mcp.

In this paper, we develop a novel way of interpreting the structure of parametric optimal solutions of the lp relaxation of the natural ilp formulation for the pckp when varying the capacity. The mathematical structure of such solutions is known, see, e.g., [9], [17], and it is based on the knowledge of a parametric solution of the mcp. Our results reveal a new interpretation that links the structure of optimal lp solutions for the pckp and the kp. Indeed, in optimal lp solutions of the kp, items are selected to be put in the knapsack following their nonincreasing efficiencies given by the profit over weight ratio. One of the contributions of this work is to show that an analogous result holds for the pckp: subsets of items, which we call macroitems, are selected simultaneously in nonincreasing order of efficiency, defined as the ratio of their total profit to their total weight. The subsets of items can be obtained by maximizing this ratio while maintaining the relative precedences satisfied. We also characterize the structure of optimal dual solutions, thus providing a novel combinatorial interpretation for both primal and dual lp solutions. The optimal sequence of macroitems can be computed through parametric pseudoflow methods in \(O(mn\log n)\) time [18], which for the special case of forests becomes \(O(n^2\log n)\). We improve this bound by devising an \(O(n^2)\) algorithm for forests, and two \(O(n \log n)\) algorithms for the cases of in-forests or out-forests, i.e., forests where all items have in-degree or out-degree not larger than one, respectively. We also provide computational evidence that these improvements translate into practical performance gains over the parametric pseudoflow approach.

The remainder of the paper is organized as follows. In 2 we present the natural ILP formulation for the pckp and its LP relaxation. We then collect preliminary results on a parametric version of mcp. Finally, we introduce a related precedence-constrained ratio optimization problem. In 3 we introduce feasible and optimal sequences of macroitems and relate them to the breakpoints of the parametric closure value function. In 4 we show how the optimal sequence of macroitems determines primal and dual optimal solutions of the lp relaxation. In 5 we present the algorithms for directed forests and their complexity analysis. In 6 we describe the generation of the benchmark instances and report the computational comparison with the parametric pseudoflow approach. In 7 we summarize the main results and outline possible directions for future research.

2 The natural ILP formulation of the PCKP and its relaxations↩︎

For each item \(i \in \mathcal{I}\), let us introduce a binary variable \(x_i \in \{0,1\}\) taking value \(1\) if and only if item \(i\) is selected in the knapsack. Using these \(n\) binary variables, the natural ilp formulation for the pckp reads as follows: \[\label{eq:PCKP95int} \max_{{\boldsymbol{x}} \in \{0,1\}^{\mathcal{I}}} ~ \left\{~~ \sum_{i\in \mathcal{I}} p_i\, x_i:~~\sum_{i\in \mathcal{I}} w_i\, x_i \le c,~~~~ x_i-x_j \le 0,~~ (i,j)\in\mathcal{A}~~ \right\}.\tag{1}\] The objective function in 1 maximizes the total profit of the selected items. The capacity constraint in 1 imposes that the total weight of the selected items is no larger than the knapsack capacity. The precedence constraints in 1 impose respecting the precedence relationships between pairs of items, that is, if there is an arc \((i,j) \in \mathcal{A}\), item \(i\) can be selected only if item \(j\) is selected. The formulation 1 is called \(\mathscr{F}\) in the remainder of this manuscript. Moreover, we denote by \(\zeta(\mathscr{F})\) the optimal solution value of \(\mathscr{F}\), i.e., the optimal value of the pckp.

The \(\mathscr{F}\) formulation has been studied mainly from a polyhedral perspective. In particular, [19] investigates the polyhedron associated with the pckp and introduces clique-based facet-defining inequalities that strengthen the natural formulation. The work of [20] focuses instead on separation, developing procedures for finding maximally violated valid inequalities and showing how these cuts can be used to improve exact solution methods for the pckp.

2.1 Linear programming relaxation and its dual problem↩︎

By replacing the binary variables in 1 with the following continuous variables: \[x_i \in [0,1], ~~~ i\in\mathcal{I},\] we obtain the lp relaxation of \(\mathscr{F}\) which we denote by \(\mathscr{F}_\textrm{LP}\). Moreover, we denote by \(\zeta(\mathscr{F}_\textrm{LP})\) its optimal value that provides a valid upper bound on \(\zeta(\mathscr{F})\). In this paper, we are interested in determining the parametric optimal solutions to \(\mathscr{F}_\textrm{LP}\), for every possible capacity value \(c>0\).

Using a non-negative dual variable \(\lambda\) for the capacity constraint, a non-negative dual variable \(\alpha_{ij}\) for each precedence constraint corresponding to an arc \((i,j) \in \mathcal{A}\), and, for each item \(i \in \mathcal{I}\), a non-negative dual variable \(\mu_{i}\) for each less than or equal to one constraint, the dual problem of \(\mathscr{F}_\textrm{LP}\) reads as follows: \[\tag{2} \begin{align} \tag{3}&&\min_{\lambda \ge 0,{\boldsymbol{\alpha}}\ge \boldsymbol{0}, {\boldsymbol{\mu}}\ge \boldsymbol{0} }~~~ c \,\lambda +\sum_{i\in \mathcal{I}} \mu_i&\\[1 ex] \tag{4}&&w_i \,\lambda +\mu_i+\sum_{j\in\mathcal{I}^+(i)}\alpha_{ij}-\sum_{k\in\mathcal{I}^-(i)}\alpha_{ki} &\ge p_i, & i\in\mathcal{I}. \end{align}\] For each item \(i \in \mathcal{I}\), the set \(\mathcal{I}^+(i) := \{j \in \mathcal{I} : (i,j) \in \mathcal{A}\}\) is the set of its out-neighbors, and the set \(\mathcal{I}^-(i) := \{k \in \mathcal{I} : (k,i) \in \mathcal{A}\}\) is the set of its in-neighbors. The value of a variable \(\alpha_{ij}\) can be interpreted as a flow passing through the associated arc \((i,j) \in \mathcal{A}\) and, accordingly, \(\sum_{j\in\mathcal{I}^+(i)}\alpha_{ij}\) and \(\sum_{k\in\mathcal{I}^-(i)}\alpha_{ki}\) become the outgoing and incoming total flows of an item \(i \in \mathcal{I}\), respectively. Within this interpretation, constraints 4 impose for each item \(i \in \mathcal{I}\) that the difference between the outgoing and incoming total flows must be greater than or equal to the profit \(p_i\) of the item minus \(\lambda\) times the weight \(w_i\) of the item and the value of the variable \(\mu_i\).

We denote the LP formulation 2 by \(\mathscr{F}_\textrm{D(LP)}\) in the remainder of this manuscript. Moreover, we denote by \(\zeta(\mathscr{F}_\textrm{D(LP)})\) its optimal value, and, by the lp strong duality theorem, we have \(\zeta(\mathscr{F}_\textrm{LP})=\zeta(\mathscr{F}_\textrm{D(LP)})\).

2.2 Parametric maximum closure problem↩︎

An explicit solution of \(\mathscr{F}_\textrm{LP}\) is known since [17], and it is also derived in [9], where it is applied in relation with problems in mine production planning. This solution is based on the determination of the function \(u\colon[0,+\infty)\rightarrow \mathbb{R}\) given by \[\begin{align} \label{eq:UPIT95parametric} u(\lambda):=\max_{ {\boldsymbol{x}} \in \{0,1\}^{\mathcal{I}} } \left\{~ \sum_{i\in \mathcal{I}} (p_i-\lambda\,w_i)\,x_i:~~~ x_i-x_j \le 0,~~ (i,j)\in\mathcal{A} ~\right\}, \end{align}\tag{5}\] which is related to the Lagrangian relaxation of the capacity constraint in \(\mathscr{F}\). For a fixed \(\lambda\) problem 5 is known in the literature as the (maximum) closure problem on the graph \(\mathcal{G}\), which can be reduced to a max-flow/min-cut problem on an extended graph (see, for example, [16]).

We denote with \({\mathcal{P}}\) the set of feasible solutions of (5 ). Every feasible solution \(\boldsymbol{x}\) of 5 defines an affine function with equation \[f_{\boldsymbol{x}}(\lambda):=P(\boldsymbol{x})-\lambda\, W(\boldsymbol{x}),\] where, for any \(\boldsymbol{x}\in \{0,1\}^n\), we have \[P(\boldsymbol{x}):=\sum_{i\in\mathcal{I}}p_ix_i,\qquad W(\boldsymbol{x}):=\sum_{i\in\mathcal{I}}w_ix_i.\] With abuse of notation, for any \(M\subset\mathcal{I}\) we also write \[P(M):=\sum_{i\in M}p_i,\qquad W(M):=\sum_{i\in M}w_i.\] Note that \(f_{\boldsymbol{x}}\) is strictly decreasing if \(\boldsymbol{x}\ne 0\) because weights are always positive. Since the set \({\mathcal{P}}\) has finite cardinality, for every \(\lambda\ge 0\) the value \(u(\lambda)\) is defined as the largest of the finite number of values \(f_{\boldsymbol{x}}(\lambda)\), i.e., \[u(\lambda)=\max_{\boldsymbol{x}\in {\mathcal{P}}} f_{\boldsymbol{x}}(\lambda).\] Then, we have that the function \(u\) is a nonincreasing piecewise-affine convex function with a finite number of breakpoints. We indicate the breakpoints with the symbols \[\lambda_0=+\infty>\lambda_1>\lambda_2>\dots>\lambda_k>\lambda_{k+1}=0.\] Breakpoints \(\lambda_r\), with \(r\in\{1,2,\dots,k\}\), are \(\lambda\) values such that the set \[X^\star(\lambda)=\{\boldsymbol{x}\in {\mathcal{P}}\;:\;u(\lambda)=f_{\boldsymbol{x}}(\lambda)\},\] of optimal solutions of problem (5 ) is not a singleton.

To compute the function \(u\) and its breakpoints, one can systematically search for its distinct affine components by solving problem 5 for specific values of \(\lambda\). At these fixed values, the formulation simplifies into a standard non-parametric graph closure problem. This strategy is applied, for instance, in the implementation of the algorithms developed by [9] for the Open-Pit Mine Production Scheduling Problem. Alternative approaches leverage algorithms designed for the general parametric max-flow/min-cut problem, with the one presented in [18] representing the state of the art.

The next observation records the closure property of the feasible set of the parametric closure problem 5 , which is the basic order-theoretic ingredient used to compare its optimal solutions.

As already observed, each breakpoint \(\lambda_r\) is such that the set \(X^\star(\lambda_r)\) of optimal solutions of problem (5 ) for \(\lambda=\lambda_r\) is not a singleton. Note that if \(\boldsymbol{z}\in X^\star(\lambda_r)\), then the optimal value of (5 ) is \(f_{\boldsymbol{z}}(\lambda_r)=P(\boldsymbol{z})-\lambda_rW(\boldsymbol{z})\). The next result shows that the lattice structure discussed in 1 is inherited by the set of optimal solutions of the parametric closure problem at a breakpoint.

Now, for each breakpoint \(\lambda_r\) we set \[\begin{array}{lll} \boldsymbol{x}^{r-1}&=&\bigwedge\limits_{\boldsymbol{z}\in X^\star(\lambda_r)} \boldsymbol{z} \\ [8pt] \boldsymbol{x}^{r}&=&\bigvee\limits_{\boldsymbol{z}\in X^\star(\lambda_r)} \boldsymbol{z}, \end{array}\] i.e., \(\boldsymbol{x}^{r-1}\) is the minimal optimal solution in \(X^\star(\lambda_r)\), while \(\boldsymbol{x}^{r}\) is the maximal optimal solution in \(X^\star(\lambda_r)\). Obviously \(\boldsymbol{x}^r\geq \boldsymbol{x}^{r-1}\). Noticing that \(q(\lambda)\) is decreasing, then the maximal solution \(\boldsymbol{x}^r\) will be the unique optimal solution of (5 ) for \(\lambda\in (\lambda_{r+1},\lambda_{r})\), while the minimal solution \(\boldsymbol{x}^{r-1}\) will be the unique optimal solution of (5 ) for \(\lambda\in (\lambda_{r},\lambda_{r-1})\). Stated in another way, we have that \(u(\lambda)=f_{\boldsymbol{x}^r}(\lambda)\) for \(\lambda\in (\lambda_{r+1},\lambda_{r})\), while \(u(\lambda)=f_{\boldsymbol{x}^{r-1}}(\lambda)\) for \(\lambda\in (\lambda_{r},\lambda_{r-1})\). Note that the breakpoint \(\lambda_r\) is the intersection of the two lines \(f_{\boldsymbol{x}^{r-1}}(\lambda)\) and \(f_{\boldsymbol{x}^r}(\lambda)\), so that \[\label{eq:deflambdar} \lambda_r=\frac{P(\boldsymbol{x}^r-\boldsymbol{x}^{r-1})}{W(\boldsymbol{x}^r-\boldsymbol{x}^{r-1})}.\tag{8}\] The following theorem gives the main interpretation of each breakpoint: it is the best profit-to-weight ratio that can be obtained by adding a new feasible block of items.

The last observation in this section is a simple ratio property for disjoint sets, used later to compare unions of candidate macroitems.

2.3 A related ratio optimization problem↩︎

Let us also introduce the following precedence-constrained ratio optimization problem, which corresponds to the mcp with a fractional objective function. The problem reads as follows: \[\label{eq:ratio95problem} \max_{\boldsymbol{x} \in \{0,1\}^{\mathcal{I}}} \left\{ \frac{\sum_{i\in \mathcal{I}} p_i\, x_i}{\sum_{i\in \mathcal{I}} w_i\, x_i}:~~ x_i-x_j \le 0,\;(i,j)\in\mathcal{A},\quad \sum_{i\in\mathcal{I}}w_ix_i>0 \right\}.\tag{14}\] In this model, the coefficient \(p_i\) can be seen as the return, benefit, or revenue generated by item \(i\), while \(w_i\) may represent the amount of capital, budget, or resource consumption required to select it. Thus, the objective maximizes the return per unit of invested resource over all feasible solutions satisfying the precedence constraints. The strict positivity condition on the denominator simply excludes the empty solution. Ratio objectives of this type are classical in fractional programming [21], [22] and arise naturally when the goal is to maximize an efficiency measure. In finance, for instance, related ratios are used to compare returns with the amount of capital or risk required to obtain them, as in return-on-investment and risk-adjusted performance criteria [23]. Problem 14 is a combinatorial problem in its own right, and the results of this paper can be used to solve it efficiently.

3 Macroitems↩︎

In order to show the combinatorial structure of an optimal solution of \(\mathscr{F}_\textrm{LP}\), we introduce a few definitions.

In what follows we denote with \(\boldsymbol{x}^{\mathcal{M}}\) the binary vector corresponding to the indicator of set \({\mathcal{M}}\), i.e., \(\left(\boldsymbol{x}^{\mathcal{M}}\right)_i=1\) if and only if \(i\in {\mathcal{M}}\). We introduce the following definition.

For each macroitem \(\mathcal{I}_r\) in a feasible sequence, the profit \(P_r\) and the weight \(W_r\) are defined as \[P_r:=P(\mathcal{I}_r)=\sum_{i\in\mathcal{I}_r}p_i,\qquad W_r:=W(\mathcal{I}_r)=\sum_{i\in\mathcal{I}_r}w_i.\] We introduce the notion of split macroitem of a feasible sequence.

By the standing assumption on the capacity, the split macroitem exists for every feasible sequence. Given a feasible sequence of macroitems, we can construct a feasible solution of \(\mathscr{F}_\textrm{LP}\) as follows: \[x_i = \begin{cases} 1, & i \in \mathcal{I}_r,\quad r\in\{1,2,\dots,h(\mathcal{S})-1\},\\[8pt] \dfrac{c-\sum_{s=1}^{h(\mathcal{S})-1}W_s}{W_{h(\mathcal{S})}}, & i \in \mathcal{I}_{h(\mathcal{S})},\\[8pt] 0, & i \in \mathcal{I}_r,\quad r\in\{h(\mathcal{S})+1,h(\mathcal{S})+2,\dots,k(\mathcal{S})\}. \end{cases}\] In other words, we take entire macroitems of the ordered sequence up to the split macroitem, we put only a fraction of the split macroitem (the fraction needed to fill the capacity), and we do not take all the other macroitems. A feasible sequence of macroitems and its associated solution of maximum capacity for the example in 1, is represented in 2.

Note that the feasible solution found is very bad (it has negative profit) and it could easily be improved by just reordering the sequence of macroitems, while keeping it feasible. For this reason it is useful to introduce the following definitions.

Observing that \[\frac{P_r}{W_r}=\frac{P_{r+1}}{W_{r+1}}\;\;\Rightarrow\;\;\frac{P_r}{W_r}=\frac{P_{r+1}+P_r}{W_{r+1}+W_r},\] any nonincreasing sequence \(\mathcal{S}\) can always be replaced by a decreasing sequence by replacing each pair of macroitems with the same ratio with the union of the two macroitems.

Now we can define the sequences of macroitems which allow us to compute optimal solutions of \(\mathscr{F}_\textrm{LP}\).

The following result gives us the interpretation of the breakpoints of the function \(u\), as the profit/weight ratios associated to the macroitems in the optimal sequence with positive ratio. Recall that \(\mathcal{M}_1,\dots,\mathcal{M}_k\) are the subsets with indicator vectors \(\boldsymbol{x}^1,\dots,\boldsymbol{x}^k\), obtained by the iterative solution of Problem 9 . Following Remark 1, the sequence is extended to include also macroitems with negative profit. The first vectors of this sequence, more precisely, those with positive profit, are also those giving the affine pieces of the function \(u\) as explained in 1 1.

For the example of 1, the optimal sequence of macroitems has three elements \(\mathcal{I}_1\), \(\mathcal{I}_2\) and \(\mathcal{I}_3\) and they are represented in 3. In particular, \(P(\mathcal{I}_1)=4\), \(W(\mathcal{I}_1)=2\), \(P(\mathcal{M}_1)=4\), and \(\lambda_1=\frac{4}{2}\); \(P(\mathcal{I}_2)=6\), \(W(\mathcal{I}_2)=4\), \(P(\mathcal{M}_2)=10\), and \(\lambda_2=\frac{6}{4}\); and \(P(\mathcal{I}_3)=4\), \(W(\mathcal{I}_3)=4\), \(P(\mathcal{M}_3)=14\), and \(\lambda_3=\frac{4}{4}\).

In 4, we can find the plot of the function \(u\) for this example, this time indicating the breakpoints, which are the ratios of the macroitems in the optimal sequence.

4 Optimal Solutions of \(\mathscr{F}_\textrm{LP}\)↩︎

In this section, we will show that an optimal solution for \(\mathscr{F}_\textrm{LP}\) can be constructed as in the continuous relaxation of the classical knapsack problem, using an optimal sequence of macroitems, instead of just a nonincreasing sequence of simple items. An analogue to the classical knapsack also holds for the dual problem, and for the optimal multiplier in the Lagrangian relaxation of the capacity constraint.

For the rest of the discussion we consider optimal sequences of macroitems \(\mathcal{S}=(\mathcal{I}_1,\mathcal{I}_2,\dots,\mathcal{I}_{k(\mathcal{S})})\) and we assume that the split macroitem \(\mathcal{I}_{h(\mathcal{S})}\) has a positive profit. Indeed, otherwise, all macroitems in the sequence with a positive profit, would fit in the capacity \(c\). In that case the optimal solution is easily given by taking all items contained in all macroitems with positive profit. Moreover, we define the residual capacity \(\tilde{c}(\mathcal{S})\) as \[\label{res95cap} \tilde{c}(\mathcal{S}) = c - \sum_{r=1}^{h(\mathcal{S})-1} W_{r}.\tag{15}\] The following theorem establishes the optimal solution of \(\mathscr{F}_\textrm{LP}\) and of the corresponding dual problem \(\mathscr{F}_\textrm{D(LP)}\).

It follows from 3 that the optimal value of \(\mathscr{F}_\textrm{LP}\) and \(\mathscr{F}_\textrm{D(LP)}\) is \[\label{eq:PCKP95value} \sum_{r = 1}^{h(\mathcal{S})-1} P_{r} + P_{h(\mathcal{S})} \,\frac{\tilde{c}(\mathcal{S})}{W_{h(\mathcal{S})}}.\tag{21}\]

As an illustration of the previous result, we refer to 3 for the optimal solution of the \(\mathscr{F}_\textrm{LP}\) arising from the graph in 1, while in 5 we represent the flow inside the macroitems, which gives the optimal solution of the dual problem \(\mathscr{F}_\textrm{D(LP)}\), for the same example.

\(\;\)

The final result concerns the value of the optimal multiplier for the Lagrangian relaxation of the capacity constraint, i.e., the optimal solution of the dual Lagrangian problem. This is the solution of \[\label{eq:opt95multiplier95prob} \min_{\lambda\ge 0}\left(c\,\lambda+\max_{x \in {\mathcal{P}}} \sum_{i\in \mathcal{I}} (p_i-\lambda\, w_i)x_i\right)=\min_{\lambda\ge 0} c\,\lambda+u(\lambda).\tag{22}\]

We denote the optimization problem 22 by \(\mathscr{F}_\textrm{LAG}\) in the remainder of this manuscript. Moreover, we denote by \(\zeta(\mathscr{F}_\textrm{LAG})\) its optimal value.

We are able to prove the following result, analogous to the one for the classical knapsack problem:

The plot of the objective function of \(\mathscr{F}_\textrm{LAG}\) for the example of 1 with capacity \(c=4\) is represented in 6. Note that since in this case \(h=2\), the minimum of the function \(c\,\lambda+u(\lambda)\) is attained at \(\lambda_2=\frac{6}{4}\), which is the ratio of the split macroitem \(\mathcal{I}_2\).

5 Algorithms for computing the optimal sequence of macroitems on directed forests↩︎

In this section, we present new algorithms for computing the optimal sequence of macroitems when the precedence graph \(\mathcal{G}\) is a directed forest, i.e., a disjoint union of directed trees. We show that, despite the additional combinatorial structure imposed by the precedence constraints, the optimal sequence can be computed with an \(O(n^2)\) algorithm, where \(n\) is the number of items. We further show that when the arcs are all directed in the same direction (i.e., the forest is composed of out-trees or in-trees), a close variant of this algorithm reduces the complexity to \(O(n \log n)\), matching the time needed to compute the parametric LP relaxation of the classical kp for all capacity values, which requires sorting items by efficiency and thus runs in \(O(n \log n)\) [3], [4]. As already discussed in the Introduction, the optimal sequence of macroitems can also be obtained on arbitrary precedence graphs via parametric flow algorithms in \(O(mn \log n)\) time, where \(m\) is the number of arcs [18]; on forests, where \(m = O(n)\), this general-purpose bound becomes \(O(n^2 \log n)\), and the algorithms introduced in this section improve on it by exploiting the tree structure directly. A computational comparison between these two approaches is provided in 6.

5.1 Notation↩︎

In order to describe the algorithms of this section, we introduce the following notation.

An illustration of preceding/succeeding sets associated to items and arcs, and of final/initial items, can be found in 7, while an illustration of the sets \(\mathcal{M}^+(\mathcal{M}')\) and \(\mathcal{M}^-(\mathcal{M}')\) is in 8.

Notice that a sequence \(\mathcal{S}=\big(\mathcal{I}_1,\mathcal{I}_2,\dots,\mathcal{I}_{k(\mathcal{S})}\big)\) of macroitems is feasible if and only if for every item \(j\in \mathcal{I}\), all items in \(F_j\) are contained in macroitems of the sequence \(\mathcal{S}\) that precede the macroitem containing \(j\), or are contained in the same macroitem. Furthermore, given an arc \(a=(i,j)\), item \(i\) can be in the same macroitem as item \(j\) only if all items in \(F_a\) are contained in a macroitem of the sequence \(\mathcal{S}\) that precedes the macroitem containing \(j\), or are contained in the same macroitem.

5.2 Main algorithm to compute the optimal sequence of macroitems on a forest↩︎

To show that our main algorithm outputs the optimal sequence of macroitems we prove three propositions.

An illustration of the outcome of the constructive procedure described in the proof of 4 can be found in 9.

5 allows us, by collapsing the arc \(a^*\), to reduce the problem of finding the optimal sequence of macroitems to a smaller graph. An illustration of such an operation on an instance can be found in 15, where a full run of the main algorithm is presented.

In 10, after the initialization (lines [ln:start95init]-[ln:end95init]), which creates a copy \((\mathcal{I}',\mathcal{A}')\) of the graph and associates to each copied item \(j\) a set of items \(\mathcal{M}_j\subset\mathcal{I}\) in the original graph, then in the main cycle (lines [ln:start95main95cycle]-[ln:end95main95cycle]) at each iteration we either find a new macroitem in the optimal sequence as prescribed by 6, and we remove it from the graph \((\mathcal{I}',\mathcal{A}')\), or we “contract” an arc joining two adjacent items according to 5.

In particular, in procedure FindBestWing (11) we determine the arc \(a^*=(u,v)\in\mathcal{A}'\) whose associated set \(F_{a^*}\) is the one with the largest ratio. Then, in procedure FindBestFinalNodes (12) we determine the set \(\mathcal{B}_\textrm{f}\) of the final items of \(\mathcal{I}'\) with the largest ratio. Now, if the largest determined ratio is achieved only by the final items in \(\mathcal{B}_\textrm{f}\), then the subset of items \(\bigcup_{f\in\mathcal{B}_\textrm{f}}\mathcal{M}_f\subset\mathcal{I}\) is the next macroitem in the optimal sequence by 6. Hence, procedure RemoveFinalNodes (13) adds to the optimal sequence the new macroitem, and removes the items in \(\mathcal{B}_\textrm{f}\) together with the corresponding arcs from the graph \((\mathcal{I}',\mathcal{A}')\). Conversely, if the largest determined ratio is achieved by (or also by) a set \(F_{a^*}\subset\mathcal{I}'\) associated to some arc \(a^*\in\mathcal{A}'\), procedure ContractArc (14) removes arc \(a^*=(u,v)\) from \(\mathcal{A}'\) according to 5, joining the two items \(u\) and \(v\) and the corresponding sets \(\mathcal{M}_u\), \(\mathcal{M}_v\) of associated items in \(\mathcal{I}\). An illustration of a full run of 10 on a small instance can be found in 15.

5.3 Dual Variant↩︎

10 finds the macroitems in the optimal sequence in decreasing order with respect to their ratio. It is possible to devise an analogous variant of 10, which finds the macroitems in the optimal sequence in increasing order. In this variant, instead of computing the ratio of final items and preceding sets, we need to compute the ratio of initial items and succeeding sets, namely the sets \(\mathcal{I}_\textrm{i}\), \(B_j\) and \(B_a\) already introduced in 5.1. A graphical illustration of initial items, and succeeding sets associated to items and arcs, can be found in 7.

We have the following three propositions, whose proofs are analogous to those of 4 5 6, and we omit them in this paper.

Thanks to these results, 10 can be converted to find the macroitems in the optimal sequence in increasing order with respect to their ratio. We refer to this algorithm as the dual variant of 10, and an illustration of a full run of this dual variant can be found in 16.

We also have the same complexity of \(O(n)\) per iteration and \(O(n^2)\) total complexity, for which we give only the statement, since the proof is analogous to the one of 5.

5.4 Improved variants with all out-trees or all in-trees↩︎

If we know that the forest graph \(\mathcal{G}\) is composed of all trees whose arcs all point in the same direction, we can employ a heap data structure in 10 and obtain a better total complexity of \(O(n\log n)\). To describe this variant we first give the definition of out-tree and in-tree.

17 is devised for in-trees. In the initialization (lines [ln:heaped95start95init]-[ln:heaped95end95init]) we create a copy of the set of items and we insert the elements in a heap with respect to their ratio. Then in the main cycle (lines [ln:heaped95start95main95cycle]-[ln:heaped95end95main95cycle]), at each iteration we extract the item \(g\) at the top of the heap. If item \(g\) is a final item, we add it to the current (or to a new) macroitem (lines [ln:heaped95start95if95best95final]-[ln:heaped95end95if95best95final]), we delete it from the graph and we update the heap accordingly. If item \(g\) is not a final item, we contract the only arc exiting \(g\) and we update the heap accordingly.

6 Computational Results↩︎

This section evaluates the practical performance of the algorithms developed in 5. All algorithms were implemented in C++ and run single-threaded, and all experiments were conducted on a Linux machine equipped with an Intel i7-12700 processor (2.1 GHz) and 32 GB of RAM. We first describe the generation of the benchmark instances used throughout the section. We then justify the heap-based implementation of the main forest algorithm by comparing it with a non-heap implementation of the same algorithm. We then study how the heap-based algorithm scales on the instances with a large number of items, and we assess the impact of the specialized variants for in-trees and out-trees. Finally, we compare the heap-based forest algorithm with a bounded-precision implementation of the parametric pseudoflow approach.

6.1 Instance Generation↩︎

This section describes the generation of the benchmark instances used throughout the computational experiments. The instances are grouped by number of items, forest density, orientation pattern, and profit-weight correlation class.

Each benchmark instance is obtained by combining two independent components: the item coefficients, namely weights and profits, and the precedence graph. The item coefficients are generated following the standard test classes used for the classical knapsack problem [26]. For each item \(i\), the weight \(w_i\) is sampled uniformly from \(\{1,2,\dots,R\}\), with \(R=1000\). Profits are generated according to three classes: uncorrelated (uncorr), where \(p_i\) is sampled independently and uniformly from \(\{1,2,\dots,R\}\); weakly correlated (weakly-corr), where \(p_i\) is sampled uniformly from the integer interval between \(\max\{1,w_i-R/10\}\) and \(w_i+R/10\); and strongly correlated (strongly-corr), where \(p_i=w_i+R/10\). We also generate signed variants of these three classes by independently changing the sign of each profit with probability \(0.25\). We denote them by uncorr-neg, weakly-corr-neg, and strongly-corr-neg, respectively.

The second component is the precedence graph. We consider three families of directed forests. In an in-forest, every item has out-degree at most one. It is generated by scanning items \(i \in \{1,2,\dots,n-1\}\) and, independently with probability \(\rho\), adding one arc \((i,j)\) with \(j\) chosen uniformly from \(\{i+1,i+2,\dots,n\}\). In an out-forest, every item has in-degree at most one. It is generated by scanning items \(i \in \{2,3,\dots,n\}\) and, independently with probability \(\rho\), adding one arc \((j,i)\) with \(j\) chosen uniformly from \(\{1,2,\dots,i-1\}\). Finally, in a gen-forest, we first generate an undirected forest by connecting each item \(i \in \{2,3,\dots,n\}\) to a uniformly chosen predecessor \(j<i\) with probability \(\rho\), and then orient each selected edge independently in one of the two possible directions with probability \(0.5\). The density parameter is \(\rho\in\{0.3,0.6,0.9,1.0\}\), referred to as sparse, medium, dense, and conn, respectively. The first three density classes generate forests, possibly with several connected components. The class conn corresponds to \(\rho=1.0\) and therefore generates a connected forest, which is in fact a single spanning tree. For every combination of topology, profit-weight class, density, and size, we generate \(10\) independent instances.

We use two main test beds in the computational experiments. The medium-sized test bed contains \(7\,200\) instances: all three topologies, all six profit-weight classes, all four density values, and ten seeds for each size in \(n \in \{100,200,300,\dots,1\,000\}\). The large-sized test bed contains \(7\,200\) instances with the same combinations of topologies, profit-weight classes, densities, and seeds, for each size in \(n \in \{10\,000,20\,000,\dots,100\,000\}\).

6.2 Justification of the Heap-Based Variant↩︎

We implemented the main algorithm of the paper in a heap-based version, following the practical variant anticipated in 10. We refer to this implementation as the Heap-based Forest Macroitem Algorithm (HFMA). To isolate the effect of the heap data structure, we compare HFMA with a non-heap implementation of the same forest macroitem algorithm, denoted by FMA. This implementation follows 10 and uses the same incremental updates of closure sums as HFMA, but it selects the maximum-ratio final item or arc by direct linear scans, instead of maintaining the candidate ratios in a heap.

We tested both algorithms on the gen-forest instances of the medium-sized test bed, plus the sizes \(n=10\,000\) and \(n=20\,000\) of the large-sized test bed. 18 reports the average CPU time of HFMA and FMA on these benchmark instances. Each point is the mean over all profit-weight classes, arc densities, and seeds available for that value of \(n\).

The two implementations have comparable running times on the smallest instances, where the overhead of maintaining a heap offsets the benefit of faster selection. As \(n\) grows, however, the repeated linear scans of FMA become dominant. At \(n=1000\), FMA is about \(2.0\) times slower than HFMA; at \(n=10000\), the gap increases to about \(17.6\) times, and at \(n=20000\) it further widens to about \(33.1\) times. This confirms that the heap-based implementation, despite not being asymptotically preferable in the worst-case analysis, is suitable to obtain stable performance on larger forest instances.

6.3 Scaling of HFMA↩︎

We now evaluate the scalability of HFMA on the gen-forest instances of the large-sized test bed. 19 reports, for each value of \(n\), the number of tested instances and the corresponding mean CPU time. Each row averages over all profit-weight classes, arc densities, and seeds, for a total of \(240\) instances.

The observed growth is smooth over the whole large-sized range. The CPU times appear to follow a \(O(n\log n)\) growth. This empirical behavior is well below the worst-case complexity \(O(n^2\log n)\) of the heap-based implementation on general forests. But this is not in conflict with the theoretical analysis, since the complexity result refers to a worst-case analysis, whereas the reported times are averages over the generated benchmark instances.

6.4 Specialized Variants for In-Trees and Out-Trees↩︎

We finally evaluate the specialized heap-based variants for forests composed only of in-trees or only of out-trees. We denote by HIMA the Heap-based In-tree Macroitem Algorithm and by HOMA the Heap-based Out-tree Macroitem Algorithm. The former is the algorithm of 5.4; the latter is the dual heap-based variant described in 11. Both are tested on the corresponding large-sized instances.

20 reports the number of tested instances and the mean CPU times of the specialized algorithms.

In this case, the CPU times of both HIMA and HOMA display a \(O(n\log n)\) growth, which is aligned with the worst-case complexity of these algorithms. To quantify the benefit of specialization, we compute, for each value of \(n\), the ratio between the mean CPU time of HFMA and the mean CPU time of the specialized algorithm, both measured on the same set of instances (in-forest instances for HIMA, out-forest instances for HOMA). With this measure, HIMA is between \(7.5\) and \(9.8\) times faster than HFMA on in-forest instances, while HOMA is between \(4.3\) and \(5.0\) times faster than HFMA on out-forest instances.

6.5 Comparison with Pseudoflow↩︎

As a benchmark against a general parametric-flow approach, we use the Bounded-Precision Parametric Pseudoflow algorithm (BPPF), namely the public implementation of Hochbaum’s parametric pseudoflow method available at https://github.com/hochbaumGroup/Bounded-precision-simple-parametric.git.

We compare HFMA and BPPF on the gen-forest instances of the medium-sized test bed. This gives \(2\,400\) instances, obtained from all \(6\) profit-weight classes, all \(4\) arc densities, and \(10\) seeds for each value of \(n\). For each instance, HFMA computes the optimal sequence of macroitems and the corresponding breakpoint ratios. The same instance is also solved by BPPF, and the two outputs are compared in terms of the number and composition of macroitems.

21 reports the CPU time comparison. The table on the left gives, for each value of \(n\), the number of tested instances, the average CPU time of HFMA and BPPF, and their ratio. The plot on the right represents the same average CPU times as a function of \(n\).

The gap between HFMA and BPPF widens as \(n\) grows: the ratio BPPF/HFMA increases from about \(1.7\times\) at \(n=100\) to about \(5.1\times\) at \(n=1000\), roughly tripling over the range. This is consistent with BPPF solving a general parametric minimum-cut problem on the whole network, whereas HFMA exploits the special forest structure of the precedence graph directly, so its running time grows more slowly with \(n\).

As a consistency check for the performance comparison, we also verified the macroitem partitions returned by the two algorithms. Since BPPF is a bounded-precision implementation, we ran it with a specified tolerance of \(10^{-6}\) on the input coefficients and on the resulting breakpoint ratios. The number and composition of the macroitems coincide on \(2\,392\) out of the \(2\,400\) tested instances. In the remaining \(8\) instances, BPPF merges two consecutive macroitems whose breakpoint ratios differ by less than this tolerance. These cases occur only for instances with \(700\le n\le 1\,000\). This is consistent with the numerical-precision issue discussed in 7. The precision parameter of BPPF cannot be increased without qualification: the implementation scales decimal capacities to integers, and using more decimal digits increases the magnitude of the internal integer coefficients, thereby creating overflow. We also tested BPPF on instances with more than \(1000\) items, but on these instances the same numerical-precision issues prevent a reliable comparison with HFMA.

7 Conclusion↩︎

In this paper we have studied the combinatorial structure of optimal solutions of the LP relaxation of the natural ILP formulation of the Precedence Constrained Knapsack Problem (PCKP).

Our central contribution is the introduction of the concept of optimal sequence of macroitems, an ordered partition of the item set into precedence-closed groups ranked by nonincreasing profit-to-weight ratio, and the proof that this sequence fully characterizes optimal LP solutions. Specifically, the optimal LP solution assigns value \(1\) to all items in macroitems preceding the split macroitem, a common fractional value to all items in the split macroitem, and \(0\) to all remaining items. This result generalizes the classical greedy structure of LP-optimal solutions, where the role of individual items is taken over by macroitems.

We have further characterized the structure of optimal dual solutions, showing that they correspond to feasible flows within each macroitem of the optimal sequence. As an additional consequence, we have identified the optimal Lagrangian multiplier for the capacity constraint as the profit-to-weight ratio of the split macroitem, recovering the analogue of the classical result for the standard Knapsack Problem.

On the algorithmic side, we have presented an \(O(n^2)\) algorithm for computing the optimal sequence of macroitems when the precedence graph is a directed forest, based on iterative contraction of the arc with the highest profit-to-weight ratio among all minimal preceding sets. When the forest is composed of in-trees (or out-trees), we have shown that a heap-based variant of the algorithm achieves \(O(n \log n)\) complexity, by exploiting the fact that each arc’s minimal preceding set is a singleton in this case. As a by-product, since its optimal solution coincides with the first (resp.last) macroitem of the optimal sequence, the same algorithms also compute the optimal solution of the precedence-constrained ratio optimization problem 14 introduced in 2.3, within the same complexity bounds.

An interesting open future research direction is to study whether efficient algorithms for computing the optimal sequence of macroitems can be devised beyond the forest case, and whether the LP structure identified here can be embedded into branch-and-bound frameworks to yield improved exact algorithms for the PCKP.

Code and Data Availability↩︎

The source code and computational material used in the experiments are available online, with the aim of stimulating further research on these topics and facilitating reproducible comparisons. The code repository is https://github.com/fabiofurini/macroitems-cpp; it contains the C++ implementation of the forest macroitem algorithms and the scripts used to reproduce the benchmark runs. The data repository is the data directory of the same GitHub repository: https://github.com/fabiofurini/macroitems-cpp/tree/main/data; it contains the raw CSV files underlying the computational figures and tables. In particular, the data files report one row per tested instance and include the instance class, topology, density, seed, number of macroitems, and running time. The pseudoflow comparison uses the public Bounded-Precision Parametric Pseudoflow implementation available at https://github.com/hochbaumGroup/Bounded-precision-simple-parametric.git.

References↩︎