Optimal assignment of resources to strengthen the weakest link in an uncertain environment

The weakest link principle applies to many real-life situations where a system is as productive as its bottleneck. The purpose of this paper is to show how the efficiency of a manufacturing or service process (i.e., the strength of a chain) may be maximized by optimal allocation of resources to improve the performance of the bottleneck (i.e., strengthen the weakest link) in an uncertain environment. Specifically, we consider two different versions of the stochastic bottleneck assignment problem (SBAP), which is a variation of the classic assignment problem (AP), with respective goals of minimizing the expected longest processing time and maximizing the expected lowest production rate. It is proven that each of the two intrinsically difficult SBAPs is reducible to an efficiently solvable AP provided that the processing times or the production rates are independent random variables following some families of probability distributions.     

Portfolio management with background risk under uncertain mean-variance utility

This paper studies comparative static effects in a portfolio selection problem when the investor has mean-variance preferences. Since the security market is complex, there exists the situation where security returns are given by experts’ estimates when they cannot be reflected by historical data. This paper discusses the problem in such a situation. Based on uncertainty theory, the paper first establishes an uncertain mean-variance utility model, in which security returns and background asset returns are uncertain variables and subject to normal uncertainty distributions. Then, the effects of changes in mean and standard deviation of uncertain background asset on capital allocation are discussed. Furthermore, the influence of initial proportion in background asset on portfolio investment decisions is analyzed when investors have quadratic mean-variance utility function. Finally, the economic analysis illustration of investment strategy is presented.

     

Internet protocol network design with uncertain demand

We present a case study concerning the design and dimensioning of the internet protocol network of TDC, the largest Danish network operator. Due to historical reasons the number of points of presence (POPs) in the network has reached a level, believed to be too high. To point out potential POPs for dismantling, we consider a network planning problem concerning dimensioning of the POPs and capacity expansion of the transmission links of the network. This problem is formulated as a two-stage stochastic program using a finite number of scenarios to describe the uncertain outcome of future demand. The problem is then solved by an L-shaped algorithm, and we report results of our computational experiments.     

Time-dependent optimization of a multi-item uncertain supply chain network: A hybrid approximation algorithm

We consider the uncertain least cost shipping problem. The input is a multi-item supply chain network with time-evolving uncertain costs and capacities. Exploiting the operational law of uncertainty theory, a mathematical model of the problem is established and the indeterminacy factors are tackled. We use the scaling idea together with transformation approach and uncertainty programming to develop a hybrid algorithm to optimize and obtain the uncertainty distribution of the total shipping cost. We analyze the practical performance of the algorithm and present an illustrative example.     

A robust optimization approach for multicast network coding under uncertain link costs

Network coding is a technique that can be used to improve the performance of communication networks by performing mathematical operations at intermediate nodes. An important problem in coding theory is that of finding an optimal coding subgraph for delivering network data from a source node throughout intermediate nodes to a set of destination nodes with the minimum transmission cost. However, in many real applications, it can be difficult to determine exact values or specific probability distributions of link costs. Establishing minimum-cost multicast connections based on erroneous link costs might exhibit poor performance when implemented. This paper considers the problem of minimum-cost multicast using network coding under uncertain link costs. We propose a robust optimization approach to obtain solutions that protect the system against the worst-case value of the uncertainty in a prespecified set. The simulation results show that a robust solution provides significant improvement in worst-case performance while incurring a small loss in optimality for specific instances of the uncertainty.     

Optimization architecture for joint multi-path routing and scheduling in wireless mesh networks

In Wireless Mesh Networks (WMN), the optimal routing of data depends on the link capacities which are determined by link scheduling. The optimal performance of the network, therefore, can only be achieved by joint routing and scheduling optimization. Although the joint single-path routing and scheduling optimization problem has been extensively studied, its multi-path counterpart within wireless mesh networks has not yet been fully investigated. In this paper, we present an optimization architecture for joint multi-path QoS routing and the underlying wireless link scheduling in wireless mesh networks. By employing the contention matrix to represent the wireless link interference, we formulate a utility maximization problem for the joint multi-path routing and MAC scheduling and resolve it using the primal–dual method. Since the multi-path routing usually results in the non-strict concavity of the primal objective function, we first introduce the Proximal Optimization Algorithm to get around such difficulty. We then propose an algorithm to solve the routing subproblem and the scheduling subproblem via the dual decomposition. Simulations demonstrate the efficiency and correctness of our algorithm.     

