0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LarrySnyder610 May 26 at 17:14
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks. originally $X$ is a binary variable. So, I can linearize $F(X)$ easily. But, I want to relax $X$. $\endgroup$ – Nazanin May 26 at 11:05
  • 1
    $\begingroup$ 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. $\endgroup$ – LarrySnyder610 May 26 at 13:38
  • $\begingroup$ 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. $\endgroup$ – Nazanin May 26 at 15:08
  • $\begingroup$ Furthermore, to optimally solve the problem, I use PyscipOpt solver in python. $\endgroup$ – Nazanin May 26 at 15:09
  • $\begingroup$ 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? $\endgroup$ – LarrySnyder610 May 26 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.