Muutke küpsiste eelistusi

E-raamat: Integer Programming

4.20/5 (36 hinnangut Goodreads-ist)
(L'Universite Catholique de Louvain)
  • Formaat: EPUB+DRM
  • Ilmumisaeg: 18-Sep-2020
  • Kirjastus: John Wiley & Sons Inc
  • Keel: eng
  • ISBN-13: 9781119606550
Teised raamatud teemal:
  • Formaat - EPUB+DRM
  • Hind: 124,67 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Integer ProgrammingSuurem pilt
  • Formaat: EPUB+DRM
  • Ilmumisaeg: 18-Sep-2020
  • Kirjastus: John Wiley & Sons Inc
  • Keel: eng
  • ISBN-13: 9781119606550
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

"An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. Contains a new chapter on Benders' algorithm, as there have been many successful applications of Benders' algorithm since the first edition published. Provides improved presentation of Branch-and-Price Algorithms. Contains an introduction to Branch-Cut and Price. Includes new heuristics within mixed integer programming (MIP) codes and user implemented heuristics using a Modelling Language and a MIP solver . Supplementary material consists of solutions to some exercises, available to instructors on a Wiley Instructor Companion Site"--

A PRACTICAL GUIDE TO OPTIMIZATION PROBLEMS WITH DISCRETE OR INTEGER VARIABLES, REVISED AND UPDATED

The revised second edition of Integer Programming explains in clear and simple terms how to construct custom-made algorithms or use existing commercial software to obtain optimal or near-optimal solutions for a variety of real-world problems. The second edition also includes information on the remarkable progress in the development of mixed integer programming solvers in the 22 years since the first edition of the book appeared. The updated text includes information on the most recent developments in the field such as the much improved preprocessing/presolving and the many new ideas for primal heuristics included in the solvers. The result has been a speed-up of several orders of magnitude. The other major change reflected in the text is the widespread use of decomposition algorithms, in particular column generation (branch-(cut)-and-price) and Benders’ decomposition. The revised second edition:

  • Contains new developments on column generation
  • Offers a new chapter on Benders’ algorithm
  • Includes expanded information on preprocessing, heuristics, and branch-and-cut
  • Presents several basic and extended formulations, for example for fixed cost
  • network flows
  • Also touches on and briefly introduces topics such as non-bipartite matching, the complexity of extended formulations or a good linear program for the implementation of lift-and-project 

Written for students of integer/mathematical programming in operations research, mathematics, engineering, or computer science, Integer Programming offers an updated edition of the basic text that reflects the most recent developments in the field.

Preface to the Second Edition xii
Preface to the First Edition xiii
Abbreviations and Notation xvii
About the Companion Website xix
1 Formulations
1(24)
1.1 Introduction
1(2)
1.2 What Is an Integer Program?
3(2)
1.3 Formulating IPs and BIPs
5(3)
1.4 The Combinatorial Explosion
8(1)
1.5 Mixed Integer Formulations
9(3)
1.6 Alternative Formulations
12(3)
1.7 Good and Ideal Formulations
15(3)
1.8 Notes
18(1)
1.9 Exercises
19(6)
2 OptimaLity, Relaxation, and Bounds
25(18)
2.1 Optimality and Relaxation
25(2)
2.2 Linear Programming Relaxations
27(1)
2.3 Combinatorial Relaxations
28(1)
2.4 Lagrangian Relaxation
29(1)
2.5 Duality
30(2)
2.6 Linear Programming and Polyhedra
32(2)
2.7 Primal Bounds: Greedy and Local Search
34(4)
2.8 Notes
38(1)
2.9 Exercises
38(5)
3 Well-Solved Problems
43(20)
3.1 Properties of Easy Problems
43(1)
3.2 IPs with Totally Unimodular Matrices
44(2)
3.3 Minimum Cost Network Flows
46(2)
3.4 Special Minimum Cost Flows
48(2)
3.4.1 Shortest Path
48(1)
3.4.2 Maximum's - t Flow
49(1)
3.5 Optimal Trees
50(4)
3.6 Submodularity and Matroids
54(3)
3.7 Two Harder Network Flow Problems
57(2)
3.8 Notes
59(1)
3.9 Exercises
60(3)
4 Matchings and Assignments
63(16)
4.1 Augmenting Paths and Optimality
63(2)
4.2 Bipartite Maximum Cardinality Matching
65(2)
4.3 The Assignment Problem
67(6)
4.4 Matchings in Nonbipartite Graphs
73(1)
4.5 Notes
74(1)
4.6 Exercises
75(4)
5 Dynamic Programming
79(16)
5.1 Some Motivation: Shortest Paths
79(1)
5.2 Uncapacitated Lot-Sizing
80(3)
5.3 An Optimal Subtree of a Tree
83(1)
5.4 Knapsack Problems
84(5)
5.4.1 0-1 Knapsack Problems
85(1)
5.4.2 Integer Knapsack Problems
86(3)
5.5 The Cutting Stock Problem
89(2)
5.6 Notes
91(1)
5.7 Exercises
92(3)
6 Complexity and Problem Reductions
95(18)
6.1 Complexity
95(1)
6.2 Decision Problems, and Classes NT and P
96(2)
6.3 Polynomial Reduction and the Class NTC
98(5)
6.4 Consequences of V = NT or P # VP
103(1)
6.5 Optimization and Separation
104(1)
6.6 The Complexity of Extended Formulations
105(1)
6.7 Worst-Case Analysis of Heuristics
106(3)
6.8 Notes
109(1)
6.9 Exercises
110(3)
7 Branch and Bound
113(26)
7.1 Divide and Conquer
113(1)
7.2 Implicit Enumeration
114(2)
7.3 Branch and Bound: an Example
116(4)
7.4 LP-Based Branch and Bound
120(3)
7.5 Using a Branch-and-Bound/Cut System
123(6)
7.6 Preprocessing or Presolve
129(5)
7.7 Notes
134(1)
7.8 Exercises
135(4)
8 Cutting Plane Algorithms
139(28)
8.1 Introduction
139(1)
8.2 Some Simple Valid Inequalities
140(3)
8.3 Valid Inequalities
143(4)
8.4 A Priori Addition of Constraints
147(2)
8.5 Automatic Reformulation or Cutting Plane Algorithms
149(1)
8.6 Gomory's Fractional Cutting Plane Algorithm
150(3)
8.7 Mixed Integer Cuts
153(5)
8.7.1 The Basic Mixed Integer Inequality
153(2)
8.7.2 The Mixed Integer Rounding (MIR) Inequality
155(1)
8.7.3 The Gomory Mixed Integer Cut
155(1)
8.7.4 Split Cuts
156(2)
8.8 Disjunctive Inequalities and Lift-and-Project
158(3)
8.9 Notes
161(1)
8.10 Exercises
162(5)
9 Strong Valid Inequalities
167(28)
9.1 Introduction
167(1)
9.2 Strong Inequalities
168(7)
9.3 0-1 Knapsack Inequalities
175(4)
9.3.1 Cover Inequalities
175(1)
9.3.2 Strengthening Cover Inequalities
176(2)
9.3.3 Separation for Cover Inequalities
178(1)
9.4 Mixed 0-1 Inequalities
179(4)
9.4.1 Flow Cover Inequalities
179(2)
9.4.2 Separation for Flow Cover Inequalities
181(2)
9.5 The Optimal Subtour Problem
183(3)
9.5.1 Separation for Generalized Subtour Constraints
183(3)
9.6 Branch-and-Cut
186(3)
9.7 Notes
189(1)
9.8 Exercises
190(5)
10 Lagrangian Duality
195(18)
10.1 Lagrangian Relaxation
195(5)
10.2 The Strength of the Lagrangian Dual
200(2)
10.3 Solving the Lagrangian Dual
202(3)
10.4 Lagrangian Heuristics
205(2)
10.5 Choosing a Lagrangian Dual
207(2)
10.6 Notes
209(1)
10.7 Exercises
210(3)
11 Column (and Row) Generation Algorithms
213(22)
11.1 Introduction
213(2)
11.2 The Dantzig-Wolfe Reformulation of an IP
215(1)
11.3 Solving the LP Master Problem: Column Generation
216(3)
11.4 Solving the Master Problem: Branch-and-Price
219(3)
11.5 Problem Variants
222(3)
11.5.1 Handling Multiple Subproblems
222(1)
11.5.2 Partitioning/Packing Problems with Additional Variables
223(1)
11.5.3 Partitioning/Packing Problems with Identical Subsets
224(1)
11.6 Computational Issues
225(1)
11.7 Branch-Cut-and-Price: An Example
226(1)
11.7.1 A Capacitated Vehicle Routing Problem
226(3)
11.7.2 Solving the Subproblems
229(1)
11.7.3 The Load Formulation
230(1)
11.8 Notes
230(2)
11.9 Exercises
232(3)
12 Benders' Algorithm
235(16)
12.1 Introduction
235(1)
12.2 Benders' Reformulation
236(4)
12.3 Benders' with Multiple Subproblems
240(2)
12.4 Solving the Linear Programming Subproblems
242(2)
12.5 Integer Subproblems: Basic Algorithms
244(3)
12.5.1 Branching in the (x, η,y)-Space
244(2)
12.5.2 Branching in (x, η)-Space and "No-Good" Cuts
246(1)
12.6 Notes
247(1)
12.7 Exercises
248(3)
13 Primal Heuristics
251(18)
13.1 Introduction
251(1)
13.2 Greedy and Local Search Revisited
252(3)
13.3 Improved Local Search Heuristics
255(4)
13.3.1 Tabu Search
255(1)
13.3.2 Simulated Annealing
256(1)
13.3.3 Genetic Algorithms
257(2)
13.4 Heuristics Inside MIP Solvers
259(3)
13.4.1 Construction Heuristics
259(2)
13.4.2 Improvement Heuristics
261(1)
13.5 User-Defined MIP heuristics
262(3)
13.6 Notes
265(1)
13.7 Exercises
266(3)
14 From Theory to Solutions
269(22)
14.1 Introduction
269(1)
14.2 Software for Solving Integer Programs
269(3)
14.3 How Do We Find an Improved Formulation?
272(5)
14.4 Multi-item Single Machine Lot-Sizing
277(5)
14.5 A Multiplexer Assignment Problem
282(3)
14.6 Integer Programming and Machine Learning
285(2)
14.7 Notes
287(1)
14.8 Exercises
287(4)
References 291(20)
Index 311
LAURENCE A. WOLSEY is a mathematician working in the field of integer programming. He is a former president and research director of the Center for Operations Research and Econometrics (CORE) at UCLouvain in Belgium where he is Emeritus Professor of applied mathematics in the Engineering school.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97811196065506e.html
Märksõnad: