# Integer programming problem

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?

• The Taylor series question is interesting but should probably be asked as a separate question. It's best to ask multiple questions each with their own (narrow) scope rather than to have multi-part questions. – LarrySnyder610 May 26 at 17:14

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\}$$.)

• Thanks. originally $X$ is a binary variable. So, I can linearize $F(X)$ easily. But, I want to relax $X$. – Nazanin May 26 at 11:05
• Relax $X$ how? More importantly, why? It seems you are worried about the NP-hardness of your ILP. But CPLEX and Gurobi eat NP-hard problems for breakfast; you shouldn't over-think it. Have you tried just giving your ILP to CPLEX or Gurobi? They will do the relaxations for you within the branch-and-bound (or -cut) scheme; you don't need to do that part explicitly. – LarrySnyder610 May 26 at 13:38
• I am going to write a research paper. I want to relax $X$, after that using rounding techniques, propose a heuristic algorithm. Anyway, I really thank you for your answer. – Nazanin May 26 at 15:08
• Furthermore, to optimally solve the problem, I use PyscipOpt solver in python. – Nazanin May 26 at 15:09
• It's not clear to me exactly what you are trying to do, then. Are you saying you want a linear reformulation of $F(X)$ that is exactly equal to the original formulation of $F(X)$ when $X$ is relaxed to be continuous? – LarrySnyder610 May 26 at 17:13