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

870 questions

988 answers


439 users

0 votes

I have some doubt in this slide.

It says for every integer we have to do below steps, in lecture video also professor explains it nicely but still I have some doubts as explained below:

-> We take only one rational solution at a time and check with floor(x) and if not found then repeat with ceil(x), If it still not found then reset this x and try the same with another non-integer solution y. Is this correct ?

-> When do we need to stop ? like professor said about Bound but I couldn't get it. In the tool for the below question (Default question of tool), 

-oo <= 5 1 <= 5

-oo <= 2   1 <= 4

-oo <= 1/2 1 <= 2

-oo <= 1/5 1 <= 1

  1 <= 1/2 1 <= +oo

3/2 <= 1   1 <= +oo

In the final step it tries to find the Integer solution so as explained in the lecture it first adds constraint to x0 <= 0, and tries to solve it. In the last step in tool for floor(x) constraint it stops with message "no integer solution found on this branch; backtrack" why it didn't tried to satisfy the constraint of (3/2) <= y5 := 1 <= +oo (Is there any bound set ?)

in * TF "Emb. Sys. and Rob." by (2.9k points)

1 Answer

+1 vote
Best answer
You not correctly repeat what is written on the slide. The slide says that we pick a variable with a non-integer solution v, and add the constraint x<=floor(v) to restart the simplex procedure. It repeats that with other variables, but if not integer solution is found, we remove the constraint x<=floor(v) and add instead x>=ceil(v) to restart the simplex procedure. Again, it continues with strengthening constraints for other non-integer solutions until a solution is found or no solutions exists. If the latter is the case, we tried both x<=floor(v) and x>=ceil(v) and if that does not lead to a integer solution, then there is none.

That far that good, but it may happen that the constraint for the same variable x is strengthened further in the recursive calls, and the example shown in the lecture shows that the procedure may not terminate.

For this reason, one can compute a bound to enforce termination, but how these bounds are computed was not shown in the lecture. The teaching tool simply stops after some thousand steps, and guesses that there is probably no solution.
by (139k points)
selected by
Imprint | Privacy Policy