Discrete Optimization

ویرایش: 1 
نویسندگان: K. Aardal,  G.L. Nemhauser and R. Weismantel (Eds.)  
سری: Handbooks in Operations Research and Management Science 12 
ISBN (شابک) : 9780444515070 
ناشر: North Holland 
سال نشر: 2005 
تعداد صفحات: 606 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 4 مگابایت 

قیمت کتاب (تومان) : 43,000

فصل‌های این کتاب نه موضوع اصلی را پوشش می‌دهد که نشان‌دهنده پیشرفت‌های
نظری و الگوریتمی اخیر در این زمینه است. علاوه بر 9 مقاله ای که به ارائه وضعیت هنر می پردازند، مقاله ای در مورد
تاریخ اولیه این رشته وجود دارد.

این کتاب مرجع مفیدی برای متخصصان این حوزه و همچنین خواهد بود. دانش‌آموزان و دیگرانی که می‌خواهند درباره بهینه‌سازی گسسته بیاموزند.

همه فصل‌های این کتاب راهنما توسط نویسندگانی نوشته شده‌اند که مشارکت اصلی قابل توجهی در موضوعات خود داشته‌اند. در اینجا مقدمه ای کوتاه بر فصول کتاب راهنما ارائه می شود.

«درباره تاریخچه بهینه سازی ترکیبی (تا سال 1960)» به کار Monge در قرن 18 در مورد مسئله انتساب برمی گردد و شش حوزه مسئله را ارائه می کند. : انتساب، حمل و نقل،
حداکثر جریان، کوتاه ترین درخت، کوتاه ترین مسیر و فروشنده دوره گرد.

الگوریتم شاخه و برش برنامه نویسی عدد صحیح، نیروی محاسباتی بهینه سازی گسسته است. ابزارهایی را که در نرم افزارهای تجاری مانند CPLEX
و Xpress MP پیاده سازی شده است فراهم می کند که حل مشکلات عملی در زنجیره تامین، تولید، مخابرات و بسیاری از زمینه های دیگر را ممکن می سازد.
''برنامه نویسی و برش اعداد صحیح محاسباتی planes اجزای کلیدی
این الگوریتم ها را ارائه می دهد.

اگرچه شاخه و برش مبتنی بر آرام سازی برنامه ریزی خطی پرکاربردترین الگوریتم برنامه ریزی اعداد صحیح است، روش های دیگری برای حل نمونه هایی که در آنها شاخه و برش ضعیف عمل می کند و درک بهتر این الگوریتم نیاز است. ساختار چند وجهی انتگرال سه فصل بعدی رویکردهای جایگزین را مورد بحث قرار می دهد.

"ساختار آرامش های گروهی" خانواده ای از چند وجهی را مطالعه می کند که با حذف محدودیت های غیر منفی در مسائل برنامه ریزی عدد صحیح به دست می آید. به صورت چند جمله ای در ابعاد ثابت قابل حل است. «برنامه‌نویسی عدد صحیح، شبکه‌ها و نتایج در ابعاد ثابت» نتایجی را در این زمینه ارائه می‌کند، از جمله الگوریتم‌هایی که از پایه‌های کاهش‌یافته شبکه‌های اعداد صحیح استفاده می‌کنند که قادر به حل کلاس‌های خاصی از برنامه‌های اعداد صحیح هستند که راه‌حل را با شاخه و برش به چالش می‌کشند.

