Approximations for chance-constrained programming problems

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.     

A global optimization algorithm for reliable network design

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.     

Alternatives for reliable and quality telecommunication network design

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.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

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.     

Tree knapsack approaches for local access network design

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.     

Biclique completion problems for multicast network design

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.     

A branch-and-cut algorithm for capacitated network design problems

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     

Strong inequalities for capacitated survivable network design problems

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     

Exponential approximation schemata for some network design problems

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.     

New formulations and solution procedures for the hop constrained network design problem

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.     

A non-smooth model for signalized road network design problems

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.     

A survey on algorithmic approaches for solving tourist trip design problems

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.     

The non-approximability of bicriteria network design problems

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.     

On formulations of optimal design problems with respect to reliability criteria for reinforced shells

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.     

Extended formulations for stochastic lot-sizing problems

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.     

General network design: A unified view of combined location and network design problems

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.     

Model formulations for hub covering problems

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.