A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems

این کتاب به تئوری و کاربردهای تکنیک خطی‌سازی/تحدب مجدد (RL T) برای حل مسائل بهینه‌سازی غیر محدب می‌پردازد. یک درمان یکپارچه از مشکلات برنامه ریزی غیر محدب گسسته و پیوسته با استفاده از این رویکرد ارائه شده است. در اصل، پل بین این دو نوع غیر محدب از طریق نمایش چند جمله‌ای از محدودیت‌های گسسته ساخته می‌شود. به عنوان مثال، باینری بودن روی یک متغیر x 0-1. را می توان به طور معادل J به عنوان محدودیت چند جمله ای x بیان کرد. (1-x . ) = 0. انگیزه این کتاب J J نقش نمایش های برنامه ریزی خطی/محدب فشرده یا آرامش در حل چنین مسائل برنامه ریزی غیر محدب گسسته و پیوسته است. هدف اصلی این است که با مدلی شروع کنیم که نمایش و ساختار مفیدی را ارائه دهد و سپس این نمایش را از طریق فرمول‌بندی مجدد خودکار و تکنیک‌های تولید محدودیت تقویت کنیم. همانطور که در بالا ذکر شد، نقطه کانونی این کتاب توسعه و استفاده از RL T برای استفاده به عنوان یک روش فرمول‌بندی مجدد خودکار و همچنین ایجاد نابرابری‌های معتبر قوی است. RLT در دو فاز عمل می کند. در فاز فرمول‌بندی، انواع خاصی از محدودیت‌های چند جمله‌ای ضمنی اضافی، که شامل محدودیت‌های ذکر شده در مورد متغیرهای باینری است، به مسئله اضافه می‌شوند. مشکل حاصل متعاقباً خطی‌سازی می‌شود، با این تفاوت که محدودیت‌های محدب خاصی گاهی در موارد خاص XV، در فاز خطی‌سازی/تحریک‌سازی حفظ می‌شوند. این کار از طریق تعریف متغیرهای جدید مناسب برای جایگزینی هر عبارت متغیر-محصول متمایز انجام می شود. نمایش ابعادی بالاتر، آرامش برنامه ریزی خطی (یا محدب) را ایجاد می کند.

This book deals with the theory and applications of the Reformulation- Linearization/Convexification Technique (RL T) for solving nonconvex optimization problems. A unified treatment of discrete and continuous nonconvex programming problems is presented using this approach. In essence, the bridge between these two types of nonconvexities is made via a polynomial representation of discrete constraints. For example, the binariness on a 0-1 variable x . can be equivalently J expressed as the polynomial constraint x . (1-x . ) = 0. The motivation for this book is J J the role of tight linear/convex programming representations or relaxations in solving such discrete and continuous nonconvex programming problems. The principal thrust is to commence with a model that affords a useful representation and structure, and then to further strengthen this representation through automatic reformulation and constraint generation techniques. As mentioned above, the focal point of this book is the development and application of RL T for use as an automatic reformulation procedure, and also, to generate strong valid inequalities. The RLT operates in two phases. In the Reformulation Phase, certain types of additional implied polynomial constraints, that include the aforementioned constraints in the case of binary variables, are appended to the problem. The resulting problem is subsequently linearized, except that certain convex constraints are sometimes retained in XV particular special cases, in the Linearization/Convexijication Phase. This is done via the definition of suitable new variables to replace each distinct variable-product term. The higher dimensional representation yields a linear (or convex) programming relaxation.