Maximizing a function defined in terms of meta notation

Question

Let $f : \mathbb{N}^n \to \mathbb{N}$ be the function defined by

$$f(w) = \sum\limits_{i=1}^m 1_A(M_iw)$$

where $M_i$ is the $i^{\text{th}}$ row of a matrix $M\in \text{Mat}_{m\times n}(\mathbb{N})$, $w$ is a column vector in $\mathbb{N}^n$, and

$$1_A(n) := \begin{cases}1 & n\in A\\0 & n \notin A\end{cases}$$

For concreteness, you can fix $A$ to be any set such that $|A| = 1$ and $M$ to be any nontrivial matrix.

How would one approach maximizing $f$? It seems like trial and error is the only approach.

Answer 1

Let $A=\{a\}$. You can solve the problem via mixed integer linear programming as follows. For $i\in\{1,\dots,m\}$, introduce binary decision variables $x_i$, $y_i$, and $z_i$, and let $\ell_i$ and $u_i$ be constant lower and upper bounds on $M_i w $. The problem is to maximize $\sum_{i=1}^m y_i$ subject to constraints: \begin{align} \ell_i x_i + a y_i + (a+1) z_i \le M_i w &\le (a-1)x_i + a y_i + u_i z_i &&\text{for $i\in\{1,\dots,m\}$}\\ x_i+y_i+z_i&=1 &&\text{for $i\in\{1,\dots,m\}$}\\ x_i &\in \{0,1\} &&\text{for $i\in\{1,\dots,m\}$}\\ y_i &\in \{0,1\} &&\text{for $i\in\{1,\dots,m\}$}\\ z_i &\in \{0,1\} &&\text{for $i\in\{1,\dots,m\}$} \end{align} If $x_i=1$, then $M_i w < a$. If $y_i=1$, then $M_i w = a$. If $z_i=1$, then $M_i w > a$.

Answer 2

Here's a way to handle your new $A$ set with $37m$ binary variables and $m+n$ integer variables. Let binary decision variable $x_{i,j}$ indicate that $M_i w = j\pmod {37}$. Then you want to maximize $\sum_{i=1}^m x_{i,15}$ subject to: \begin{align} M_i w &= 37p_i + \sum_{j=0}^{36} j\ x_{i,j} &&\text{for $i\in\{1,\dots,m\}$}\\ \sum_{j=0}^{36} x_{i,j} &= 1&&\text{for $i\in\{1,\dots,m\}$}\\ x_{i,j} &\in \{0,1\} &&\text{for $i\in\{1,\dots,m\}, j\in\{0,\dots,36\}$}\\ p_i &\in [0,36m] \cap \mathbb{Z}&&\text{for $i\in\{1,\dots,m\}$}\\ w_k &\in \mathbb{N}&&\text{for $k\in\{1,\dots,n\}$} \end{align}