# Is a convex or MILP (without big-M) formulation possible for this problem

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.