2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

See When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

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!!).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hi Mark, I made edits to the OP based on your comments. Thanks for letting me know about using Indicator constraints instead. I guess I am primarily interested to know whether my proposed approach is the best way to model this problem or if there are alternatives that one would try? $\endgroup$ – batwing Jul 12 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.