Available online
Description
The programme demonstrates the use of the Branch and Bound method in solving integer programming problems.
The programme demonstrates the use of the Branch and Bound method in solving integer programming problems.
| Module code and title: | M351, Numerical computation |
|---|---|
| Item code: | M351; 04 |
| First transmission date: | 08-06-1976 |
| Published: | 1976 |
| Rights Statement: | |
| Restrictions on use: | |
| Duration: | 00:24:00 |
| + Show more... | |
| Producer: | John Richmond |
| Contributors: | Bill Arms; Paul Williams |
| Publisher: | BBC Open University |
| Keyword(s): | Linear programming; Margarine blending problem; Branching; Tree diagram |
| Footage description: | The programme opens with Bill Arms at a studio computer terminal. He shows how to find the continuous solution to a simple linear programming problem in Unit 7. Constraints are added to ensure that x1 is integer. Williams goes over the problem again, using a geometrical diagram to explain it. Arms introduces the idea of a tree diagram. Using an animated diagram, he explains the terms 'branching' and 'the bound'. He then goes through the problem using this method. With the help of a studio chart showing the completed tree diagram, Williams explains the use of stopping rules. Arms explains branching strategy and how it can be implemented on the computer. He displays the simple strategy used earlier in the programme. Returning to the tree diagram, he shows how a store is used with the branching strategy. Williams introduces the margarine blending problem as an example of a practical integer programming problem, and shows it on a studio board. Using an animated diagram, he shows how 0-1 variables can be used to implement a logical restriction on the problem. Arms shows how the branching strategy used earlier in the programme provided a tree, and explains why this strategy is inadequate for the margarine blending problem. Williams shows how to obtain a better branching strategy. Animated diagrams are used. Arms shows why the new tree is better than the old one. He concludes with a few remarks on the importance of a good branching strategy. |
| Master spool number: | 6HT/72020 |
| Production number: | 00525_4223 |
| Videofinder number: | 851 |
| Available to public: | no |
