General problem
I am facing a problem from the transportation field. For a given network, the maximum flow $q$ on a link is either the sum of the flows from upstream links, entering at the upstream intersection, or the link capacity $c$. Turning ratios $\alpha$ and the link capacity $c$ are assumed to be known.
I consider an example network as shown in the figure attached (see Example network). Only one turning ratio is shown, but they exist for all possible relations.
I have the following system of equations: $$q_{11} = c$$ $$q_{12} = c$$ $$q_{13} = c$$ $$q_{21} = \min\left(q_{11}\cdot(1-\alpha_{12}) + q_{12}\cdot\alpha_{21}, c\right)$$ $$q_{22} = \min\left(q_{11}\cdot\alpha_{12} + q_{12}\cdot(1-\alpha_{21}), c\right)$$ $$q_{23} = \min\left(q_{13}\cdot(1-\alpha_{31}) + q_{21}\cdot\alpha_{13}, c\right)$$ $$q_{31} = \min\left(q_{13}\cdot\alpha_{31} + q_{21}\cdot(1-\alpha_{13}), c\right)$$ $$q_{32} = \min\left(q_{22}\cdot(1-\alpha_{23}) + q_{23}\cdot\alpha_{32}, c\right)$$ $$q_{33} = \min\left(q_{22}\cdot\alpha_{23} + q_{23}\cdot(1-\alpha_{32}), c\right)$$
I could solve this by inserting $q_{11}$ and $q_{12}$ into the equation for $q_{21}$, etc. However, for large networks this becomes infeasible. Thus, I am looking for other ways to solve this. So far, I have explored the following potential solution techniques:
Max-plus algebra:
I tried to apply techniques from max-plus algebra by converting the min-operator to a max-oprerator. However, since I have two variables in the minimum operation, this becomes non-linear in the max-plus algebra (if I am not taken wrong). For example: $$ - q_{21} = (- q_{11}\alpha_{12} \otimes - q_{12}(1-\alpha_{21})) \oplus -c$$ Since these are my first steps into max-plus algebra, I am very much open to any comments on this. So far, I did not find any commonly applied solutions methods for a system of non-linear max plus algebra equations.
Mixed-integer linear program:
I could rewrite each eq. to a set of constraints, for example: $$q_{21} = \min\left(q_{11}\cdot(1-\alpha_{12}) + q_{12}\cdot\alpha_{21}, c\right)$$ $${q}_{21} \leq q_{11}\cdot(1-\alpha_{12}) + q_{12}\cdot\alpha_{21} $$ $${q}_{21} \leq c $$ $${q}_{21} \geq y c + (1-y) (q_{11}\cdot(1-\alpha_{12}) + q_{12}\cdot\alpha_{21}) $$ $$y \in [0,1] $$
However, I do not know what the objective function then is. Could it be an maximization/minimization of the sum of all flows?
Any thoughts, hints or other help on this is highly appreciated!
Your MIP model is close, but there are two things to fix. First, the domain for $y$ should be $y\in\lbrace 0,1\rbrace$, not $y\in[0,1]$. Second, you want to avoid multiplying $y$ and any expressions containing $q$ variables, as the relaxation is quadratic rather than linear.
To save me some typing, let $f=q_{11}\cdot(1-\alpha_{12}) + q_{12}\cdot\alpha_{21}$. To linearize the product with $y$, you need an a priori upper bound $M$ for $f$. The constraints become: \begin{align*} q_{21} & \le f\\ q_{21} & \le c\\ q_{21} & \ge f-My\\ q_{21} & \ge cy. \end{align*}
As far as the objective function goes, if you are looking for any feasible solution, just minimize (or maximize) 0 subject to your constraints. Minimizing or maximizing the sum of all flows will also work. If you are looking for a particular solution, such as a solution with maximum overall flow, or a solution with maximum flow into (out of) certain nodes, then you will want to customize the objective function to get that solution.