Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes

Hello

Please may explain why X1 constraint converted to -1, since -1/3 > -1 in below exam Problem 9?

https://es.cs.uni-kl.de/teaching/vrs/exams/2020.02.19.vrs/2020.02.19.vrs.solutions.pdf

Thanks

in * TF "Intelligent Systems" by (770 points)

1 Answer

0 votes
The part you copied about has already found a rational solution for the inequalities, but we have to find an integer solution. As explained on slide 78, this is done by a branch and bound method, where we pick the first variable (x0) that is not mapped to an integer (v0=11/9) and restart the simplex algorithm with v0' := floor(11/9) = 1 (this is the first line you copied and the constraint for x0 was to be <= +oo). If that would not succeed, we would try again with v0'' := ceil(11/9) = 2.

Using v0' violates the (strengthened) constraint for x0, so that we have to make a pivoting step with x0 and y1.

Then we pick the next non-integer value, which is x1 = -1/3 and restart the simplex algorithm with floor (-1/3) = -1 (if that would not succeed, we would try again with ceil(-1/3) = 0) and so on...
by (166k points)
Imprint | Privacy Policy
...