What are the flow based formulations?

Question

What are the flow-based formulations? For what optimization problems are they applied, and in which form? Which are the specificities of such a formulation?

Also, the same question for the time staged formulation.

Answer 1

What are flow based formulations ?

Flow based formulations can be used when working with networks. The classical approach is to define a variable for each edge of the network. In a flow based formulation, you basically perform a change of variables, and define a variable for each possible path/flow of the network.

For what optimization problems are they applied ?

For example, if you are solving a multi-commodity flow problem, you would normally have a variable $x_{ij}^p$ for each edge $(i,j)$ of the network, for each commodity $p$. In a flow based formulation, you will define variables for each possible path, for example, for a path from the source to the sink, for a given commodity, you can define variable $\lambda_q, q \in \Omega$ . If you have a capacity constraint on an edge $(i,j)$, in the first model you would write $\sum_{p\in P}x_{ij}^p\le Q$. With a flow based formulation, you would write $\sum_{q\in \Omega, (i,j) \in q}\lambda_q \le Q$.

Which are the specificities of such formulations ?

• They have a tighter linear relaxations than edge based models
• They are designed to be used with decomposition approaches (column generation/Lagrangian relaxation)