Is there any better than a brute force method for finding the maximum $$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$ for $m,n \in \mathbb N^{+}$ and $v_{i,j} \in \mathbb Z$?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$– Community BotCommented Nov 16, 2022 at 18:27
-
2$\begingroup$ In other words, one needs to independently rotate the rows of a given $n\times m$ integer matrix $(v_{i,j})$ to maximize the sum of squares of its column sums. $\endgroup$– Max AlekseyevCommented Nov 18, 2022 at 12:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
You can solve the problem via binary quadratic programming as follows. Let binary decision variable $x_{id}$ indicate whether row $i$ is rotated $d$ places. The problem is to maximize $$\sum_{j=0}^{m-1} \left(\sum_{i=1}^n \sum_{d=0}^{m-1} v_{i,(j+d) \bmod m} x_{id} \right)^2$$ subject to $$\sum_{d=0}^{m-1} x_{id} = 1 \quad \text{for $i \in \{1,\dots,n\}$}.$$
You can either call an MIQP solver or linearize the products of binary variables and call an MILP solver.
-
$\begingroup$ Actually I found that MIQP solvers will mimize $x^{t}Px$ for some positive-semidefinite P. The problem of maximization apparently cannot be stated in a from required by the MIQP solver. Is that correct? $\endgroup$– user494931Commented Nov 19, 2022 at 12:45
-
$\begingroup$ I don’t have a recommendation for a Python MIQP solver, but if the one you’re using requires minimization, just negate the objective function. $\endgroup$– RobPrattCommented Nov 19, 2022 at 13:22
-
$\begingroup$ Sorry, I missed the positive semidefinite requirement for your solver. The usual linearization has $(mn)^2$ variables and $3(mn)^2$ constraints. A compact linearization has the same number of variables but “only” $(mn)^2+mn^2$ constraints. Yes, $2^{32}$ variables would be a challenge, but a brute force over $256^{256}$ is much worse. Does your $v$ matrix have any special properties? $\endgroup$– RobPrattCommented Nov 19, 2022 at 16:46
-
$\begingroup$ By the way, binary QP can always be rewritten with a positive semidefinite $Q$ by using $x^2=x$ to shift the diagonal to the linear part of the objective. $\endgroup$– RobPrattCommented Nov 19, 2022 at 16:53
-
$\begingroup$ Putting the pieces together: We start with maximizing $x^{t}Px$ and the restrictions for the binary vector $x$. Then we turn to minimizing $x^{t}P'x$ with $P'=-P+aI$ (the solution remains the same because of the restriction for $x$). We can now make all eigenvalues of $P'$ positive by using appropriate $a$. Then the MIQP solver can be applied ($P'$ is symmetric and positive semidefinite and we seek minimum of $x^{t}P'x$). Given this I consider the question answered. $\endgroup$– user494931Commented Nov 20, 2022 at 9:48