Variable Sensitivity Analysis

Question

I am working with the following MIP : \begin{alignat}2\min&\quad\sum_{j\in J} c_j x_j\\\text{s.t.}&\quad l_j \le f(x_j,t_j) \le u_j \quad &\forall j \in J \\&\quad x_j \in \mathbb{N} \quad &\forall j \in J \\&\quad t_j \in \mathbb{R}^+ \quad &\forall j \in J \end{alignat}

where $f$ is a linear function, $x_j$ are decision variables and $t_j$ represents starting time for task $j$.

I would like to perform some sort of "sensitivity analysis" on variables $t_j$ (maybe sensitivity analysis is the wrong term, feel free to correct me).

Once I solve the MIP, the solver outputs a set of starting times $(t_1,\cdots,t_n)$. I would like to determine the earliest and latest starting times for each task, such that the optimal solution is unchanged (in terms of cost).

Here is my current approach :

1. Solve the MIP. Let $x^*$ be the optimal values of $x$ variables.
2. Solve the MIP again, with the additional constraint $x=x^*$, and minimize $\sum\limits_j t_j$.
3. Solve the MIP again, with the additional constraint $x=x^*$, and maximize $\sum\limits_j t_j$.

Steps 2) and 3) sequentially give me a set of "earliest" and "latest" starting times.

Is there a more straightforward way to achieve this? Any approach is welcome.

Answer 1

Having fixed the discrete decisions, you could start at the beginning and work forward through the task dependency graph, starting each task as early as possible; then work backward from the end, starting each task as late as possible. I don't know that it is superior in any way to what you are doing, but it might be easier to explain to someone (a customer of the analysis, for instance).