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$

1 Answer 1

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$
5
  • $\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
    Commented Sep 14, 2019 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$
    – RobPratt
    Commented Sep 14, 2019 at 0:07
  • $\begingroup$ Thanks, I get it now $\endgroup$
    – Aaron_Geng
    Commented Sep 14, 2019 at 0:10
  • $\begingroup$ Do you have any good material regarding to linearization? $\endgroup$
    – Aaron_Geng
    Commented Sep 14, 2019 at 0:12
  • $\begingroup$ Model Building in Mathematical Programming by H. Paul Williams. All 29 examples are demonstrated in the SAS/OR documentation. $\endgroup$
    – RobPratt
    Commented Sep 14, 2019 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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