10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – A.Omidi Dec 3 at 8:38
  • $\begingroup$ @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 :) $\endgroup$ – Kuifje Dec 3 at 9:13
4
$\begingroup$

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

$\endgroup$

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.