A problem from Stephen Boyd's Convex Optimization class. It's a bit long, beware. The original of the problem is here, 18.22.
Problem:
We consider a transit system with $K$ trains, denoted $k = 1,..,K$. Each train $k$ travels over a route, which is a sequence of $S_k$ stops. For simplicity, we will assume that each train has the same number of stops, $S$. The train schedule or time-table is given by the arrival and departure times for each train, at each of the stops on its route. We let $A_{ks} \in \mathbb{R}$ be the arrival time of train $k$ at stop $s$ for $s = 1,..,S$ and $D_{ks} \in \mathbb{R}$ be the departure time of train $k$ at stop $s$, for $s=1,..,S$. These times are given in minutes from some starting or reference time. The first station arrival times $A_{k1}$ and the last station arrival times $A_{kS}$ are given, for $k = 1,..,K$. Our goal is to choose the remaining arrival and departure times.
We let $d_{ks} \in \mathbb{R}$ be the distance between stops $s+1$ and stop $s$ for train $k$, for $k=1,..,K$ and $s=1,..,S-1$. There are minimum and maximum speed limits on each travel segment between stops, $v^{min}$ and $v^{max}$ respectively. In this simple model, you can assume the trains travel at constant speed between stops.
At each stop, each train must stop for at least $\tau^{min}$ minutes, i.e. $D_{ks} - A_{ks} \ge \tau^{min}$ for $k=1,..,k$, $s=1,..,S-1$.
Trains are meant to overlap at various stops called connections. We have $C$ connections, indexed by $c=1,..,C$. Each connection consists of a pair of trains and stops; $(k,s,k',s')$ means that the $s$ stop of train $k$ should connect with $s'$ stop of train $k'$.
Note: Presumably this means the train stop at the same station, but we're not keeping track of the stations where the trains stops here.
The connection time associated with connection $c$ is
$$ T_c = \min ( D_{ks}, D_{k's'} ) - \max ( A_{ks}, A_{k's'} ), $$
which is the time interval during which both trains are at the station. There is a required minimum connection time, i.e. $T_c \ge T^{min}$.
The objective is to maximize the sum of the logs of the connection times (or equivalently, their geometric mean), subject to the constrains described above.
Question:
How can we pose this as a convex optimization problem? Any input is welcome. If new variables are introduced, or variables changed, how do we recover the optimal arrival and departure times from the solution of the problem? Problem gives hint: geometric mean may be a more numerically stable objective when optimizing with CVX.
Also, for the schedule data given below
a coded solution using CVX, cvxpy, or other methods would be great.
There is a helper function scheduleDraw that print schedules.
Thanks,