کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10350773 | 863890 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
شیمی
شیمی تئوریک و عملی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Combinatorial optimization problems are usually NP-hard. These problems are generally tackled by heuristic or branch-and-bound methods. The aim of this paper is to tackle constrained combinatorial optimization problems by importance Monte Carlo sampling. For this, we show that every constrained combinatorial optimization problem can be represented by a thermodynamical system in a suitable grand canonical ensemble given by the quantities of temperature, volume, and chemical potential. In order to find optimum solutions of the optimization problem, the grand canonical Monte Carlo method can be applied to the corresponding thermodynamical system. This method will amount to importance sampling, i.e. good feasible solutions of the optimization problem will be preferably sampled, provided that the intensive quantities of temperature and chemical potential are appropriately chosen. Our approach extends the standard importance sampling approach in the canonical ensemble to tackle unconstrained combinatorial optimization problems. The knapsack problem is considered as a prototype example.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Physics Communications - Volume 165, Issue 3, 1 February 2005, Pages 243-259
Journal: Computer Physics Communications - Volume 165, Issue 3, 1 February 2005, Pages 243-259
نویسندگان
Karl-Heinz Zimmermann,