8

Actually the question below is not specific to Gurobi, but that's the tool I am using.

Consider a scheduling problem where a 2D array of binary variables $Z(i,v)$ is defined, where $i$ is index of time slot, and $v$ is index of operation, each $Z(i,v)$ is a 0-1 binary variable, $Z(i,v)=1$ means operation $v$ is allocated to time slot $i$.

Now consider adding the following constraint/penalty based on $Z(i,v)$:

  1. A certain operation $v_0$ can be scheduled multiple times, i.e., there are multiple $i$ values where $Z(i,v_0) = 1$. We want to add constraint to the "last $i$" where $Z(i,v_0)=1$, i.e., the last $v_0$ operation. For example, in the last $v_0$ operation the product volume $\operatorname{vol}(i, v_0)\ge100$. The problem is we must tell what is the last $i$ that satisfies $Z(i,v_0) = 1$, and only after that add $\operatorname{vol}(i,v_0)\ge100$, how to do that?
  2. This is an extension of the above problem. Here we consider multiple operations $v_0, v_1, \cdots, v_n$. In certain applications the "order" of those $n+1$ operations matter, meaning that certain order could incur extra cost, and that the objective should contain a penalty term that is a function of the order. To add penalty, we should know the order first, which in turns means that we should extract all those $i$ values where $Z(i, v_0)=1$, $Z(i,v_1)=1$, etc.

Comment: if $Z(i,v)$ is given, then I can just use a for loop to locate all those $i$ values where $Z(i,v)=1$, the problem is $Z(i,v)$ is part of the solution, and is unknown during the solution process. That's what gets me confused. But I expect that Gurobi has some built-in syntax/function to handle those scenarios because technically it should be possible.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
user22363
  • 281
  • 1
  • 3

1 Answers1

3

We can't modify the optimisation problem while it's being solved. What you could try instead is to solve once (maybe with a lax convergence criterion), add/update the constraints based on that solution, and then re-solve by warm-starting the problem using the solution from the previous step.

Nikos Kazazakis
  • 12,121
  • 17
  • 59
  • Thanks. With indicator constraint it's possible to "do something when Z(i,v)=1", to me it's kinda a way to modify the problem during the solution process. For example, I can achieve "when Z(i,v0)=1, then vol(i,v0)>=100". This is actually rather close to my first question, only that I want to only constraint the last v0 (instead of all of them). I am not sure if my variation is trivial, or it's so hard that indicator constraint doesn't help at all. – user22363 Sep 25 '19 at 02:17