3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – LarrySnyder610 Nov 22 at 18:45
  • $\begingroup$ Yes it is about scheduling problems and tsp problems also $\endgroup$ – fathese Nov 22 at 19:25
4
$\begingroup$

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)
| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – fathese Nov 22 at 16:34
  • $\begingroup$ what is the edge flow models ? and what are the other commun flow formulations? $\endgroup$ – fathese Nov 22 at 16:35
  • $\begingroup$ 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. $\endgroup$ – Kuifje Nov 22 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.