05825cam a2200661Mi 4500 ocn887507297 OCoLC 20171026113514.0 m o d cr cnu---unuuu 140816s2014 xx o 000 0 eng d 9781119005216 (electronic bk.) 1119005213 (electronic bk.) 9781119015185 (electronic bk.) 1119015189 (electronic bk.) CHBIS 010259771 CHDSB 006318344 CHVBK 325941009 CHVBK 326773215 DEBBG BV043397063 DEBSZ 431746133 (OCoLC)887507297 EBLCP eng pn EBLCP MHW DG1 N$T OCLCQ VRC CHVBK OCLCF DEBSZ DEBBG OCLCQ MAIN QA402.5 .C545123 2014 MAT 003000 bisacsh MAT 029000 bisacsh 519.64 23 Concepts of combinatorial optimization / edited by Vangelis Th. Paschos. [electronic resource] 2nd ed. Hoboken : Wiley, 2014. 1 online resource (409 pages). text txt rdacontent computer c rdamedia online resource cr rdacarrier ISTE Chapter 5: Mixed Integer Linear Programming Models forCombinatorial Optimization Problems. Cover; Title Page; Copyright; Contents; Preface; PART I: Complexity of CombinatorialOptimization Problems; Chapter 1: Basic Concepts in Algorithmsand Complexity Theory; 1.1. Algorithmic complexity; 1.2. Problem complexity; 1.3. The classes P, NP and NPO; 1.4. Karp and Turing reductions; 1.5. NP-completeness; 1.6. Two examples of NP-complete problems; 1.6.1. MIN VERTEX COVER; 1.6.2. MAX STABLE; 1.7. A few words on strong and weak NP-completeness; 1.8. A few other well-known complexity classes; 1.9. Bibliography; Chapter 2: Randomized Complexity; 2.1. Deterministic and probabilistic algorithms. 2.1.1. Complexity of a Las Vegas algorithm2.1.2. Probabilistic complexity of a problem; 2.2. Lower bound technique; 2.2.1. Definitions and notations; 2.2.2. Minimax theorem; 2.2.3. The Loomis lemma and the Yao principle; 2.3. Elementary intersection problem; 2.3.1. Upper bound; 2.3.2. Lower bound; 2.3.3. Probabilistic complexity; 2.4. Conclusion; 2.5. Bibliography; PART II: Classical Solution Methods; Chapter 3: Branch-and-Bound Methods; 3.1. Introduction; 3.2. Branch-and-bound method principles; 3.2.1. Principle of separation; 3.2.2. Pruning principles; 3.2.2.1. Bound. 3.2.2.2. Evaluation function3.2.2.3. Use of the bound and of the evaluation function for pruning; 3.2.2.4. Other pruning principles; 3.2.2.5. Pruning order; 3.2.3. Developing the tree; 3.2.3.1. Description of development strategies; 3.2.3.2. Compared properties of the depth first and best first strategies; 3.3. A detailed example: the binary knapsack problem; 3.3.1. Calculating the initial bound; 3.3.2. First principle of separation; 3.3.3. Pruning without evaluation; 3.3.4. Evaluation; 3.3.5. Complete execution of the branch-and-bound method for finding only oneoptimal solution. 3.3.6. First variant: finding all the optimal solutions3.3.7. Second variant: best first search strategy; 3.3.8. Third variant: second principle of separation; 3.4. Conclusion; 3.5. Bibliography; Chapter 4: Dynamic Programming; 4.1. Introduction; 4.2. A first example: crossing the bridge; 4.3. Formalization; 4.3.1. State space, decision set, transition function; 4.3.2. Feasible policies, comparison relationships and objectives; 4.4. Some other examples; 4.4.1. Stock management; 4.4.2. Shortest path bottleneck in a graph; 4.4.3. Knapsack problem; 4.5. Solution; 4.5.1. Forward procedure. 4.5.2. Backward procedure4.5.3. Principles of optimality and monotonicity; 4.6. Solution of the examples; 4.6.1. Stock management; 4.6.2. Shortest path bottleneck; 4.6.3. Knapsack; 4.7. A few extensions; 4.7.1. Partial order and multicriteria optimization; 4.7.1.1. New formulation of the problem; 4.7.1.2. Solution; 4.7.1.3. Examples; 4.7.2. Dynamic programming with variables; 4.7.2.1. Sequential decision problems under uncertainty; 4.7.2.2. Solution; 4.7.2.3. Example; 4.7.3. Generalized dynamic programming; 4.8. Conclusion; 4.9. Bibliography; PART III: Elements from MathematicalProgramming. Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts:- On the complexity of combinatorial optimization problems, presenting basics abo. Print version record. Combinatorial optimization. Programming (Mathematics) MATHEMATICS Applied. bisacsh MATHEMATICS Probability & Statistics General. bisacsh Combinatorial optimization. fast (OCoLC)fst00868980 Programming (Mathematics) fast (OCoLC)fst01078701 Kombinatorische Optimierung. (DE-588)4031826-6 gnd Electronic books. Paschos, Vangelis Th. Print version: Paschos, Vangelis Th. Concepts of Combinatorial Optimization. Hoboken : Wiley, ©2014 9781848216563 ISTE. http://onlinelibrary.wiley.com/book/10.1002/9781119005216 Wiley Online Library ddc BK 207625 207625