# How do I solve this integer programming problem with non convex constraints?

I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.

I have an optimization problem like this

Min sum(yi)
st  sum on j(wij) <= cyi for all i in N
sum on i(xij) = 1 for all j in N
wij = wjxij for all i, j in N
Lij = Ljxij for all i, j in N
Dij = Lij + wij for all i, j in N
(Lij - Dik)(Lik - Dij) <= 0 for all i, j, k in N
Aj <= Lj for all j in N
Lj <= Aj + Qj for all j in N
xij = 0 or 1 for all i, j in N
yi = 0 or 1 for all i in N
Wj, Lj, Qj and c are constant
N = 10000


What can I do to transform this problem into a convex optimization problem? Or to a linear Integer programming problem? Because I only know algorithms to solve problems in those two categories.

In the problem, the only constraint that is not convex is this one

(Lij - Dik)(Lik - Dij) <= 0 for all i, j, k in N


Are there any common ways to transform this constraint into some convex constraints?

I think implicit enumeration could be a solution to this, but other than that, what can i do?

The nonlinear constraint $$(L_{ij} - D_{ik})(L_{ik} - D_{ij}) \le 0$$ is a disjunction: $$\left(L_{ij} - D_{ik} \ge 0 \wedge L_{ik} - D_{ij} \le 0\right) \bigvee \left(L_{ij} - D_{ik} \le 0 \wedge L_{ik} - D_{ij} \ge 0\right).$$ Introduce a binary variable $$z_{ijk}$$ that enforces at least one side of the disjunction. We want: \begin{align} z_{ijk} = 1 &\implies (L_{ij} - D_{ik} \ge 0 \wedge L_{ik} - D_{ij} \le 0)\\ z_{ijk} = 0 &\implies (L_{ij} - D_{ik} \le 0 \wedge L_{ik} - D_{ij} \ge 0). \end{align} The following linear "big-M" constraints do the job: \begin{align} D_{ik} - L_{ij} &\le (L_k + W_k) (1 - z_{ijk})\\ L_{ik} - D_{ij} &\le L_k (1 - z_{ijk})\\ L_{ij} - D_{ik} &\le L_j z_{ijk}\\ D_{ij} - L_{ik} &\le (L_j + W_j) z_{ijk} \end{align}
• The general "big-M" approach to enforce $y=1 \implies f(x) \le 0$ is $f(x) \le M(1-y)$, where $M$ is a (preferably small) upper bound on $f(x)$ when $y=0$. – Rob Pratt Sep 14 '19 at 0:07