共查询到20条相似文献,搜索用时 15 毫秒
1.
《Stochastics An International Journal of Probability and Stochastic Processes》2013,85(3-4):157-179
This paper proposes an approximation approach to the solution of chance-constrained stochastic programming problems. The results rely in a fundamental way on the theory of convergence of sequences of measurable multifunctions. Particular results are presented for stochastic linear programming problems. 相似文献
2.
In this paper, we consider the problem of designing reliable networks that satisfy supply/demand, flow balance, and capacity constraints, while simultaneously allocating certain resources to mitigate the arc failure probabilities in such a manner as to minimize the total cost of network design and resource allocation. The resulting model formulation is a nonconvex mixed-integer 0-1 program, for which a tight linear programming relaxation is derived using RLT-based variable substitution strategies and a polyhedral outer-approximation technique. This LP relaxation is subsequently embedded within a specialized branch-and-bound procedure, and the proposed approach is proven to converge to a global optimum. Various alternative partitioning strategies that could potentially be employed in the context of this branch-and-bound framework, while preserving the theoretical convergence property, are also explored. Computational results are reported for a hypothetical scenario based on different parameter inputs and alternative branching strategies. Related optimization models that conform to the same class of problems are also briefly presented. 相似文献
3.
Peter Kubat 《Annals of Operations Research》1991,33(2):95-105
In today's highly competitive telecommunication market, customers expect and demand reliable and high-quality service. In order to please customers, new telecommunication systems and networks which support a wide range of voice, data and video services are being designed with extremely high reliability/availability requirements, but usually without much consideration of cost. These super-reliable systems are generally very complex and therefore extremely expensive to develop, build, and operate. Increased costs are going to be reflected in the price of the services the system is offering, and the reliability benefits may be overshadowed by the fact that the procurement and operations of the system may be too costly; customers will be drawn to competitors with less expensive network solutions and more affordable services. This paper discusses alternative approaches to the system design from the point of view of future costs. We will illustrate that the system can be improved not only by increasing reliability of subsystems, but also by effectively utilizing system operations support. The operations support alternatives may be less expensive than reliability improvements and, in addition, may provide many strategic marketing advantages. In the telecommunication industry, a high-quality service requirement usually translates into a high-quality network. Network support is defined, and customers' expectations are discussed. In an example, based on the concept of distributed switching systems, we show how the selection of the maintenance/repair operation policy may influence the cost of the system operations and reduce the hardware costs involved. 相似文献
4.
We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small. 相似文献
5.
《European Journal of Operational Research》2006,174(3):1968-1978
In the process of solving many forms of the local access network design problem, the basic model of the tree knapsack problem (TKP) is used as a building block for the search engine of the solution strategy. Various solution strategies can be used to solve this problem. An approach that use standard software coupled with enhanced modelling is presented for the TKP. Enhanced modelling is used to partition the TKP into sub-problems that is easier to solve using standard off the shelve software. The basic approach is described and empirical work is presented. Empirical comparisons are also given relating this approach with some algorithms suggested by other authors. 相似文献
6.
7.
Nathalie Faure Philippe Chrtienne Eric Gourdin Francis Sourd 《Discrete Optimization》2007,4(3-4):360-377
This paper considers the problem of aggregating several multicast sessions. A multicast session is defined as a subset of clients requiring the same information. Besides, each client can require several multicast sessions. A telecommunication network cannot manage many multicast sessions at the same time. It is hence necessary to group the sessions into a limited number of clusters. The problem then consists in aggregating the sessions into clusters to limit the number of unnecessary information sent to clients. The strong relationship of the problems with biclique problems in bipartite graph is established. We then model the problems using integer quadratic and linear programming formulations. We investigate some properties to strengthen the models. Several algorithms are provided and compared with a series of numerical experiments. 相似文献
8.
Oktay Günlük 《Mathematical Programming》1999,86(1):17-39
We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point
traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so
that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new
facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities,
are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report
on our computational experience using real-life data.
Received April 29, 1997 / Revised version received January 9, 1999? Published online June 28, 1999 相似文献
9.
We present several classes of facet-defining inequalities to strengthen polyhedra arising as subsystems of network design
problems with survivability constraints. These problems typically involve assigning capacities to a network with multicommodity
demands, such that after a vertex- or edge-deletion at least some prescribed fraction of each demand can be routed.
Received: December 1997 / Accepted: April 2000?Published online September 20, 2000 相似文献
10.
We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled. 相似文献
11.
12.
《European Journal of Operational Research》2003,148(1):126-140
Optical fiber provides tremendous advantages in being able to carry a wide range of services including video on demand, video conferencing, distance learning, remote medical imaging, and telecommuting. The high capacities encourage carriers to create networks that are substantially sparser than previous copper based networks. A recent publication by the Telecommunications Industry Association indicated that investment in fiber optics is projected to reach $35 billion in the year 2003. Given the magnitude of investments, the design of networks becomes a very important issue. Most telecommunication companies (telcos), IT consulting companies, network equipment manufacturers and network service providers have extensive network design groups. The primary function of these groups is to design the most efficient networks both in terms of costs and performance and maintain them. These designers need flexible tools to support topological network design decisions. These decisions involve significant levels of investments in transmissions and switching facilities, and impact the resulting networks’ performance fundamentally.In this paper we study a special type of a network design problem called the hop constrained backbone network design problem. We present new mathematical programming formulations of the problem and develop an efficient solution procedure based on the linear programming relaxation. Extensive computational results across a number of networks are reported. 相似文献
13.
A signalized road network is considered where the set of link capacity expansions and signal setting variables are simultaneously determined. This paper addresses a new optimization scheme for a signalized road network design problem (SRNDP). A SRNDP can be formulated as a mathematical program with equilibrium constraints (MPEC) where user equilibrium is expressed as a variational inequality problem. Due to non-differentiability of the perturbed solutions in equilibrium constraints, a non-smooth model is established. A bundle subgradient projection (BSP) method is presented with global convergence. Numerical calculations are conducted on a real data city road network and large-scale grid networks where promising results are obtained. 相似文献
14.
Damianos Gavalas Charalampos Konstantopoulos Konstantinos Mastakas Grammati Pantziou 《Journal of Heuristics》2014,20(3):291-328
The tourist trip design problem (TTDP) refers to a route-planning problem for tourists interested in visiting multiple points of interest (POIs). TTDP solvers derive daily tourist tours, i.e., ordered visits to POIs, which respect tourist constraints and POIs attributes. The main objective of the problem discussed is to select POIs that match tourist preferences, thereby maximizing tourist satisfaction, while taking into account a multitude of parameters and constraints (e.g., distances among POIs, visiting time required for each POI, POIs visiting days/hours, entrance fees, weather conditions) and respecting the time available for sightseeing on a daily basis. The aim of this work is to survey models, algorithmic approaches and methodologies concerning tourist trip design problems. Recent approaches are examined, focusing on problem models that best capture a multitude of realistic POIs attributes and user constraints; further, several interesting TTDP variants are investigated. Open issues and promising prospects in tourist trip planning research are also discussed. 相似文献
15.
Vojtech Blint 《Journal of Discrete Algorithms》2003,1(3-4):339-355
Let G be an undirected graph with two edge costs (c-cost and d-cost). We want to minimize the diameter of a spanning subgraph S (under d-cost) subject to the constraint that the total cost of the edges in S (with respect to c) does not exceed a given budget. We prove that this problem is non-approximable, even in some special cases. Similar results are proved if the stretch factor or the root stretch factor is considered instead of the diameter. 相似文献
16.
We discuss problems of the application of various reliability theories in models of optimal design of structures. Using the example of the problem of optimizing (with respect to the minimal mass criterion) the parameters of an inclined spherical shell reinforced by a network of ribs and subject to a random load stated as a nonlinear programming problem we give a comparative analysis of the optimal designs obtained using the theory of Bolotin and the theory of Kapur-Lamberson. One figure. One table. Bibliography: 5 titles.Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 30, 1989, pp. 82–87. 相似文献
17.
18.
In this paper, extended formulations for stochastic uncapacitated lot-sizing problems with and without backlogging are developed in higher dimensional spaces that provide integral solutions. Moreover, physical meanings of the decision variables in the extended formulations are explored and special cases with more efficient formulations are studied. 相似文献
19.
This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed. 相似文献
20.
B Wagner 《The Journal of the Operational Research Society》2008,59(7):932-938
Improved model formulations for hub covering problems are proposed. We discuss multiple and single allocation problems, including non-increasing quantity-dependent transport time functions for transport links for the latter case. Computational results are presented, which show that the new solution approaches for problems with quantity-independent transport times clearly outperform previous work on this topic. 相似文献