0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Sorry, I didn't get it... How does big M lead to the linear constraint that you were getting? I mean, I get your point, but I don't know how to come up with the linear constraints $\endgroup$ – Aaron_Geng Sep 14 '19 at 0:01
  • $\begingroup$ 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$. $\endgroup$ – Rob Pratt Sep 14 '19 at 0:07
  • $\begingroup$ Thanks, I get it now $\endgroup$ – Aaron_Geng Sep 14 '19 at 0:10
  • $\begingroup$ Do you have any good material regarding to linearization? $\endgroup$ – Aaron_Geng Sep 14 '19 at 0:12
  • $\begingroup$ Model Building in Mathematical Programming by H. Paul Williams. All 29 examples are demonstrated in the SAS/OR documentation. $\endgroup$ – Rob Pratt Sep 14 '19 at 0:18

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.