How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?

Question

For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by

$$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} := \max\limits_{A, B} \left|\sum\limits_{i \in A, j \in B} m_{ij}\right|.$$

By expanding to a matrix so that the row and column sums are $0,$ both norms become essentially the same, i.e.,

$$\|M\|_{\infty \to 1} = 4 \|M\|_{\square}.$$

The idea is that due to the zero sums, the $1$'s in $x, y$ will represent $A, B$ respectively. This observation and usage of integer programming allows us to approximate the cut norm within a constant factor in polynomial time.

For finite sets $X, Y,$ we say $X < Y$ if $\max X < \min Y.$ I am interested in the following measurement: $$f(M) = \max\limits_{A < B < C \\ |A|=|B|=|C|} \left(\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij} \right).$$ Motivation: It's a measure of how much $M$ fails to increase as we move towards the diagonal from above, the useful property being that $f(M) \ge 0$ and $f(M) = 0$ if and only if $M$ increases towards the diagonal. The function $f$ also behaves well with the cut norm.

I can replace $C$ with $y \in \{-1,1\}^n$ and do the same row sum trick. It may be possible to replace $A$ and $B$ with $x \in \{-1, 0, 1\}^n$ and then use the column sum trick. However, there is a major problem: we are only considering $x$ with the same number of $1$s as $-1$s and where all the $-1$'s come after the $1$s.

Each such $x$ corresponds bijectively to a size $2m$ subset of $\{1, 2, \dots, n\}$ by making the first $m$ elements $1,$ the last $m$ elements $-1,$ and the rest $0.$ Thus, ignoring the constraint from $|C|,$ there are $\binom{n}{0} + \binom{n}{2} + \dots = 2^{n-1}$ ways to choose $A, B.$ To choose all of $A, B, C,$ there are of course $\binom{n}{0}+\binom{n}{3}+\dots = \frac{2^n + 2 \cos(n\pi/3)}{3}$ ways.

The cut norm was nicely reduced due to the natural correspondence between the $2^n$ subsets of $\{1, 2, \dots, n\}$ and the elements of $\{-1,1\}^n.$ Since we have neither $2^n$ nor $3^n$ choices for $A, B, C,$ plus the choices are not as clean, I am unable to turn computing $f$ into an integer programming problem. Is it possible in the case $M \ge 0$? It may be possible for all $M$ but I only care about non-negative matrices anyways.

Answer 1

Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize $$\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij}$$ subject to $A < B < C$ and $|A|=|B|=|C|$.

Introduce binary decision variables $a_i, b_i, c_i \in \{0,1\}$ to indicate whether $i\in A, i\in B, i\in C$, respectively. Introduce decision variable $d$ to represent the common cardinality. The problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (a_i c_j - b_i c_j)$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ \end{align} This is an integer quadratic programming (IQP) problem, but you can linearize by introducing binary variables $u_{ij}$ and $v_{ij}$ to replace the products $a_i c_j$ and $b_i c_j$, respectively. The resulting integer linear programming (ILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (u_{ij} - v_{ij})$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ a_i &\ge u_{ij} &&\text{for all $i$ and $j$} \tag1\label1 \\ c_j &\ge u_{ij} &&\text{for all $i$ and $j$} \tag2\label2 \\ a_i + c_j - 1 &\le u_{ij} &&\text{for all $i$ and $j$}\\ b_i &\ge v_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge v_{ij} &&\text{for all $i$ and $j$}\\ b_i + c_j - 1 &\le v_{ij} &&\text{for all $i$ and $j$} \tag3\label3 \end{align} For nonnegative $m_{ij}$, you can omit constraints \eqref{1}, \eqref{2}, and \eqref{3}.