2
$\begingroup$

I have the following inequality that I would want to linearize. Consider that $r_{ij}, x_{ij}, y_{ij}$ are binary variables defined for every pair of nodes $(i,j) \in A$. Also, I have a set of nodes $V$ which its used later.

The following constraint holds: $$r_{ij} \leq \sum_{k \ne i, k \ne j}x_{ik}y_{jk}\qquad \forall (i,j) \in A$$

At first I thought that I should introduce a new family of 3-index binary variables $l^k_{ij}$ and define: $$l^k_{ij} \leq x_{ik}\qquad \forall (i,j) \in A, k\in V: i \ne k, j\ne k\\l^k_{ij}\leq y_{jk}\qquad \forall (i,j) \in A,k \in V:i\ne k, j\ne k\\ l^k_{ij} \geq x_{ik}+y_{jk}-1 \qquad \forall (i,j) \in A,k \in V:i\ne k, j\ne k$$

My ultimate goal is to be able to come up with a linearization that maintains the original number of indexes (although so far i haven't been able to do so and I think it may not be possible).

I've read this survey Transformation and Linearization Techniques in Optimization: A State-of-the-Art Survey and was wondering if there are any others papers like it that I could check as inspiration.

$\endgroup$
2
  • $\begingroup$ Have you read this post?: or.stackexchange.com/questions/37/… $\endgroup$ Commented Oct 13, 2022 at 14:22
  • $\begingroup$ Yes, I changed my question since I realized that the linearization i've done it's (apparently) correct to the one present in the literature $\endgroup$ Commented Oct 13, 2022 at 14:28

1 Answer 1

2
$\begingroup$

With your $\ell_{ij}^k$ variables, a linearization is: \begin{align} \ell_{ij}^k &\le x_{ik} \\ \ell_{ij}^k &\le y_{jk} \\ r_{ij} &\le \sum_k \ell_{ij}^k \end{align}

Without introducing new variables, an alternative formulation arises from rewriting the implication $$r_{ij} \implies \bigvee_k (x_{ik} \land y_{jk}) $$ in conjunctive normal form, but doing this yields exponentially many constraints: $$r_{ij} \le \sum_k *_k,$$ where each $*_k$ is either $x_{ik}$ or $y_{jk}$. Explicitly, for $|V|=3$, there are $2^3$ constraints for each $(i,j)$: \begin{align} r_{ij} &\le x_{i,1} + x_{i,2} + x_{i,3} \\ r_{ij} &\le x_{i,1} + x_{i,2} + y_{j,3} \\ r_{ij} &\le x_{i,1} + y_{j,2} + x_{i,3} \\ r_{ij} &\le x_{i,1} + y_{j,2} + y_{j,3} \\ r_{ij} &\le y_{j,1} + x_{i,2} + x_{i,3} \\ r_{ij} &\le y_{j,1} + x_{i,2} + y_{j,3} \\ r_{ij} &\le y_{j,1} + y_{j,2} + x_{i,3} \\ r_{ij} &\le y_{j,1} + y_{j,2} + y_{j,3} \end{align}

$\endgroup$
7
  • $\begingroup$ Can you clarify the "exponentially many" constraints part? I'm only see two constraints for each $(i,j)$ combination, one summing $x_{ik}$ and one summing $y_{jk}$, but those constraints don't do the job, so I assume I'm not understanding your notation. $\endgroup$
    – prubin
    Commented Oct 13, 2022 at 15:57
  • $\begingroup$ @prubin Yes, those are $2$ out of the $2^{|V|}$ constraints for each $(i,j)$. I updated my answer with more details. $\endgroup$
    – RobPratt
    Commented Oct 13, 2022 at 16:15
  • $\begingroup$ Thanks, that helps. I think you might have too many terms in the constraints, though. The original constraint sums over $k\neq i, k\neq j.$ $\endgroup$
    – prubin
    Commented Oct 13, 2022 at 17:59
  • $\begingroup$ Yes just omit any such variables from those constraints. $\endgroup$
    – RobPratt
    Commented Oct 13, 2022 at 23:04
  • $\begingroup$ Thanks! @RobPratt. If i'm understanding it correctly, there will be very few (or maybe just one) inequalities that will actually provide useful upper bounds for $r_{ij}$. Let $x_{ik_2} = y_{jk_1} = 0$ then exists a constraint that would be $r_{ij}\leq x_{ik_2}+y_{jk_1}$ considering $|V| = 4$ and would make $r_{ij}\leq 0$. If that's how it works then I could have an aux. problem to check the condition and just add that constraint while branching so the exponential number of constraints shouldn't be a huge issue. Now I'd have to think on how to define $*_k$ in Gurobi or cplex $\endgroup$ Commented Oct 14, 2022 at 8:01

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.