how to express big-M formulation as an indicator constraint

130 Views Asked by At

I want to solve the following LP using CPLEX. In the CPLEX documentation it is suggested to use indicator constraint instead of big-M formulation. I searched on google the term "indicator constraints" but except some research papers I could not find much information on this type of constraints.

I would appreciate it if someone could guide me on how to convert the big-M equation into an indicator constraint.

Problem Formulation $$ \min \sum_{(i,j) \in E} \sum_{f \in F} c_{ij}^fx^f_{ij}$$

$$ \sum_{j \in V}x^f_{ij} - \sum_{j \in V}x_{ji}^f = \begin{cases} d_f &, & i = s_f \\ -d_f&, & i = t_f\\ 0 &,& \text{otherwise} \end{cases} $$

$$ \sum_{i,j \in E} x_{ij}^f \le u_{ij}$$ $$ \sum_{i,j \in E} w_{i,j}y_{ij}^f \le W^f$$

$$0 \le x^f_{i,j} \le My^f_{i,j}, \,\, y^f_{i,j} \in \{0, 1\} \quad \forall (i,j) \in E, f \in F$$

This is a modified multicommodity flow problem that for a flow $f$ the sum of all the weights $w_{ij}$ of the edges for which $x^f_{i,j} \gt 0$ should be less than $W^f$.

Solution 1 $$ \min \sum_{(i,j) \in E} \sum_{f \in F} c_{ij}^fx^f_{ij}$$

$$ \sum_{j \in V}x^f_{ij} - \sum_{j \in V}x_{ji}^f = \begin{cases} d_f &, & i = s_f \\ -d_f&, & i = t_f\\ 0 &,& \text{otherwise} \end{cases} $$

$$ \sum_{i,j \in E} x_{ij}^f \le u_{ij}$$ $$ \sum_{i,j \in E} w_{i,j}y_{ij}^f \le W^f$$ $$ y_{i,j}^f = 0 \Rightarrow x_{i,j}^f = 0 \quad \forall (i,j) \in E, f \in F$$

$$ x^f_{i,j} \ge 0, \,\, y^f_{i,j} \in \{0, 1\} \quad \forall (i,j) \in E, f \in F$$

1

There are 1 best solutions below

6
On BEST ANSWER

The indicator constraint is $$y_{i,j}^f = 0 \Rightarrow x_{i,j}^f = 0 \quad \forall (i,j) \in E, f \in F$$