Multi-service multi-facility network design under uncertainty

The problem of designing high speed networks using different modules of link capacities, in the same model, in order to meet uncertain demands obtained from different probability distribution functions (PDF) is a very hard and challenging real network design problem. The novelty of the new model, compared to previous ones, is to allow installing more than one module per link having equal or different capacities. Moreover, the scenarios of traffic can be generated, according to practical observations, from the main classes of uncertain demands (multi-service) simulated from different PDFs, including heavy tailed ones. These classes of traffic are considered simultaneously for the scenario generation, different from related works in the literature that use only one probability distribution function to simulate the scenarios of traffic. In this work we present the problem formulation and report computational results using branch-and-bound and L-shaped decomposition solution approaches. We consider in the same model up to three different types of modular capacities (multi-facility), since it seems that using more than this can lead to an intractable model. The objective is to minimize penalty (in case of unmet demands) and investment costs. We obtain confidence intervals (with 95% of covering rate) on the expected optimal solution value for the resulting two-stage stochastic integer-modular problem and discuss when they are meaningful. Numerical experiments show that our model can handle up to medium real size instances.     

Altruistic motives,uncertain lifetime and urban public pension replacement rates

This article employs an overlapping generations model with altruistic motives and uncertain lifetime to investigate China's urban public pension system. We examine the effects of the individual account benefit replacement rate, social pool benefit replacement rate, life expectancy and population growth rate on the capital-labour ratio, pension benefits, consumption and utility. We also find the optimal social pool benefit replacement rate. Raising the individual account benefit replacement rate only increases the individual account benefits. Raising the social pool benefit replacement rate increases the social pool benefits and retirement-period consumption, whereas decreases the capital-labour ratio, individual account benefits, working-period consumption and utility. The fall in the population growth rate increases the capital-labour ratio, social pool benefits, individual account benefits, working-period consumption and utility, whereas decreases the retirement-period consumption. The rise in the life expectancy decreases the six variables. The optimal social pool benefit replacement rate falls in case of either risen life expectancy or fallen population growth rate. It further falls under the joint case of risen life expectancy and fallen population growth rate. It will do more good than harm to raise the individual account benefit replacement rate, reduce the social pool benefit replacement rate and strictly implement the population policy.     

Discrete Capacity Assignment in IP networks using Particle Swarm Optimization

This paper presents a design methodology for IP networks under end-to-end Quality-of-Service (QoS) constraints. Particularly, we consider a more realistic problem formulation in which the link capacities of a general-topology packet network are discrete variables. This Discrete Capacity Assignment (DCA) problem can be classified as a constrained combinatorial optimization problem. A refined TCP/IP traffic modeling technique is also considered in order to estimate performance metrics for networks loaded by realistic traffic patterns. We propose a discrete variable Particle Swarm Optimization (PSO) procedure to find solutions for the problem. A simple approach called Bottleneck Link Heuristic (BLH) is also proposed to obtain admissible solutions in a fast way. The PSO performance, compared to that one of an exhaustive search (ES) procedure, suggests that the PSO algorithm provides a quite efficient approach to obtain (near) optimal solutions with small computational effort.     

Capacity and flow assignment of data networks by generalized Benders decomposition

A mixed-integer non-linear model is proposed to optimize jointly the assignment of capacities and flows (the CFA problem) in a communication network. Discrete capacities are considered and the cost function combines the installation cost with a measure of the Quality of Service (QoS) of the resulting network for a given traffic. Generalized Benders decomposition induces convex subproblems which are multicommodity flow problems on different topologies with fixed capacities. These are solved by an efficient proximal decomposition method. Numerical tests on small to medium-size networks show the ability of the decomposition approach to obtain global optimal solutions of the CFA problem.     

