Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods

مدل‌های بهینه‌سازی محدود ابزارهای اصلی در تجارت، علم، دولت و ارتش با کاربردهایی از جمله برنامه‌ریزی خطوط هوایی، کنترل عملیات پالایش نفت، تصمیم‌های سرمایه‌گذاری و بسیاری موارد دیگر هستند. مدل‌های بهینه‌سازی محدود در سال‌های اخیر با در دسترس قرار گرفتن توان محاسباتی ارزان قیمت، از نظر مقیاس و پیچیدگی بسیار رشد کرده‌اند. مدل‌ها در حال حاضر اغلب دارای محدودیت‌های تعاملی پیچیده‌ای هستند که باعث ایجاد مجموعه‌ای از مسائل مربوط به امکان‌سنجی و غیرممکن می‌شود. به عنوان مثال، گاهی اوقات یافتن هر نقطه عملی برای یک مدل بزرگ، یا حتی تعیین دقیق وجود آن، به عنوان مثال، دشوار است. برای مدل های غیر خطی اگر مدل قابل اجرا باشد، چقدر سریع می توان راه حلی پیدا کرد؟ اگر مدل غیرممکن است، چگونه می توان علت را جدا و تشخیص داد؟ آیا تعمیر برای بازیابی امکان سنجی به صورت خودکار انجام می شود؟ محققان الگوریتم‌ها و روش‌های محاسباتی متعددی را در سال‌های اخیر برای پرداختن به چنین مسائلی، با تعدادی کاربرد شگفت‌آور در زمینه‌هایی مانند هوش مصنوعی و زیست‌شناسی محاسباتی، توسعه داده‌اند. در همان دوره زمانی، رویکردها و تکنیک‌های مرتبط با امکان‌سنجی و غیرممکن بودن مشکلات محدود در جامعه برنامه‌نویسی محدودیت‌ها پدید آمده است. STRONG> یک کتاب توضیحی به موقع است که وضعیت هنر را در الگوریتم‌های کلاسیک و اخیر مربوط به امکان‌سنجی و غیرممکن در بهینه‌سازی با تمرکز بر روش‌های عملی خلاصه می‌کند. تمام فرم های مدل شامل برنامه های خطی، غیرخطی و عدد صحیح مختلط پوشش داده شده است. اتصالات به کار مرتبط در برنامه نویسی محدودیت نشان داده شده است. بخش اول کتاب به الگوریتم‌هایی برای جستجوی سریع امکان‌سنجی، از جمله روش‌های جدید برای موارد دشوار برنامه‌های غیرخطی و عدد صحیح مختلط می‌پردازد. بخش دوم الگوریتم‌هایی را برای تجزیه و تحلیل غیرممکن با جداسازی زیرمجموعه‌های حداقل غیرممکن (یا حداکثر امکان‌پذیر) از محدودیت‌ها یا با یافتن بهترین تعمیر برای عدم امکان‌پذیری ارائه می‌کند. الگوریتم‌های تحلیل امکان‌ناپذیری عمدتاً در دو دهه گذشته پدید آمده‌اند، و کتاب این موارد را به طور عمیق و با جزئیات پوشش می‌دهد. بخش سوم کاربردها را در مناطق متعددی خارج از تجزیه و تحلیل غیرممکن مستقیم، مانند یافتن درخت‌های تصمیم برای طبقه‌بندی داده‌ها، تجزیه و تحلیل تاخوردگی پروتئین، برنامه‌ریزی پرتو درمانی، مونتاژ تست خودکار و غیره توصیف می‌کند.

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

Constrained optimization models are core tools in business, science, government, and the military with applications including airline scheduling, control of petroleum refining operations, investment decisions, and many others. Constrained optimization models have grown immensely in scale and complexity in recent years as inexpensive computing power has become widely available. Models now frequently have many complicated interacting constraints, giving rise to a host of issues related to feasibility and infeasibility. For example, it is sometimes difficult to find any feasible point at all for a large model, or even to accurately determine if one exists, e.g. for nonlinear models. If the model is feasible, how quickly can a solution be found? If the model is infeasible, how can the cause be isolated and diagnosed? Can a repair to restore feasibility be carried out automatically? Researchers have developed numerous algorithms and computational methods in recent years to address such issues, with a number of surprising spin-off applications in fields such as artificial intelligence and computational biology. Over the same time period, related approaches and techniques relating to feasibility and infeasibility of constrained problems have arisen in the constraint programming community.

Feasibility and Infeasibility in Optimization is a timely expository book that summarizes the state of the art in both classical and recent algorithms related to feasibility and infeasibility in optimization, with a focus on practical methods. All model forms are covered, including linear, nonlinear, and mixed-integer programs. Connections to related work in constraint programming are shown. Part I of the book addresses algorithms for seeking feasibility quickly, including new methods for the difficult cases of nonlinear and mixed-integer programs. Part II provides algorithms for analyzing infeasibility by isolating minimal infeasible (or maximum feasible) subsets of constraints, or by finding the best repair for the infeasibility. Infeasibility analysis algorithms have arisen primarily over the last two decades, and the book covers these in depth and detail. Part III describes applications in numerous areas outside of direct infeasibility analysis such as finding decision trees for data classification, analyzing protein folding, radiation treatment planning, automated test assembly, etc.

A main goal of the book is to impart an understanding of the methods so that practitioners can make immediate use of existing algorithms and software, and so that researchers can extend the state of the art and find new applications. The book is of interest to researchers, students, and practitioners across the applied sciences who are working on optimization problems.