Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 82

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 .. 84 >> Следующая

Contents

233

2.2.9. Combined heuristics for the knapsack problem (59).

2.2.10. Experimental investigation of a system of combined heuristics for approximate solution of the knapsack problem (59).

2.3. Graph-theoretic problems ................................. 63

2.3.1. Graph covering problem (63). 2.3.2. Graph isomorphism problem (66). 2.3.3. Graph coloring problem (68).

2.4. Covering a finite set by a system of its subsets ......... 71

PART II COMBINATORIAL METHODS FOR SOLVING DISCRETE OPTIMIZATION PROBLEMS

Chapter 3. The branch-and bound method ........................... 75

3.1. The scheme of the method for the general discrete optimization

problem ................................................... 75

3.2. The Land and Doig method for the mixed-integer linear programming problem ............................................... 78

3.3. The Land and Doig method for the knapsack problem ........ 80

3.3.1. The main algorithm (80). 3.3.2. The modified algo-

rithm (81). 3.3.3. Remarks on the algorithm complexity (82).

3.3.4. The problem of finding all solutions close to the optimum and its applications (82). 3.3.5. Examples (84).

3.4. Application of the branch-and-bound method to the traveling

salesman problem .......................................... 92

3.4.1. Problem formulation (92). 3.4.2. Reduction of the distance matrix (92). 3.4.3. Branching (94). 3.4.4. The general step of the algorithm (96). 3.4.5. An example (98). 3.4.6. An example of solution of the symmetric problem (100). 3.4.7. A remark on the reduction of the distance matrix (101). 3.4.8. Application of the assignment problem to the computation of the bound and branching (102).

3.5. Application of the branch-and-bound method to the symmetric

traveling salesman problem ...................................... 102

3.5.1. The definition of a 1-tree (102). 3.5.2. Branching (103).

3.5.3. An example (103). 3.5.4. Some recommendations concerning practical problem solution (107).

3.6. Some problems of computational implementation of algorithms

with a tree-like scheme of searching for an optimal solution ... 109

3.6.1. The information structure about the tree of subproblems (HO). 3.6.2. Operations on the tree of subproblems (110).
234

Contents

3.6.3. The information structure about a subproblem (111).

3.7. The branch-and-bound algorithm for finding the set of all Я-close solutions in the general problem and some applications .................................................... 113

3.7.1. An algorithm for finding all Я-close solutions (113).

3.7.2. The approximation-combinatorial method for solving discrete optimization problems (114).

Chapter 4. Applicationofdynamicprogrammingmethodto

solving some additive discrete optimization problems 117

4.1. Problems of resource allocation between projects ....... 117

4.1.1. A simple example (117). 4.1.2. Bellman’s dynamic

programming algorithm (120). 4.1.3. The optimality princi-

ple (122).

4.2. The knapsack problem.................................... 122

4.2.1. The optimality principle (122). 4.2.2. The algorithm (124). 4.2.3. Examples of application of the algo-

rithm (125).

4.3. Minimizing the sum of functions of two variables ....... 129

4.3.1. The problem formulation and the general solution scheme (129). 4.3.2. The algorithm for analysis of variants (131).

4.3.3. The “Kiev Broom” algorithm (132). 4.3.4. The optimality principle (133).

PART III

APPROXIMATE METHODS AND ALGORITHMS

IN DISCRETE OPTIMIZATION

Chapter 5. The search for an approximate solution: problem formulation and some general questions .......................... 137

5.1. Problem formulation ........................................ 137

5.2. A general characterization of approximate algorithms and their

classification .............................................. 139

5.3. Local and global approaches to raising the efficiency of discrete

optimization algorithms ..................................... 140

5.3.1. Local approaches (140). 5.3.2. Global approaches. Transition to epsilon-optimization (142).

5.4. An є-optimal branch-and-bound algorithm for the knapsack

problem ..................................................... 143

5.4.1. Problem formulation and the algorithm (143). 5.4.2. A bound for the number of є-essential variables (146). 5.4.3. Remarks on the polynomial complexity of the algorithm (147).

5.4.4. Examples (148).
Contents

235

Chapter 6. Algorithms with guaranteed performance............ 151

6.1. The one-dimensional knapsack problem .................. 151

6.1.1. The one-dimensional integer knapsack problem (151).

6.1.2. The one-dimensional Boolean knapsack problem (153).

6.2. The metric traveling salesman problems in the plane ...... 154

6.2.1. The first algorithm (155). 6.2.2. The second algo-

rithm (156).

6.3. Graph covering problems........................................... 158
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100