10

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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • AFAIK, one of the ways to calculate the earliest and latest starting times (for each task) sound like float or slack in the project schedule problem that is: the amount of time that a task in a project network can be delayed without causing a delay to a) subsequent tasks, b) project completion date. Project scheduling MIP formulations contain such the constraints which could be helpful. – A.Omidi Dec 03 '19 at 08:38
  • @A.Omidi yes that is pretty much what I'm looking for, if you have specific references or know how to write such a formulation for the above problem, feel free :) – Kuifje Dec 03 '19 at 09:13

1 Answers1

4

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

prubin
  • 39,078
  • 3
  • 37
  • 104