Tuesday, May 28, 2019

Bad question?

In [1] a user asks:

I need to build a MILP (Mixed integer linear programming) constraint form this if-else statement: with beta is a constant.
if (a > b) then c = beta else c = 0
How can I build the statement to MILP constraint. Are there any techniques for solving this problem. Thank you.

In my opinion this is a difficult question to answer. To put it bluntly: this is a poor question because we lack lots of information.

  1. We are not sure which identifiers are decision variables and which ones are parameters. It is stated that beta is a constant, so probably we can deduce that all other identifiers refer to variables. In general, it is important to state these things explicitly.
  2. For the variables: we don't know the types (binary, integer, positive, free).
  3. We don't see the rest of the model. In its most general form, this if-construct is a somewhat difficult thing to handle. In practice however, we can almost always exploit knowledge from the model to simplify things considerably. I almost never encounter models where we have to handle this construct in its most general form. 
  4. Expanding on the previous point: one thing to look at is how the objective behaves. It may push variables in a certain direction, which we may exploit. Often this leads to substantial simplifications. In many cases we can drop an implication (e.g. drop the else part).
  5. We don't know what solver or modeling system is being used. Some tools have good support for implications (a.k.a. indicator constraints), which can make things much easier. In other cases, we may need to use big-M constraints.
  6. If  \(a\), \(b\) and \(c\) are (free) continuous variables, the condition \(\gt\) is a bit ambiguous. Do we really mean \(\gt\) or can we use \(\ge\)? In my models, I tend to use \(\ge\) and make \(a=b\) ambiguous: we can pick the best decision for this case (I don't want to skip a more profitable solution because of some epsilon thing). 
  7. Using assumptions in the previous point, we can write \[\begin{align} &\delta = 1 \Rightarrow a \ge b\\ & \delta=0 \Rightarrow a \le b\\ & c = \delta \cdot \beta\\ & \delta \in \{0,1\}\end{align}\] Note that the \(c\) constraint is linear: \(\beta\) is a parameter.
  8. This can be translated into  \[\begin{align} & a \ge b - M(1-\delta)\\ & a \le b + M\delta \\ & c = \delta \cdot \beta\\ & \delta \in \{0,1\}\end{align}\] To determine good values for big-\(M\) constants, again, we need to know more about the model.
  9. If you insist on \(a\gt b\), we can introduce some tolerance \(\varepsilon>0\) and write: \[\begin{align} &\delta = 1 \Rightarrow a \ge b + \varepsilon \\ & \delta=0 \Rightarrow a \le b\\ & c = \delta \cdot \beta\\ & \delta \in \{0,1\}\end{align}\] Here \(\varepsilon\) should be larger than the feasibility tolerance of the solver (scaling may make this not completely obvious). Note that we effectively create a "forbidden region". The variable \(a\) can not assume any value in the interval \((b,b+\varepsilon)\) (again, subject to feasibility tolerances).
  10. Of course when we have integer variables \(a \gt b\) is much more well-defined and we can interpret that as \(a \ge b+1\).

So the best answer is: I would need to look at the whole model to give a good answer.

These type of questions are quite common, and answering them is just very difficult. You can not expect a reply that enumerates all possible answers for all possible cases.

References


  1. Build MILP constraint from if-else statements, https://stackoverflow.com/questions/55899166/build-milp-constraint-from-if-else-statements

1 comment:

  1. Depending on the solver, it might be better to combine the two inequality constraints into a range constraint: epsilon - M <= a - b - M delta <= 0.

    ReplyDelete