Hi Guys,
I have a quick question regarding constraints in integer linear programming. I've never seen a constraint look something like this but I need it to complete my model.
(X1 + X2) / 9 > 0 and integer
Essentially meaning x1 + x2 modulo 9 needs to be 0. Would this be acceptable in linear programming because I have yet to see a constraint that divides numbers on the left side.
Hmm. I don't know much about linear programming (I've been waiting for someone else to chime in.) However, it does seem to me that one of the first principles of it is that you are generally dealing with a convex feasible region. The modular arithmetic constraint you have there does not describe a convex region at all. Ergo, I would say you are no longer in the linear programming regime. But that's my highly inexpert opinion.
Another way of writing the constraint, that is entirely equivalent, is that x1 + x2 = 9k (or k9, if you prefer dogs), for k in the positive integers. This is going to be a series of disconnected lines, of slope -1, in the x1-x2 plane. I don't mean the lines are continuous; I really mean that you have a series of dots that are on these lines. So that set is not only not convex, it's not connected in any way, shape, or form.
Are there any constraints on x1 and x2? Because, the way you've written it, there are actually infinitely many points on each line. If, say, x1 and x2 must be positive, then there are finitely many points on each line. However, because there are infinitely many lines, you still have infinitely (countably) many solutions to the constraint. That would take a computer a long time to check.
  |
LinkBack URL
About LinkBacks