پیشرفت‌ها در بهینه‌سازی ترکیبیاتی: فرمول‌بندی برنامه‌ریزی خطی مسئله فروشنده دوره‌گرد و سایر مسائل سخت بهینه‌سازی ترکیبیاتی ۲۰۱۶
Advances In Combinatorial Optimization: Linear Programming Formulations Of The Traveling Salesman And Other Hard Combinatorial Optimization Problems 2016

بهینه‌سازی ترکیبیاتی (CO) شاخه‌ای از ریاضیات کاربردی، علم تصمیم‌گیری و علوم کامپیوتر است که به یافتن بهترین راه حل از میان جستجویی غیراحصائی می‌پردازد. بهینه‌سازی ترکیبیاتی با رشته‌هایی مانند نظریه پیچیدگی محاسباتی و نظریه الگوریتم مرتبط است و کاربردهای مهمی در زمینه‌هایی مانند تحقیق در عملیات/علم مدیریت، هوش مصنوعی، یادگیری ماشین و مهندسی نرم‌افزار دارد.

کتاب “پیشرفت‌ها در بهینه‌سازی ترکیبیاتی” چارچوبی کلی برای فرمول‌بندی مسائل دشوار بهینه‌سازی ترکیبیاتی (COPs) به صورت برنامه‌های خطی با اندازه چندجمله‌ای ارائه می‌دهد. این چارچوب که بر اساس «مسئله فروشنده دوره‌گرد» (TSP) توسعه یافته است، امکان فرمول‌بندی بسیاری از مسائل NP-Complete COPs شناخته‌شده را به‌طور مستقیم (بدون نیاز به کاهش آن‌ها به مسائل COPs دیگر) به عنوان برنامه‌های خطی فراهم می‌کند و همین امر را برای سه مسئله دیگر (به عنوان مثال “مسئله رنگ‌آمیزی راس” (VCP)) نشان می‌دهد. این اثر همچنین اثباتی بر برابری طبقات پیچیدگی ‘P’ (زمان چندجمله‌ای) و ‘NP’ (زمان چندجمله‌ای غیرقطعی) ارائه می‌دهد و به نظریه و کاربرد «فرمول‌بندی‌های توسعه‌یافته» (EFs) کمک می‌کند.

به طور کلی، کتاب “پیشرفت‌ها در بهینه‌سازی ترکیبیاتی” دیدگاه‌های جدیدی در مدل‌سازی و حل مسائل ارائه می‌دهد که برای متخصصان، دانشجویان تحصیلات تکمیلی و محققانی که به طور خاص درگیر تصمیم‌گیری‌های مسیریابی، زمان‌بندی و ترتیب‌بندی هستند، یا به طور کلی با نظریه محاسبات سروکار دارند، مفید خواهد بود.

Combinational optimization (CO) is a topic in applied mathematics, decision science and computer science that consists of finding the best solution from a non-exhaustive search. CO is related to disciplines such as computational complexity theory and algorithm theory, and has important applications in fields such as operations research/management science, artificial intelligence, machine learning, and software engineering.Advances in Combinatorial Optimization presents a generalized framework for formulating hard combinatorial optimization problems (COPs) as polynomial sized linear programs. Though developed based on the ‘traveling salesman problem’ (TSP), the framework allows for the formulating of many of the well-known NP-Complete COPs directly (without the need to reduce them to other COPs) as linear programs, and demonstrates the same for three other problems (e.g. the ‘vertex coloring problem’ (VCP)). This work also represents a proof of the equality of the complexity classes ‘P’ (polynomial time) and ‘NP’ (nondeterministic polynomial time), and makes a contribution to the theory and application of ‘extended formulations’ (EFs).On a whole, Advances in Combinatorial Optimization offers new modeling and solution perspectives which will be useful to professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general.