کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478128 1446025 2014 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
When is rounding allowed in integer nonlinear optimization?
ترجمه فارسی عنوان
وقتی که بهینه سازی غیر خطی عدد صحیح اجازه داده می شود؟
کلمات کلیدی
رویکرد سطح، بهینه سازی عددی غیر خطی، آرامش مستمر،
ترجمه چکیده
در این مقاله ما به بررسی مسائل بهینه سازی عددی غیرخطی می پردازیم. برنامه ریزی عدد صحیح غیر خطی عمدتا برای کلاس های خاص، مانند توابع هدف محدب و مقعر و محدودیت های چند درجه ای مورد مطالعه قرار گرفته است. در این مقاله ما رویکرد دیگری را دنبال می کنیم که بر مبنای محدب یا تقریب نیست. مطالعه خواص هندسی مجموعه های سطح و منطقه قابل اجرا، مواردی را شناسایی می کنیم که در آن می توان یک کمینه کننده عدد صحیح یک برنامه غیرخطی را با گرد کردن (بالا یا پایین) مختصات یک راه حل برای آرام سازی مداوم آن یافت. ما این اموال را داریم. اگر آن راضی باشد، ما را قادر می سازد (برای ابعاد ثابت) یک مشکل برنامه نویسی عدد صحیح را در همان زمان پیچیدگی به عنوان آرامش پیوسته آن حل کند. ما همچنین ویژگی گرد شدن قوی را بررسی می کنیم که اجازه می دهد دور یک راه حل را به آرامش مداوم به راه حل عدد صحیح بعدی و به نوبه خود باعث می شود که نسخه عدد صحیح را می توان در همان زمان پیچیدگی به عنوان آرامش پیوسته خود را برای ابعاد دلخواه حل می شود.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
وقتی که بهینه سازی غیر خطی عدد صحیح اجازه داده می شود؟
چکیده انگلیسی
In this paper we consider nonlinear integer optimization problems. Nonlinear integer programming has mainly been studied for special classes, such as convex and concave objective functions and polyhedral constraints. In this paper we follow an other approach which is not based on convexity or concavity. Studying geometric properties of the level sets and the feasible region, we identify cases in which an integer minimizer of a nonlinear program can be found by rounding (up or down) the coordinates of a solution to its continuous relaxation. We call this property rounding property. If it is satisfied, it enables us (for fixed dimension) to solve an integer programming problem in the same time complexity as its continuous relaxation. We also investigate the strong rounding property which allows rounding a solution to the continuous relaxation to the next integer solution and in turn yields that the integer version can be solved in the same time complexity as its continuous relaxation for arbitrary dimensions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 237, Issue 2, 1 September 2014, Pages 404-410
نویسندگان
, ,