# What are the flow based formulations?

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.

• Can you provide a little more context here? Flow-based formulations for what? You added the scheduling tag, so are you asking specifically about scheduling problems? If so, it would help to include that in your title and/or question. Nov 22 '20 at 18:45
• Yes it is about scheduling problems and tsp problems also Nov 22 '20 at 19:25

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)
• SO, i cannot consider the traditional form you cite as a flow based formulation. the condition should be a path or a flow between them? Nov 22 '20 at 16:34
• what is the edge flow models ? and what are the other commun flow formulations? Nov 22 '20 at 16:35
• edge based: one variable per edge, flow based : one variable per flow/path. To my knowledge there are no other common formulations, but don't quote me on that. Nov 22 '20 at 16:51