0
$\begingroup$

I am looking for the most elegant solution to the following problem:

I have an if-else query that depends on my optimization variable $x_i$.

If $a \leq b_i + x_i$, the parameter $c$ should take the value of an parameter $z$, otherwise it should be $0$.

I'm sure I need to solve this via constraints, but I don't know how to do it most cleverly.

$\endgroup$
8
  • $\begingroup$ what are $b_i$s? please check the edit on the third line and confirm if it is correct. $\endgroup$ Mar 8 at 15:45
  • $\begingroup$ You might want to have a look into the Big M Method. $\endgroup$
    – SimonT
    Mar 8 at 22:07
  • 1
    $\begingroup$ A constant that can assume two different values is not a constant. $\endgroup$ Mar 9 at 0:48
  • $\begingroup$ @OguzToragay yes its correct in this way...b is just another constant depending on i $\endgroup$ Mar 9 at 7:38
  • $\begingroup$ @SimonT i think you mean especially the part with the binary variable or? $\endgroup$ Mar 9 at 7:51
2
$\begingroup$

"variable c (no optimization variable)" is not something that one can say in linear and (mixed) integer programming. There are decision variables and there are parameters (coefficients). That's it. There are no local variables as in computer programming. It is best to look at things as solving large sparse systems of linear equations.

Now, Gurobi has one very useful feature: indicator constraints. They take the form of implications with a binary variable on the left and a linear constraint on the right. We can use this to formulate: "If $a\le b_i+x_i$, the variable c should take the value of a parameter z, otherwise it should be 0." Well, more or less. As stated it looks wrong. What if for one $i$ the constraint holds and for another it does not? So I will assume the problem is more like:

$$ \begin{aligned} & a\le b_i+x_i \Rightarrow c_i = z \\ & a\gt b_i+x_i \Rightarrow c_i = 0 \end{aligned} $$

As we cannot have strict inequalities, here is my suggestion to implement this:

$$\begin{aligned} & \delta_i = 1 \Rightarrow a\le b_i+x_i \\ & \delta_i = 0 \Rightarrow a\ge b_i+x_i+0.0001 \\ & c_i = z \cdot \delta_i\\ & \delta_i \in \{0,1\} \end{aligned}$$

Again, the implications can be implemented in Gurobi in a straightforward manner using indicator constraints. $\delta_i$ is an additional binary variable.

In practice, I would drop the 0.0001 and keep the model a bit ambiguous in case of equality (the model can then pick the most profitable branch). If all quantities involved are integers, we can replace 0.0001 by 1.

Instead of indicator constraints, it is also possible to use big-M constraints. They require a bit more care, as we need to worry about good bounds.

$\endgroup$
5
  • $\begingroup$ thank you for the detailed answer! I just don't quite understand how to apply the indicator constraint. Do I create the two constrainst for case 1 and 2 and then write two indicator constraints? In addition, a double value is needed if I see that correctly...how do I do that here if the values for a can change? $\endgroup$ Mar 10 at 7:35
  • $\begingroup$ to be honest I don't know exactly how to implement this in Gurbi (Java). $\endgroup$ Mar 10 at 8:19
  • 1
    $\begingroup$ Do I create the two constrainst for case 1 and 2 and then write two indicator constraints? Definitely not. See the documentation and I would suggest write some small tests in Java/Gurobi to get more familiar with this. $\endgroup$ Mar 10 at 17:19
  • $\begingroup$ a double value is needed if I see that correctly The documentation mentions this represents the rhs of the constraint. $\endgroup$ Mar 10 at 17:20
  • 1
    $\begingroup$ how do I do that here if the values for a can change? Depends. If a is a decision variable then just let Gurobi determine its value. If a is a parameter, just use a Java variable to hold its value. $\endgroup$ Mar 10 at 17:22

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.