Tag Info

If you are looking for a way to ensure (in a MILP model) that a graph with $p$ nodes is connected, a common approach is to treat each edge as a pair of directed edges (adding flow variables $x_{ij}$ and $x_{ji}$ for each edge $(i,j)$, choose one node arbitrarily to have supply $p-1$ of a phantom commodity, and assign a demand of $1$ to every other node. You ...
Try adding valid constraints $$y_{i,j} \le \sum_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k} \quad\text{for (i,j) such that \hat{y}_i = 0 and j \in \tilde{V}\setminus\{i\}}$$ that enforce the logical implications (y_{i,j} \land \lnot\hat{y}_i \land [j \in \tilde{V} \setminus\{i\}]) \implies \bigvee_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,...