اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA New Algorithm for Multicommodity Flow
89
0
0.0
(
0
)
تأليف
Dhananjay P. Mehendale
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We propose a new algorithm to obtain max flow for the multicommodity flow. This algorithm utilizes the max-flow min-cut theorem and the well known labeling algorithm due to Ford and Fulkerson [1]. We proceed as follows: We select one source/sink pair among the n distinguished source/sink pairs at a time and treat the given multicommodity network as a single commodity network for such chosen source/sink pair. Then applying standard labeling algorithm, separately for each sink/source pair, the feasible flow which is max flow and the corresponding minimum cut corresponding to each source/sink pair is obtained. A record is made of these cuts and the paths flowing through the edges of these cuts. This record is then utilized to develop our algorithm to obtain max flow for multicommodity flow. In this paper we have pinpointed the difficulty behind not getting a max flow min cut type theorem for multicommodity flow and found out a remedy.
قيم البحث
اقرأ أيضاً
In this article we propose a new fractional derivative without singular kernel. We consider the potential application for modeling the steady heat-conduction problem. The analytical solution of the fractional-order heat flow is also obtained by means of the Laplace transform.
When solving hard multicommodity network flow problems using an LP-based approach, the number of commodities is a driving factor in the speed at which the LP can be solved, as it is linear in the number of constraints and variables. The conventional
approach to improve the solve time of the LP relaxation of a Mixed Integer Programming (MIP) model that encodes such an instance is to aggregate all commodities that have the same origin or the same destination. However, the bound of the resulting LP relaxation can significantly worsen, which tempers the efficiency of aggregating techniques. In this paper, we introduce the concept of partial aggregation of commodities that aggregates commodities over a subset of the network instead of the conventional aggregation over the entire underlying network. This offers a high level of control on the trade-off between size of the aggregated MIP model and quality of its LP bound. We apply the concept of partial aggregation to two different MIP models for the multicommodity network design problem. Our computational study on benchmark instances confirms that the trade-off between solve time and LP bound can be controlled by the level of aggregation, and that choosing a good trade-off can allow us to solve the original large-scale problems faster than without aggregation or with full aggregation.
A concise analytical formula is developed for the inverse of an invertible 3 x 3 matrix using a telescoping method, and is generalized to larger square matrices. The formula is confirmed using randomly generated matrices in Matlab
The idea of generating prime numbers through sequence of sets of co-primes was the starting point of this paper that ends up by proving two conjectures, the existence of infinitely many twin primes and the Goldbach conjecture. The main idea of our ap
proach is summarized on the creation and on the analyzing sequence of sets of distinct co-primes with the first $n$ primes, $left{ p_i :, ileq n right}$, and the important properties of the modulus linear combination of the co-prime sets, $H=left(1,p_{n+1},..., Pi_{i=1}^n p_i-1right) $, that gives sets of even numbers ${0,2,4,..., Pi_{i=1}^n p_i -2 }$. Furthermore, by generalizing our approach, the Polignac conjecture the existence of infinitely many cousin primes, $p_{n+1}-p_{n}=4$, and the statement that every even integer can be expressed as a difference of two primes, are derived as well.
The aim of this paper is to provide a new class of series identities in the form of four general results. The results are established with the help of generalizatons of the classical Kummers summation theorem obtained earlier by Rakha and Rathie. Res
ults obtained earlier by Srivastava, Bailey and Rathie et al. follow special cases of our main findings.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
