بهینه سازی شبکه ها با تابع هزینه مقعر

نویسنده

چکیده

در این مقاله مسئله یافتن یک شبکه ارتباطی1 با حداقل هزینه در نظر گرفته می‌شود که در آن اولاً شبکه چندکالایی2 و بدون جهت3 و ثانیاً هزینه کمانها توابعی خطی قطعه‌بندی شده و مقعر4 از جریانها هستند. چند روش برای حل مسئله بررسی می‌شوند: روش جستجوی تصادفی ترمودینامیکی، یک رو ش ابداعی بر پایه روش ارائه شده توسط مینوکس و یک روش ساده سازی لاگرانژی برای به دست آوردن حد پایینی همچنین نتایج محاسباتی سه روش بالا ارائه می‌شوند.

کلیدواژه‌ها


عنوان مقاله [English]

Network Optimization with Concave Costs

نویسنده [English]

  • S. Ketabi
چکیده [English]

In this paper the problem of minimum cost communication network design is considered where the costs are piecewise linear concave. Several methods are compared: Simulated Annealing method, a heuristic based on the method proposed by Minoux, and a lagrangian method based on lower bounding procedure.

کلیدواژه‌ها [English]

  • Network flow
  • Piecewise linear concave function
  • link-path model
  • random search methods
  • lagrangian relaxation method
  • subgradient method

تحت نظارت وف ایرانی