On single-path network routing subject to max-min fair flow allocation

Fair allocation of flows in multicommodity networks has been attracting a growing attention. In Max-Min Fair (MMF) flow allocation, not only the flow of the commodity with the smallest allocation is maximized but also, in turn, the second smallest, the third smallest, and so on. Since the MMF paradigm allows to approximate the TCP flow allocation when the routing paths are given and the flows are elastic, we address the network routing problem where, given a graph with arc capacities and a set of origin-destination pairs with unknown demands, we must route each commodity over a single path so as to maximize the throughput, subject to the constraint that the flows are allocated according to the MMF principle. After discussing two properties of the problem, we describe a column generation based heuristic and report some computational results.     

Resource allocation for end-to-end QoS provisioning in a hybrid wireless WCDMA and wireline IP-based DiffServ network

In the future UMTS network, the heterogeneous traffics of multimedia services demand various QoS provisioning. At the same time, the seamlessly conveying of information between mobile users and a hybrid network requires the networking from wireless to wireline domains. However, in both academia and industries, the end-to-end QoS provisioning in the integration of wireline and wireless networks remains a challenge. In this paper, a modeling of a hybrid wireless WCDMA and wireline IP-based DiffServ network is presented to investigate the resource allocation for end-to-end QoS provisioning for multimedia services. In the wireless domain, the mathematical modeling of the cross-layer model including the physical layer, the link layer and the network layer is built. The connection admission control scheme is implemented based on the cross-layer model to determine the amount of resource for different services. In the wireline domain, we define the mapping of QoS classes between UMTS and DiffServ networks according to different QoS requirements. We propose a bandwidth allocation scheme to provide satisfactory packet loss and delay guarantee in DiffServ networks. The final end-to-end admission control scheme combines the resource allocation and admission control in both wireless and wireline domains. The analytical and simulation results show that the proposed resource allocation and admission control schemes work cooperatively in the presented hybrid wireless and wireline networks to guarantee the end-to-end QoS requirements for multimedia services.     

On robust maximum flow with polyhedral uncertainty sets

We address the problem of determining a robust maximum flow value in a network with uncertain link capacities taken in a polyhedral uncertainty set. Besides a few polynomial cases, we focus on the case where the uncertainty set is taken to be the solution set of an associated (continuous) knapsack problem. This class of problems is shown to be polynomially solvable for planar graphs, but NP-hard for graphs without special structure. The latter result provides evidence of the fact that the problem investigated here has a structure fundamentally different from the robust network flow models proposed in various other published works.     

Modeling uncertain passenger arrivals in the elevator dispatching problem with destination control

An Elevator Group Control System (EGCS) assigns an elevator of a group to each passenger transportation request by solving a snapshot optimization problem, the Elevator Dispatching Problem (EDP). In the destination control, passengers register their destination floors in the elevator lobbies, after which the EGCS completes the assignment at once and is not allowed to change it later. Therefore, the EDP is formulated as a stochastic optimal control problem, where uncertain future passenger arrivals are modeled by a Poisson and a geometric Poisson process. The EDP is considered as a certainty equivalent controller in which the uncertain quantities are replaced by their expected values, and as a robust controller in which they take multiple values according to risk scenarios. Numerical experiments show that the expectations do not accurately predict EDP variables. The modeling with the geometric Poisson process results in better forecasting accuracy than with the Poisson process and many scenarios that closely match the realizations of the variables. Hence, the scenarios can be used as a basis for a robust EDP which simultaneously minimizes a passenger service quality criterion and its variation due to uncertain demand.     

Semantics for possibilistic answer set programs: Uncertain rules versus rules with uncertain conclusions

