The purpose of this post is mainly for keywords for related researches.
Given $y_i\in \{0, 1\}$ and $x_i\in\{0,1\}^{n}$ for $i=1\ldots m$ and . How to solve the optimization problem $$\begin{align} & \min_w \sum_{i=1}^{m} \left(sgn(x_i^Tw)-y_i\right)^2\\ \text{such that}\quad& \; w\in\{0,1\}^n,\end{align}$$ where $sgn(a)=\begin{cases}1 & \text{if } a>0 \\ 0 & \text{if } a\le 0\end{cases}$.
$w$ can be seen as a selector of $x_i$, and the selected $x_i$ are passed through a logical or gate and get the output.
For example, $y=\begin{bmatrix}1\\1\\0\\0\end{bmatrix}$, $X=\begin{bmatrix} x_1^T \\ x_2^T \\ x_3^T \\ x_4^T \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0\\ 0 & 1 & 1 \end{bmatrix}$, then $\begin{bmatrix}1\\0\\0\end{bmatrix}$ and $\begin{bmatrix}1\\0\\1\end{bmatrix}$ are both solutions.
A simple way to solve is to try out every possible combinations, which is $2^n$ trials. Are there any more scalable ways to solve this kind of problem? Or do you have any idea which research topic is related to it?
You can solve the problem via integer linear programming as follows. Let binary decision variable $z_i$ represent $\text{sgn}(x_i^T w)$. The objective function is then $$\sum_i (z_i-y_i)^2=\sum_i (z_i^2-2y_i z_i+y_i^2)=\sum_i (z_i-2y_i z_i+y_i)=\sum_i (1-2y_i) z_i+\sum_i y_i,$$ and the constraints are $$z_i \le x_i^T w \le n z_i.$$ If $z_i=0$ then $x_i^T w=0$, and if $z_i=1$ then $1 \le x_i^T w \le n$, as desired.