بهينه سازي شبكه ها با تابع هزينه مقعر

Network Optimization with Concave Costs

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

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.