I am using GLPK to solve a simple linear problem.
Given is a set of distances $d_{ij}$ between nodes of a graph. We want to assign to each edge a velocity $v_{ij}$ such that the average time of travel per edge $\frac{1}{|G|}\sum_{i,j} \frac{d_{ij}}{v_{ij}}$ over all edges of the graph is minimized. The velocity $v_{ij}$ with which we travel on any edge must be between $v_-$ and $v_+$, and we can spend at most $t_\max$ on any particular edge.
The solver does not allow me to minimize on $\sum_{i,j} d_{ij}/v_{ij}$ because dividing by a variable makes it nonlinear. Similarly I cannot minimize on $\sum_{i,j} t_{ij}$ with an additional constraint that $\forall i,j: d_{ij}=v_{ij}t_{ij}$, as multiplying variables is not allowed either. I can minimize on $\sum t_{ij}$ with the constraint that $t_{ij} <t_\max, d_{ij}/v_- < t_{ij} < d_{ij}/v_+$, but this does not explicitly solve for the speeds that we want to assign to every edge.
This last alternative sounds reasonable but the problem has subsequent parts for which I cannot use such a "trick". Is there something I can do to express this as a linear problem?
