0

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$$

Corey
  • 15

1 Answers1

0

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

LinAlg
  • 19,822
  • Thank you LinAlg. Would you please guide me on how to add this indicator constraint into my formulation. I have modified my formulation in my question, is this correct? – Corey Jan 22 '19 at 05:34
  • @Corey yes, but you should write either $\Rightarrow$ or "if .. then". Use \text in latex for text. – LinAlg Jan 22 '19 at 12:53
  • I removed the "if". LinAlg would you please explain this indicator constraint for me. Since we are saying that if $y^f_{ij}$ is zero then $x^f_{ij}$ should also be zero. I have a bit of doubt on how the solvers know that whether $y^f_{ij}$ is zero or one; as no where in the formulation we are changing the value of $y$ – Corey Jan 22 '19 at 18:54
  • The solver will optimize $y$ just as in your original formulation. The formulations are equivalent. – LinAlg Jan 22 '19 at 19:04
  • Just one more question, there is no need to add $y$ to the objective function? – Corey Jan 22 '19 at 19:10
  • @Corey that's right. – LinAlg Jan 22 '19 at 19:36