Let $\mathbf{A}_{m\times n}$ be a matrix with non-negative elements. Assume that a submatrix $\mathbf{B}$ from $\mathbf{A}$ is defined as \begin{align} B_{i,j} = \begin{cases} A_{i,j}, & i\in\mathcal{I},\\ 0, & \text{otherwise}, \end{cases} \end{align} where $\mathcal{I}$ is a subset of $\{1,2,\cdots,m\}$.

For a constant size of $\mathcal{I}$, how does one should select $\mathcal{I}$ such that the following quantity becomes maximum $$\|\mathbf{B}^\mathrm{T}\mathbf{B}\|_1+\|\mathbf{B}\mathbf{B}^\mathrm{T}\|_1,$$ where $\|.\|_1$ is defined as the sum of the all elements of the matrix, and superscript $(.)^{\mathrm{T}}$ denotes the transpose operatrion.


You can solve the problem via integer programming as follows. For $i\in\{1,\dots,m\}$, let binary decision variable $x_i$ indicate whether row $i$ is selected. Then $B_{i,j}=A_{i,j}x_i$, so the problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^m A_{k,i} A_{k,j} x_k + \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^n A_{i,k} A_{j,k} x_i x_j$$ subject to $\sum_{i=1}^m x_i = s$, where $s$ is the desired cardinality of $\mathcal{I}$. Now use a mixed integer quadratic programming (MIQP) solver.

Alternatively, you can linearize the quadratic objective by introducing a new decision variable $y_{i,j} \ge 0$, with $1 \le i < j \le m$, to represent the product $x_i x_j$. The resulting mixed integer linear programming (MILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^m A_{k,i} A_{k,j} x_k + \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^n A_{i,k} A_{j,k} y_{i,j}$$ subject to linear constraints: \begin{align} \sum_{i=1}^m x_i &= s\\ y_{i,j} &\le x_i \\ y_{i,j} &\le x_j \\ y_{i,j} &\ge x_i + x_j - 1 \end{align} Optionally, you can use the cardinality constraint to strengthen the formulation by including an additional constraint $$\sum_{i:i<j} y_{i,j} + \sum_{i:i>j} y_{j,i} = (s-1) x_j$$ for $j\in\{1,\dots,m\}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.