Simplification of a binary matrix optimization problem

88 Views Asked by At

I am trying to find a binary matrix $X\in\{0,1\}^{I\times J}$ that solves the following optimization problem

\begin{align*} \min_{X}\quad&\sum_i\sum_j\exp(-2a_{ij}^2X_{ij})\\ \text{subject to}\qquad &\sum_i\sum_jX_{ij}=bn\\ &\sum_i X_{ij}\le n \,\,\forall j\\ &X_{ij}\in\{0,1\}\,\,\forall i,j \end{align*}

where each $a_{ij}\in\mathbb{R}$, and $b,n\in\mathbb{N}$. Is there any way to simplify this? Perhaps applying logarithms can help? Notice that the objective function is convex.

1

There are 1 best solutions below

2
On BEST ANSWER

In the objective instead of

$$\exp(-2a^2X_{ij})$$

you can write

$$1-X_{ij} + X_{ij}\exp(-2a^2)$$

and you have the same thing for $X_{ij}\in\{0,1\}$, but now it's linear.