Although Answer Set Programming (ASP) is a powerful framework for declarative problem solving, it cannot in an intuitive way handle situations in which some rules are uncertain, or in which it is more important to satisfy some constraints than others. Possibilistic ASP (PASP) is a natural extension of ASP in which certainty weights are associated with each rule. In this paper we contrast two different views on interpreting the weights attached to rules. Under the first view, weights reflect the certainty with which we can conclude the head of a rule when its body is satisfied. Under the second view, weights reflect the certainty that a given rule restricts the considered epistemic states of an agent in a valid way, i.e. it is the certainty that the rule itself is correct. The first view gives rise to a set of weighted answer sets, whereas the second view gives rise to a weighted set of classical answer sets.     

Quadratic stabilizability of uncertain linear systems containing both constant and time-varying uncertain parameters

This paper is concerned with the problem of stabilizing an uncertain linear system using state feedback control. The uncertain systems under consideration are described by state equations containing unknown but bounded uncertain parameters. The uncertain parameters are classified into two types: either constant or time-varying. Indeed, the main feature of this paper is that it allows one to exploit the fact that some of the uncertain parameters are constant. In order to investigate the question of stabilizability, quadratic Lyapunov functions are used. Hence, the paper deals with the notion of quadratic stabilizability. The main result of the paper is a necessary and sufficient condition for the quadratic stabilizability of the uncertain systems under consideration.     

Parameter estimation and topology identification of uncertain fractional order complex networks

This paper focuses on a significant issue in the research of fractional order complex network, i.e., the identification problem of unknown system parameters and network topologies in uncertain complex networks with fractional-order node dynamics. Based on the stability analysis of fractional order systems and the adaptive control method, we propose a novel and general approach to address this challenge. The theoretical results in this paper have generalized the synchronization-based identification method that has been reported in several literatures on identifying integer order complex networks. We further derive the sufficient condition that ensures successful network identification. An uncertain complex network with four fractional-order Lorenz systems is employed to verify the effectiveness of the proposed approach. The numerical results show that this approach is applicable for online monitoring of the static or changing network topology. In addition, we present a discussion to explore which factor would influence the identification process. Certain interesting conclusions from the discussion are obtained, which reveal that large coupling strengths and small fractional orders are both harmful for a successful identification.     

Telecommunication Network Capacity Design for Uncertain Demand

The expansion of telecommunication services has increased the number of users sharing network resources. When a given service is highly demanded, some demands may be unmet due to the limited capacity of the network links. Moreover, for such demands, telecommunication operators should pay penalty costs. To avoid rejecting demands, we can install more capacities in the existing network. In this paper we report experiments on the network capacity design for uncertain demand in telecommunication networks with integer link capacities. We use Poisson demands with bandwidths given by normal or log-normal distribution functions. The expectation function is evaluated using a predetermined set of realizations of the random parameter. We model this problem as a two-stage mixed integer program, which is solved using a stochastic subgradient procedure, the Barahona's volume approach and the Benders decomposition.     

A distributionally robust optimization model for batch nonlinear switched time-delay system considering uncertain output measurements

In this paper, we consider a nonlinear switched time-delay (NSTD) system with unknown switching times and unknown system parameters, where the output measurement is uncertain. This system is the underling dynamical system for the batch process of glycerol bioconversion to 1,3-propanediol induced by Klebsiella pneumoniae. The uncertain output measurement is regarded as a stochastic vector (whose components are stochastic variables) and the only information about its distribution is the first-order moment. The objective of this paper is to identify the unknown quantities of the NSTD system. For this, a distributionally robust optimization problem (a bi-level optimization problem) governed by the NSTD system is proposed, where the relative error under the environment of uncertain output measurements is involved in the cost functional. The bi-level optimization problem is transformed into a single-level optimization problem with non-smooth term through the application of duality theory in probability space. By applying the smoothing technique, the non-smooth term is approximated by a smooth term and the convergence of the approximation is established. Then, the gradients of the cost functional with respect to switching times and system parameters are derived. A hybrid optimization algorithm is developed to solve the transformed problem. Finally, we verify the obtained switching times and system parameters, as well as the effectiveness of the proposed algorithm, by solving this distributionally robust optimization problem.