Let’s say I have the following N polynomials:
$f_{1}(\boldsymbol{x}) = \Sigma_{i = 1}^{K} a_{1i} x_{i}$
$f_{2}(\boldsymbol{x}) = \Sigma_{i = 1}^{K} a_{2i} x_{i}$
...
$f_{N}(\boldsymbol{x}) = \Sigma_{i = 1}^{K} a_{Ni} x_{i}$
where $\boldsymbol{x} = (x_{1}, ..., x_{K})$ is a K-dimensional vector that takes either $0$ or $1$ as elements and $a_{ni}$ is an integer factor for each $x_{i}$ that can be a negative number.
I would like to create a vector $\boldsymbol{x} = (x_{1}, ..., x_{K})$ that makes $|f_{1}(\boldsymbol{x})|$ as large as possible while making $|f_{2}(\boldsymbol{x})|, \cdots, |f_{N}(\boldsymbol{x})|$ as small as possible.
What is this 0-1 combinatorial entity called and how do I solve this?
One naive formulation which reduces to solving mixed-integer linear programs is: \begin{equation} \max_{x\in \{0,1\}^K} \ |f_1(x)| \qquad \mbox{ subject to } \quad |f_i(x)|\le \epsilon, \quad 2\le \forall i\le N, \end{equation} for some small nonnegative number $\epsilon$. The ideal case for you happens at $\epsilon=0$. The above formulation reduces to solving: \begin{equation} \max_{x\in \{0,1\}^K, t\in \mathbb R} \ t \qquad \mbox{ subject to } \quad f_1(x)\ge t\ge 0, \quad \mbox{ and } \quad |f_i(x)|\le \epsilon, \quad 2\le \forall i\le N, \end{equation} or \begin{equation} \max_{x\in \{0,1\}^K, t\in \mathbb R} \ t \qquad \mbox{ subject to } \quad f_1(x)\le -t\le 0, \quad \mbox{ and } \quad |f_i(x)|\le \epsilon, \quad 2\le \forall i\le N. \end{equation}
Thus, you need to start with $\epsilon =0$, and if any of the above formulations have an optimum, you are done. Otherwise, increase this parameter and the show must go on until any of the problems obtains a solution. Of course, finding the best $\epsilon$ is practically possible but maybe expensive because if one of the problems above has a solution for $\epsilon_1$, any of them might have a solution for a smaller $\epsilon_2$. One fast solver for the MILP is Gurobi!