This work presents a new code for solving the multicommodity network flow problem with a linear or nonlinear objective function considering additional linear side constraints that link arcs of the same or different co...
详细信息
This work presents a new code for solving the multicommodity network flow problem with a linear or nonlinear objective function considering additional linear side constraints that link arcs of the same or different commodities. For the multicommodity network flow problem through primal partitioning the code implements a specialization of Murtagh and Saunders' strategy of dividing the set of variables into basic, nonbasic and superbasic. Several tests are reported, using random problems obtained from different network generators and real problems arising from the fields of long and short-term hydrothermal scheduling of electricity generation and traffic assignment, with sizes of up to 150 000 variables and 45 000 constraints. The performance of the code developed is compared to that of alternative methodologies for solving the same problems: a general purpose linear and nonlinear constrained optimization code, a specialised linear multicommodity network flow code and a primal-dual interior point coda.
This note presents a simple heuristic to speed up algorithms for the maximum flow problem that works by repeatedly finding blocking flows in layered (acyclic) networks. The heuristic assigns a capacity to each vertex ...
详细信息
This note presents a simple heuristic to speed up algorithms for the maximum flow problem that works by repeatedly finding blocking flows in layered (acyclic) networks. The heuristic assigns a capacity to each vertex of the layered network, which will be an upper bound on the amount of flow that can be transported through that vertex to the sink. This information can be utilized when constructing a blocking flow, since no vertex can ever accommodate more flow than its capacity. The static heuristic computes capacities in a layered network once, while a dynamic variant readjusts capacities during construction of the blocking flow. The effects of both static and dynamic heuristics are evaluated by a series of experiments with the wave algorithm of Tarjan. Although neither give theoretical improvement to the efficiency of the algorithm, the practical effects are in most cases worthwhile, and for certain types of networks quite dramatic.
作者：
Duin, CWVolgenant, AUNIV AMSTERDAM
FAC ECON & ECONOMETROPERAT RES GRPINST ACTUARIAL SCI & ECONOMETRROETERSST 111018 WB AMSTERDAMNETHERLANDS
The hierarchical network design problem is the problem to find a spanning tree of minimum total weight, when the edges of the path between two given nodes are weighted by an other cost function than the tree edges not...
详细信息
The hierarchical network design problem is the problem to find a spanning tree of minimum total weight, when the edges of the path between two given nodes are weighted by an other cost function than the tree edges not on this path. We point out that a dynamic programming oriented heuristic can already be found in literature. Further we report on possible extensions and improvements.
Blockage is a kind of phenomenon frequently occurred in a transport network, in which the human beings are the moving subjects. The minimum flow of a network defined in this paper means the maximum flow quantity throu...
详细信息
Blockage is a kind of phenomenon frequently occurred in a transport network, in which the human beings are the moving subjects. The minimum flow of a network defined in this paper means the maximum flow quantity through the network in the seriously blocked situation. It is an important parameter in designing and operating a transport network, especially in an emergency evacuation network. A branch and bound method is presented to solve the minimum flow problem on the basis of the blocking flow theory and the algorithm and its application are illustrated by examples.
In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with ...
详细信息
In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The;disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.
This paper presents a new algorithm for finding the shortest path from a source to a single sink in a network, in which the location in the plane of each node is known. The algorithm consists of two phases. In the fir...
详细信息
This paper presents a new algorithm for finding the shortest path from a source to a single sink in a network, in which the location in the plane of each node is known. The algorithm consists of two phases. In the first phase a heuristic solution to the shortest path problem is found. In the second phase the upper bound provided by the heuristic solution is utilized in a modification of a standard shortest path algorithm. Estimates based on computational tests show that on average the computation time of the presented algorithm is on the order of 40-60% of the computation time required if the information on node locations is not utilized.
We extend some known results about the Bilevel Linear Problem (BLP), a hierarchical two-stage optimization problem, showing how it can be used to reformulate any Mixed Integer (Linear) Problem;then, we introduce some ...
详细信息
We extend some known results about the Bilevel Linear Problem (BLP), a hierarchical two-stage optimization problem, showing how it can be used to reformulate any Mixed Integer (Linear) Problem;then, we introduce some new concepts, which might be useful to fasten almost all the known algorithms devised for BLP. As this kind of reformulation appears to be somewhat artificial, we define a natural generalization of BLP, the Bilevel Linear/Quadratic Problem (BL/QP), and show that most of the exact and/or approximate algorithms originally devised for the BLP, such as GSA or K-th Best, can be extended to this new class of Bilevel programming Problems. For BL/QP, more 'natural' reformulations of MIPs are available, leading to the use of known (nonexact) algorithms for BLP as (heuristic) approaches to MIPs: we report some contrasting results obtained in the network Design Problem case, showing that, although the direct application of our (Dual) GSA algorithm is not of any practical use, we obtain as a by-product a good theoretical characterization of the optimal solutions set of the NDP, along with a powerful scheme for constructing fast algorithms for the Minimum Cost Flow Problem with piecewise convex linear cast functions.
In this paper, we present a mathematical formulation of a terminal layout problem in the design of a centralized communication network with unreliable links and node outage costs. The node outage cost associated with ...
详细信息
In this paper, we present a mathematical formulation of a terminal layout problem in the design of a centralized communication network with unreliable links and node outage costs. The node outage cost associated with a terminal node is a cost incurred by the network user whenever that terminal node is unable to communicate with the central node due to failure of a link. We suggest a two-phase heuristic with a time complexity of O(N3) to solve the problem. We also present a Lagrangean relaxation method to find the lower bound of the objective function value. The lower bound given by the Lagrangean relaxation method is used to estimate the quality of the solution given by the two-phase heuristic. Experimental results over a wide range of problem structures show that the average solution given by the two-phase heuristic is within 10% of the optimal objective function value.
Minimum cost network flow problems with a piecewise linear convex cost function are used to model various optimization problems. They are also used extensively to approximate nonlinear cost functions which may otherwi...
详细信息
In this paper, based on the idea of a projection and contraction method for a class of linear complementarity problems (Refs. 1 and 2), we develop a class of iterative algorithms for linear programming with linear spe...
详细信息
In this paper, based on the idea of a projection and contraction method for a class of linear complementarity problems (Refs. 1 and 2), we develop a class of iterative algorithms for linear programming with linear speed of convergence. The algorithms are used to solve transportation and network problems with up to 10,000 variables. Our experiments indicate that the algorithms are simple, easy to parallelize, and more efficient for some large practical problems.
暂无评论