This costs minimization problem, is it solvable in polynomial time?

Question

I have the following problem: I have $c$ conflicts, named $(c_1, \ldots, c_c)$, where each conflict $c_i$ has certain size $s_i\in\mathbb{N}_0$: the number of times conflict $c_i$ has happened. Also, I have $m$ conflict resolution methods, named $(m_1, \ldots, m_m)$. Each method $m_j$ cannot be used more than $u_j\in\mathbb{N}_0$ times, and each time you use it, you have to pay $p_j\in\mathbb{N}_0$ dollars, but you get that each conflict $c_i$ connected to $m_j$ is reduced by $\min(r_{ji}, s_i)$ units ($s_i \leftarrow s_i - \min(r_{ji}, s_i)$, for each $c_i$ connected to $m_j$).

Once some $s_i=0$, the corresponding $c_i$ must be removed, and once some $u_j=0$, node $m_j$ cannot be used anymore so it can be removed as well.

The problem is solving all conflicts (making every node $c_i$ dissapear after making $s_i=0$) by repeated uses of the available methods, expending a minimal amount of money.

For example, if we call $E$ our total expended money (with an initial value of $0$), and, for the sake of simplicity, assume that every $r_{ji} = 1$, one use of $m_2$ implies the following updates:

E <- E + p
u2 <- u2 - 1   # If u2 becomes 0, remove m2 from the graph.
s3 <- s3 - 1   # If s3 becomes 0, remove c3 from the graph.
s4 <- s4 - 1   # If s4 becomes 0, remove c4 from the graph.
s5 <- s5 - 1   # If s5 becomes 0, remove c5 from the graph.

It's guaranteed that all conflicts can be solved. In other words, each $s_i\leq\sum_j(\{r_{ji}*u_j : m_j\text{ is neighbor of }c_i\})$.

Can this problem be solved polynomically? My guess is yes by using first the method that has the least "cost-per-conflict". In other words, at each iteration, make one use of the $m_j$ that minimizes $p_j/\sum_i(\{min(r_{ji},s_i) : c_i\text{ is neighbor of }m_j\})$ and afterwards remove all nodes that became $0$.

But, since the removal of conflicts increases the "costs-per-conflict" of the surviving methods for the next iteration, I'm not sure if this eager algorithm will lead to an optimal solution or whether a solution algorithm requires dealing with combinatorial explosion to be optimal.

In other words; I'm not sure if such eager algorithm causes that early eager choices will force an unneccesary number of uses of more expensive methods later, avoidable by not taken so eager choices earlier, like any other NP-hard problem.

Answer 1

It's a bad practice to use the same variable for two purposes, so I'll say that you have $C$ conflicts $(c_1, c_2, \dots, c_C)$ and similarly $M$ conflict resolution methods. To simplify, let $r_{ji} = 0$ if $c_i$ and $m_j$ are disconnected.

Suppose $t_j$ is a variable indicating how many times method $m_j$ was used we can phrase your problem as

\begin{align} \min \quad&\sum_{j}p_jt_j\\ \text{s.t.}\quad&\forall i: \sum_j r_{ji}t_j \geq s_i\,,\\ &\forall j:0\leq t_j \leq u_j\,,\\ & \forall j:t_j \in \mathbb{N}_0\,. \end{align}

What if instead we assume we always start by using every $m_j$ as much as possible, and $n_j$ represents the number of times we do not use $m_j$ (compared to the maximum allowed). Note that $t_j = u_j - n_j$. Substituting gives us

\begin{align} \min \quad&\sum_{j}p_j(u_j-n_j)\\ \text{s.t.}\quad&\forall i: \sum_j r_{ji}(u_j-n_j) \geq s_i\,,\\ &\forall j:0\leq(u_j-n_j) \leq u_j\,,\\ & \forall j:n_j \in \mathbb{N}_0\,, \end{align} which is equivalent to \begin{align} \max \quad& \sum_{j}p_jn_j\\ \text{s.t.}\quad&\forall i: \sum_j r_{ji}n_j \leq -s_i + \sum_j r_{ji}u_j\,,\\ &\forall j:0 \leq n_j \leq u_j\,,\\ & \forall j:n_j \in \mathbb{N}_0\,. \end{align}

But this is exactly the $M$-dimensional bounded knapsack problem. Thus your problem is NP-hard, but you also get to benefit from the existing literature that give very good practical solvers.