How to linearize an if-then statement?

89 Views Asked by At

I want to write constraints for finding a path for some rider, driver on a directed network problem.

Let $x_{i,j}^d$ indicate whether driver travels from $i$ to $j$ and $z_{i,j}^{r,d}$ indicates whether riders travel from $i$ to $j$ with driver, and finally, let $y_{i}^{r,d}$ indicate whether driver picks up at $i$ the rider.

I want to ensure that if a driver wants to pick up someone at $i$, then they should travel on an edge connected to $i$. Is this way of writing correct?

$$ y_{i}^{r,d} = 1 \implies \sum_{j: (i,j) \in links} x_{i,j}^d =1$$

Then how to linearize this? Is this even correct?

$$ y_{i}^{r,d} \le \sum_{j: (i,j) \in links} x_{i,j}^d $$

And, more generally, is there any good resource that explains these linearization techniques very easily and comprehensively? I've searched and everywhere is not complete and easy to understand.

1

There are 1 best solutions below

2
On BEST ANSWER

Your linear constraint enforces $$y_{i}^{r,d} = 1 \implies \sum_{j: (i,j) \in links} x_{i,j}^d \ge 1$$ Do you already have other constraints $$\sum_{j: (i,j) \in links} x_{i,j}^d \le 1?$$ If so, then your proposed linearization is sufficient.

For many linearization examples and links to references, see the [linearization] tag on the Operations Research StackExchange.