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

Question

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?

Answer 1

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}