Solving a system of piecewise linear equations with multiple variables in minimum function 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!
 A: 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.
