8
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user22363 Sep 25 '19 at 2:17

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.