آرامش یا روش‌های دوگانه، مانند برش الگوریتم‌های صفحه، به‌تدریج امکان‌ناپذیری را حذف می‌کنند و در عین حال بهینه‌سازی را برای مشکل آرام حفظ می‌کنند. چنین الگوریتم‌هایی از این مضرات برخوردارند که احتمالاً زمانی که الگوریتم خاتمه می‌یابد امکان‌سنجی به دست می‌آید. روش‌های اولیه برای برنامه‌های عدد صحیح، که از یک راه‌حل عملی به یک راه‌حل عملی بهتر حرکت می‌کنند، در دهه 1960 مورد مطالعه قرار گرفتند. قابل رقابت با روش های دوگانه با این حال، توسعه اخیر در روش‌های اولیه ارائه‌شده در «برنامه‌نویسی عدد صحیح اولیه» نشان می‌دهد که این رویکرد نه تنها از نظر نظری جالب است، بلکه ممکن است پیامدهای عملی نیز داشته باشد. سنت در برنامه نویسی عدد صحیح یک پیشرفت بزرگ در دهه 1990 با توسعه نتایج چند وجهی و ساختاری
و الگوریتم های تشخیص برای ماتریس های متعادل رخ داد. "ماتریس های متعادل" آموزشی در مورد
موضوع است.

بهینه سازی تابع زیر مدولار برخی از مسائل بهینه سازی ترکیبی خطی مانند برش حداقل را تعمیم می دهد و یکی از مسائل اساسی این زمینه است که در چند جمله ای قابل حل است.
زمان. "به حداقل رساندن تابع زیر مدولار" تئوری و الگوریتم‌های این موضوع را ارائه می‌دهد.

در جستجوی آرامش‌های دقیق‌تر مسائل بهینه‌سازی ترکیبی، برنامه‌نویسی نیمه معین تعمیم
برنامه‌نویسی خطی را ارائه می‌دهد که می‌تواند تقریب‌های بهتری ارائه دهد و هنوز به صورت چند جمله ای قابل حل است. این موضوع در "برنامه نویسی نیمه معین و برنامه ریزی عدد صحیح" مورد بحث قرار می گیرد.

بسیاری از مسائل دنیای واقعی داده های نامشخصی دارند که فقط به صورت احتمالی شناخته شده است. برنامه نویسی تصادفی به این موضوع می پردازد، اما تا همین اواخر، به دلایل محاسباتی، به برنامه های خطی تصادفی محدود می شد. برنامه‌نویسی اعداد صحیح تصادفی اکنون یک حوزه تحقیقاتی با مشخصات بالا است و پیشرفت‌های اخیر در
"الگوریتم‌های برنامه‌نویسی عدد صحیح مختلط تصادفی
مدل‌ها" ارائه شده است.

زمان‌بندی محدود منابع نمونه‌ای از یک کلاس است. از مسائل بهینه سازی ترکیبی که به طور طبیعی با قیود خطی فرموله نمی شوند تا روش های مبتنی بر برنامه ریزی خطی به خوبی کار نکنند. "برنامه نویسی محدودیت" یک رویکرد شمارشی جایگزین را ارائه می دهد که مکمل شاخه و برش است. برنامه نویسی محدودیت، که عمدتاً برای مشکلات امکان سنجی طراحی شده است، از آرامش برای به دست آوردن مرزها استفاده نمی کند. درعوض، گره‌های درخت جست‌وجو با انتشار محدودیت‌ها هرس می‌شوند، که مرزهای متغیرها را تا زمانی که مقادیرشان ثابت شود یا دامنه‌هایشان خالی نشان داده شود، سفت می‌کند.

The chapters of this Handbook volume covers nine main topics that are representative of recent
theoretical and algorithmic developments in the field. In addition to the nine papers that present the state of the art, there is an article on
the early history of the field.

The handbook will be a useful reference to experts in the field as well as students and others who want to learn about discrete optimization.

All of the chapters in this handbook are written by authors who have made significant original contributions to their topics. Herewith a brief introduction to the chapters of the handbook.

''On the history of combinatorial optimization (until 1960)'' goes back to work of Monge in the 18th century on the assignment problem and presents six problem areas: assignment, transportation,
maximum flow, shortest tree, shortest path and traveling salesman.

The branch-and-cut algorithm of integer programming is the computational workhorse of discrete optimization. It provides the tools that have been implemented in commercial software such as CPLEX
and Xpress MP that make it possible to solve practical problems in supply chain, manufacturing, telecommunications and many other areas.
''Computational integer programming and cutting planes'' presents the key ingredients
of these algorithms.

