1
$\begingroup$

In the set up for the program we have a graph where we are trying to minimize the cost of sending flow over the arcs. I have formulated the following linear program.

\begin{array}{ll} \text{minimize} & \sum_{ij} C_{ij} X_{ij} \\ \text{subject to} & \sum_j X_{ij} =\ell_i, ~ i=1,2,\dots,m \\ & X_{ij} \geq 0, ~ i=1,2,\dots,m,~j=1,2,\dots,n \end{array}

Which is basically using the conservation of flow as the constraint.

What I need to be able to do is add a flat "fee" for sending any amount of flow over an arc. I am developing a mixed integer program to model this. I introduced binary variables $y_{ij}$ which give the descision to go over the arc from $i$ to $j$, but after that I am stuck as to how to formulate the problem, does anyone have any ideas on how to modify the boundary conditions so that $y_{ij} = 1$ iff $X_{ij}>0$?

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

If you're OK with using a Big M type method (although I'm told Big M is considered a bad word in mixed integer programming :)), here's a linear constraint to capture $y_{ij} = 1$ if $X_{ij} > 0$. Use $X_{ij} \leq M_{ij} y_{ij}$. Note that if $X_{ij} > 0$ then $y_{ij}$ is forced to 1. But if $X_{ij} = 0$ then $y_{ij}$ can take values 0 or 1. However, since you will add a cost $\bar{C}_{ij} y_{ij}$ to the objective function, $y_{ij}$ will naturally take the value of 0 in the case where $X_{ij} = 0$ to ensure optimality.

The parameter $M_{ij}$ should be chosen as low as possible. One candidate for the parameter is the sum of the absolute values of the demands. But you might be able to come up with better values depending on your problem data. I think if all your data is integral, then choosing the right value for $M$ is probably not critical.

$\endgroup$
0
$\begingroup$

First I would add the constraint, that the quantity, which is transported is equal to the demand:

\begin{array}{ll} \sum_i X_{ij} =d_j, ~ j=1,2,\dots,n \end{array}

For the condition, that $y_{i,j} =1$ if $X_{ij} >0$, there would be the following constrain helpful:

\begin{array}{ll} y_{ij} \cdot X_{ij} = X_{ij} ~ i=1,2,\dots,m,~j=1,2,\dots,n \end{array}

Now you can use the variable $y_{ij}$ for the objective function. And you can add sum of all fees.

$\endgroup$
3
  • $\begingroup$ That would make the problem bilinear (aka nonlinear nonconvex). $\endgroup$ Commented Jul 23, 2014 at 14:56
  • $\begingroup$ @wonko I just formulated a mixed integer program. I had no other purpose. $\endgroup$ Commented Jul 23, 2014 at 15:41
  • $\begingroup$ I know. Just pointing out that this is a difficult formulation to try and solve, unless you linearize the bilinear product which is possible since one of the variables is binary. $\endgroup$ Commented Jul 23, 2014 at 15:44

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.