1

Given an $m*n$ positive matrix $\mathbf{A}$ and an integer $K$, where $0<K<n$.

Now, I have a $m*n$ binary matrix $\mathbf{B}$. I need to dertermine the value of each element in matrix $\mathbf{B}$. The objective is to

$$\text{minimize} ~~\sum_{0<j \leq n} { (~~\max_{0<i \leq m}\{A_{ij}B_{ij} \}~~) }$$

suject to: $$(\sum_{0<j\leq n}{B_{ij}}) = K~~ \text{for each} ~~i\in \{1, 2, \ldots, m\}$$.

This problem seems to be NP-hard to me## Heading ##. I have checked the NP problems listed here. But I am still not able to know from which problem I should try to reduce. Could anyone give me a hint? Thank you.

Thomas Andrews
  • 177,126

1 Answers1

0

This problem is not NP hard. Actually it can be reformulated as a linear problem and can be easily solved by the simplex algorithm. Let me show you how the reformulation works.

It is clear that the equality constraints are convex and linear. The difficulty of this problem lies in the target function part \begin{equation} \max_{0<i \leq m}\{A_{ij}B_{ij}\}. \end{equation} This part can be avoided by replacing it by the slack variable $ c_j $ which is an upper bound to $\{A_{ij}B_{ij}\} $ and inserting additional constraints \begin{equation} A_{ij}B_{ij} \leq c_j \rm{ ~~ for ~~all~~ }i \in \{1,\dots,m\}.\end{equation} Then, the original optimization problem becomes \begin{equation} \text{minimize} ~~\sum_{0<j \leq n} c_j \end{equation} subject to \begin{equation} A_{ij}B_{ij} \leq c_j \rm{ ~~ for ~~all~~ }i \in \{1,\dots,m\}, j \in \{1,\dots,m\}, \end{equation} \begin{equation} (\sum_{0<j\leq n}{B_{ij}}) = K~~ \text{for each} ~~i\in \{1, 2, \ldots, m\}. \end{equation} As this reformulated problem is a minization problem, $c_j$ will be chosen as small as possible such that \begin{equation} c_j = \max_{0<i \leq m}\{A_{ij}B_{ij}\}. \end{equation} (If \begin{equation} c_j \neq \max_{0<i \leq m}\{A_{ij}B_{ij}\}. \end{equation} it follows that $c_j > A_{ij}B_{ij},~~i \in \{1,\dots,m\}$ and $c_j$ can be decreased.)

The reformulated problem has a linear target function and linear equality and inequality constraints. Therefore, this is linear problem.