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

Operations Research Asked by batwing on August 19, 2021

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.

Disjunctive constraints cam be expressed as a MILP using indicator constraints, which are different than Big M constraints, even if in some sense, they are morally equivalent.

Does the reason for your "aversion" to Big M constraints extend to indicator constraints?

MILPs are, of course, non-convex, but their continuous relaxation is convex (and concave!!).

Answered by Mark L. Stone on August 19, 2021