Although branch-and-cut based on linear programming relaxation is the most widely used integer programming algorithm, other approaches are
needed to solve instances for which branch-and-cut performs poorly and to understand better the structure of integral polyhedra. The next three chapters discuss alternative approaches.

''The structure of group relaxations'' studies a family of polyhedra obtained by dropping certain
nonnegativity restrictions on integer programming problems.

Although integer programming is NP-hard in general, it is polynomially solvable in fixed dimension. ''Integer programming, lattices, and results in fixed dimension'' presents results in this area including algorithms that use reduced bases of integer lattices that are capable of solving certain classes of integer programs that defy solution by branch-and-cut.

Relaxation or dual methods, such as cutting plane algorithms,progressively remove infeasibility while maintaining optimality to the relaxed problem. Such algorithms have the disadvantage of
possibly obtaining feasibility only when the algorithm terminates.Primal methods for integer programs, which move from a feasible solution to a better feasible solution, were studied in the 1960's
but did not appear to be competitive with dual methods. However,recent development in primal methods presented in ''Primal integer programming'' indicate that this approach is not just interesting theoretically but may have practical implications as well.

The study of matrices that yield integral polyhedra has a long tradition in integer programming. A major breakthrough occurred in the 1990's with the development of polyhedral and structural results
and recognition algorithms for balanced matrices. ''Balanced matrices'' is a tutorial on the
subject.

Submodular function minimization generalizes some linear combinatorial optimization problems such as minimum cut and is one of the fundamental problems of the field that is solvable in polynomial
time. ''Submodular function minimization'' presents the theory and algorithms of this subject.

In the search for tighter relaxations of combinatorial optimization problems, semidefinite programming provides a generalization of
linear programming that can give better approximations and is still polynomially solvable. This subject is discussed in ''Semidefinite programming and integer programming''.

Many real world problems have uncertain data that is known only probabilistically. Stochastic programming treats this topic, but until recently it was limited, for computational reasons, to
stochastic linear programs. Stochastic integer programming is now a high profile research area and recent developments are presented in
''Algorithms for stochastic mixed-integer programming
models''.

Resource constrained scheduling is an example of a class of combinatorial optimization problems that is not naturally formulated with linear constraints so that linear programming based methods do
not work well. ''Constraint programming'' presents an alternative enumerative approach that is complementary to branch-and-cut. Constraint programming,primarily designed for feasibility problems, does not use a relaxation to obtain bounds. Instead nodes of the search tree are
pruned by constraint propagation, which tightens bounds on variables until their values are fixed or their domains are shown to be empty

Content: 
Preface
Pages ix-xi
K. Aardal, G.L. Nemhauser, R. Weismantel

On the History of Combinatorial Optimization (Till 1960) Review Article
Pages 1-68
Alexander Schrijver

Computational Integer Programming and Cutting Planes Review Article
Pages 69-121
Armin Fügenschuh, Alexander Martin

The Structure of Group Relaxations Review Article
Pages 123-170
Rekha R. Thomas

Integer Programming, Lattices, and Results in Fixed Dimension Review Article
Pages 171-243
Karen Aardal, Friedrich Eisenbrand

Primal Integer Programming Review Article
Pages 245-276
Bianca Spille, Robert Weismantel

Balanced Matrices Review Article
Pages 277-319
Michele Conforti, Gérard Cornuéjols

Submodular Function Minimization Review Article
Pages 321-391
S. Thomas McCormick

Semidefinite Programming and Integer Programming Review Article
Pages 393-514
Monique Laurent, Franz Rendl

Algorithms for Stochastic Mixed-Integer Programming Models Review Article
Pages 515-558
Suvrajeet Sen

Constraint Programming Review Article
Pages 559-600
Alexander Bockmayr, John N. Hooker

Index
Pages 601-607