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.
The performance, reliability, cost, size and energy usage of computing systems can be improved by one or more orders of magnitude by the systematic use of modern control and optimization methods. Computing systems rel...
详细信息
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.
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.
N patients must be planned in an operating theatre over a medium term horizon (one or two weeks). This operating theatre is composed of several operating rooms and of one recovery room where several beds are available...
详细信息
N patients must be planned in an operating theatre over a medium term horizon (one or two weeks). This operating theatre is composed of several operating rooms and of one recovery room where several beds are available. Each patient needs a particular surgical procedure, which defines the human (surgeon) and material (equipment) resources to use and the intervention duration. Additive characteristics must be taken into account: hospitalisation date, intervention deadline, etc. The patient satisfaction and resource efficiency are sought. These two criteria are, respectively, modelled by hospitalisation costs, i.e. the patient stay duration, and the overtime costs, i.e. the resource overloads. We propose to solve this problem in two steps. First, an operating theatre planning is defined. It consists in assigning patients to operating rooms over the horizon. Second, each loaded operating room is scheduled individually in order to synchronise the various human and material resources used. This paper focuses on the first step, i.e. the operating theatre planning, which defines a general assignment problem, i.e. a NP hard problem. In order to solve heuristically this problem, an assignment model with resource capacity and time-window additive constraints is proposed. Integrating most of the constraints in the cost objective function, an extension of the Hungarian method has been developed to calculate the operating theatre planning. This primal-dual heuristic has been successfully experimented on a wide range of problem test data. (C) 2003 Elsevier Science B.V. All rights reserved.
This text summarizes the results related to Operations research contained in the PhD thesis defended by the author in June 2006 under the supervision of Karel Soudan at the Universiteit Antwerpen in Belgium. The thesi...
详细信息
This text summarizes the results related to Operations research contained in the PhD thesis defended by the author in June 2006 under the supervision of Karel Soudan at the Universiteit Antwerpen in Belgium. The thesis is written in English and is available from the author upon request (Reniers in shaping an integrated cluster safety culture in the chemical process industry, 415 p, 2006a). This work investigates the optimization of major accident precautions in the chemical process industry. An integrated cluster safety culture is shaped by developing three separate capabilities (procedural, human, and technological) and by both integrating and optimizing them using the well-known Deming loop. The technological (Operations research) part develops a cluster management decision support system. The latter tool offers prevention planning guidance in taking adequate precaution measures to overcome complex domino effect risks.
This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and trans...
详细信息
暂无评论