Integer programming problem

Question

I have an integer optimization problem with a non-linear function ($F(X)$) in the objective and one of the constraints. $F(X)=x_n^{i,j}\Big[\sum\limits_{\forall s\neq i}\sum\limits_{\forall m\in\mathcal{S}_s}x^{s,m}_{n}+x_n^{i,j}\Big]$, where $X$ is binary.

If I solve this integer problem, easily I can linearize $F(X$be) due to the binary nature of $X$. On the other hand, since the integer problems are NP-hard, I should relax this problem and solve a continuous problem. But when I relax $X$, $F(X)$ could not be linearized by the same way in integer problem. Therefore, the relaxed optimization problem becomes a non-linear problem and this increases the computation complexity. I was wondering if there is any way to linearize or approximate $F(X)$? As another question, if I use Taylor first order approximation, should be the problem feasible at the initial point?

Answer 1

Here is one way to linearize $F(X)$, but at the cost of many more binary variables.

Let $x_n^{i,j,s,m} = 1$ if $x_n^{i,j}=x_n^{s,m}=1$ and $=0$ otherwise. Enforce this definition with the following constraints:

$$\begin{align} x_n^{i,j,s,m} & \ge x_n^{i,j} + x_n^{s,m} - 1\\ x_n^{i,j,s,m} & \le x_n^{i,j} \\ x_n^{i,j,s,m} & \le x_n^{s,m} \\ x_n^{i,j,s,m} & \in \{0,1\} \end{align}$$

Now replace $F(X)$ with $$\sum_{s\ne i} \sum_{m\in \mathcal{S}_s} x_n^{i,j,s,m} + x_n^{i,j}.$$ (The second term comes from the fact that $\left(x_n^{i,j}\right)^2 = x_n^{i,j}$ since $x_n^{i,j} \in \{0,1\}$.)