0
$\begingroup$

I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following constraints are met:

  1. $T_{ts}\geqslant-7$
  2. $T_{it}\leqslant14$
  3. $T_{ts}-T_{it}\geqslant5$
  4. $\alpha_{ts,gshp}=0$

Regards

SR89

$\endgroup$
4
  • $\begingroup$ If you know precision of your variables and accept it being up to given number of digits, then just calculate all the comparisons: blog.adamfurmanek.pl/2015/11/21/ilp-part-14 $\endgroup$ Commented Sep 10, 2018 at 18:29
  • $\begingroup$ I'm confused. If $\alpha_{ts,it} = 1$ just substitute the variable with $1$ in each equation. $\endgroup$
    – orlp
    Commented Sep 10, 2018 at 18:49
  • $\begingroup$ What does "as long as" mean? Do you mean that if those 4 constraints are met then you require $\alpha_{ts,it}=1$? Or do you mean that if $\alpha_{ts,it}=1$ then you require that those 4 constraints hold? Also, do you know upper and lower bounds for $T_{it}$ and $T_{ts}$? I suggest referring to cs.stackexchange.com/q/12102/755, cs.stackexchange.com/q/51025/755, cs.stackexchange.com/q/67163/755. $\endgroup$
    – D.W.
    Commented Sep 10, 2018 at 19:14
  • 1
    $\begingroup$ Thanks for the reformulation. Rather than writing "stuff. correction: never mind, I actually meant other stuff", please just edit the question to remove the incorrect material, and replace it with the correct version. We have revision history, so no need to keep around the old version or to mark what has changed. See cs.meta.stackexchange.com/q/657/755. Also please make sure to incorporate all relevant information into the question, so people don't have to read the comments to understand what you are asking (then flag the comments as no longer needed once you've done that). Thanks! $\endgroup$
    – D.W.
    Commented Sep 11, 2018 at 20:07

2 Answers 2

0
$\begingroup$

I might have found a solution to my problem by using four auxiliary binary variables $\alpha_1$, $\alpha_2$, $\alpha_3$ and $\alpha_4$ $\epsilon\ \{0,1\} $. The constraints 1.-4. are rewritten using the big-M method.


Constraint 1

  • $T_{ts}\geqslant -7-M\cdot (1-\alpha_1)$
  • $T_{ts}\leqslant -7+M\cdot \alpha_1$

Constraint 2

  • $T_{it}\leqslant 15+M\cdot (1-\alpha_2)$
  • $T_{it}\geqslant 15-M\cdot \alpha_2$

Constraint 3

  • $T_{ts}-T_{it}+M\cdot (1-\alpha_3)\geqslant 5$
  • $T_{ts}-T_{it}-M\cdot \alpha_3\leqslant 5$

Constraint 4

  • $\alpha_{ts,it}=1-\alpha_{ts,gshp}$

Constraint 5

  • $\alpha_{ts,it}\geqslant \alpha_1+\alpha_2+\alpha_3+\alpha_4-3$
  • $\alpha_{ts,it}\leqslant \alpha_1$
  • $\alpha_{ts,it}\leqslant \alpha_2$
  • $\alpha_{ts,it}\leqslant \alpha_3$
  • $\alpha_{ts,it}\leqslant \alpha_4$

This might be a solution. Unfortunately computational time is exploding. Does someone know a less time-consuming workaround?

Best SR89

$\endgroup$
0
$\begingroup$

That’s the problem with ILP; it is NP-complete so times can explode.

A simple strategy is to solve and optimise a problem as an ordinary linear programming problem, get the solution, and check where your other rules are violated. For example if you find an optimal solution where x = 12.381 but x must be an integer, then you solve two problems, one with x <= 12 added, and one with x >= 13 added. (If you do this by hand you can also handle cases like “x must be the square of a prime”: Either x <= 9 or x >= 25).

In your case, you just solve ignoring your condition. If your condition is fulfilled, great. Otherwise you solve the problem once with a (ts, it) = 1 added, and once with a (ts, it) = 0 and (one of the four conditions is not met) added.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.