Assume we are given a directed acyclic graph (DAG) $G(V, A)$, where $|V| = n, |A| = m$, and the graph contains a source node $\mathbf{s}$ (i.e. every node in $V \backslash \mathbf{s}$ is connected by a directed path from $\mathbf{s}$). Let us denote the arc lengths by the $m$ dimensional vector $\xi$ which can be chosen from a compact box $\Xi \subset \mathbb{R}^{m}_{++}$ (positive orthant).
The problem of interest to me is from a scheduling problem, so we introduce a start time for each node. For some realization of arc variables $\xi \in \Xi$, the start time of node $v$ is set to the cost of the longest path from the source node $\mathbf{s}$ to node $v$ denoted by $L(\mathbf{s}, v, \xi)$ (i.e. earliest start time policy). Note that $L(\mathbf{s}, v, \xi)$ can be easily computed by any longest path algorithm since $G$ is a DAG. For $v \in V$ and $\xi \in \Xi$, the start time of node $v$ is denoted by $S_v (\xi)$ and obviously $S_v (\xi) = L(\mathbf{s}, v, \xi)$. For brevity I will drop the dependence of $\xi$ in the start time variables. The optimization problem I am interested in is of the following form:
\begin{align} \underset{\substack{\xi \in \Xi \\ S_v \in \mathbb{R}_{n}^{+}, \, v \in V}}{\max{}} &S_{\mathbf{w}} - S_{\mathbf{u}} - || \xi - \mathbf{\bar{\xi}} ||_1 \\ \mbox{s.t. } & S_{\mathbf{s}} = 0 \text{ i.e. the start time of source node is always 0} \tag{1}\label{Eq:1}\\ &S_v = L(\mathbf{s}, v, \xi) , \forall v \in V \backslash \mathbf{s} \tag{2} \label{Eq:2} \\ \end{align} where $\mathbf{w, u}$ are some prespecified nodes both in $V \backslash \mathbf{s}$, and $\bar{\xi} \in \Xi$ is some constant vector. Note that in the optimization problem above, both arc lengths and start times of the nodes are variables in the problem.
I am wondering whether the problem shown above can be posed as a convex optimization problem or as a Mixed integer linear program without the use of big-M constants. Any help is appreciated.
My attempt:
Unfortunately, my formulation makes use of disjunctive constraints, which I believe will be hard to pose as a MILP without big-M constants. For $v \in V$, let $Pred(v) \subset V$ denote the set of nodes that are connected to $v$ by an arc in $A$ i.e., if $x \in Pred(v)$ then the arc $(x, v) \in A$. We can write the optimization problem shown previously as:
\begin{align} \underset{\substack{\xi \in \Xi \\ S_v \in \mathbb{R}_{n}^{+}, \, v \in V}}{\max{}} &S_{\mathbf{w}} - S_{\mathbf{u}} - || \xi - \mathbf{\bar{\xi}} ||_1 \\ \mbox{s.t. } & S_{\mathbf{s}} = 0 \\ &S_v \geq S_{x} + L(x, v, \xi) , \forall v \in V \backslash \mathbf{s}, \forall x \in Pred(v) \tag{3} \label{Eq:3} \\ & \underset{x \in Pred(v)}{\lor} \left(S_v \leq S_{x} + L(x, v, \xi)\right) \forall v \in V \backslash \mathbf{s} \tag{4} \label{Eq:4} \end{align} In my attempt above, essentially I have just replaced constraint (\ref{Eq:2}) by two constraints (\ref{Eq:3}) and (\ref{Eq:4}). In Eqns (\ref{Eq:3}) and (\ref{Eq:4}), $ L(x, v, \xi)$ simply denotes the length of the arc $(x, v)$ in realization $\xi$. Eqn (\ref{Eq:3}) enforces that the start time of $v$ is at least the start time of $x$ plus the length of the arc $(x,v)$. In Eqn (\ref{Eq:4}), $\lor$ denotes the logical OR constraint. In Eqn (\ref{Eq:4}) we enforce the fact that the start time of each node is equal to the start time of one of its predecessors plus the length of the arc connecting the 2 nodes.
EDIT - As Mark points out in his post, disjunctive constraints can be alternatively represented using Indicator functions, which may be beneficial over big-M. I guess I am primarily interested in a strong formulation for my problem, and so would like to know how one may alternatively model the problem or perhaps use a different approach (for e.g. a decomposition method) to approach this problem.
