TransWikia.com

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.

One Answer

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

Answered by Mark L. Stone on August 19, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP