No. 2 (2012)
Published:
2012-06-30
ARTICLES FROM THIS ISSUE
-
On MILP Models for the OWA Optimization
Abstract
The problem of aggregating multiple outcomes to form overall objective functions is of considerable importance in many applications. The ordered weighted averaging (OWA) aggregation uses the weights assigned to the ordered values (i.e., to the largest value, the second largest and so on) rather than to the specific coordinates. It allows to evaluate solutions impartially, when distribution of outcomes is more important than assignments these outcomes to the specific criteria. This applies to systems with multiple independent users or agents, whose objectives correspond to the criteria. The ordering operator causes that the OWA optimization problem is nonlinear. Several MILP models have been developed for the OWA optimization. They are built with different numbers of binary variables and auxiliary constraints. In this paper we analyze and compare computational performances of the different MILP model formulations.
-
Developing a Ring-Based Optical Network Structure with Glass-Through Nodes
Abstract
An important issue in designing optical transport networks (OTN) is security. The concept of 1+1 protection requires to connect each origin-destination(OD)-pair by at least two node-disjoint paths. In the case of a single edge or node failure, the connection of all OD-pairs is maintained under 1+1 protection. On a ring, 1+1 protection is given naturally. Moreover, on rings, the routing effort is typically decreasing. These observations motivate the investigation of ring structures for OTN. When developing a ring structure for telecommunication networks, several subtasks can be identified. Ringshave to be designed, OD-pairs have to be assigned to rings, communication among rings has to be defined, a proper flow routing has to be chosen, and rings have to be dimensioned regarding flow capacity. In this paper, we address the first two issues, namely generation of rings and assignment of OD-pairs to rings. Our approach allows to distinguish active and non-active (glass-through) nodes in OTN. Active nodes are equipped with active routing hardware that weakens the optical signal and has impact on feasible ring lengths. Non-active nodes do not influence the optical signal. Although a consideration of active/non-active nodes is important in ring design, only a few references address this issue. We propose an algorithm for generating random ring candidates. Moreover, we present a mathematical model for the assignment of OD-pairs to rings subject to a feasible choice of active nodes. We test our methods using a case of Deutsche Telekom.
-
Requirements of 4G-Based Mobile Broadband on Future Transport Networks
Abstract
Long term evolution technologies provide new standards in mobile communications regarding available bandwidth. It is expected that users of one radio cell will share more than 100 Mbit/s in future. To take advantage of the full feature set of next generation mobile networks, transport network design has to face new requirements, caused by the architectural changes of LTE technologies. Especially the newly defined X2 interface impacts on the transport network requirements. X2 enables direct communication between evolved base stations (eNBs) and thus, enforces local solutions. At the same time a tendency of locating network elements at fewer, central sites to reduce operational expenditure can be observed, in particular concerning the transport layer. This leads to
the question of how the direct X2 connection of eNBs on the logical layer can be accommodated with a general centralization of transport networks. Our considerations show that for LTE, a centralized transport network is able to realize the local meshing between eNBs. However, for LTE Advanced, the standards currently discussed by the 3GPP initiative could lead to enhanced requirements on the X2 interface latency. Consequently, the implications for the network architecture have to be analyzed in more detail. -
Hierarchical Multiobjective Routing Model in MPLS Networks with Two Service Classes – A Comparison Case Study
Abstract
A two-level hierarchical multicriteria routing model for multiprotocol label switching networks with two service classes (QoS, i.e., with quality of service requirements, and best effort services) and alternative routing is reviewed in this paper. A heuristic resolution approach, where nondominated solutions are obtained throughout the heuristic run and kept in an archive for further analysis is also reviewed. In this paper, an extensive analysis of the application of this procedure to two reference test networks for various traffic matrices is presented. Also a comparison of the results of our method with a lexicographic optimization approach based on a multicommodity flow formulation using virtual networks is carried out. Finally, results of a stochastic discrete event simulation model developed for these networks will be shown to illustrate the effectiveness of the resolution approach and to assess the inaccuracies of the analytic results.
-
Uplift Modeling in Direct Marketing
Abstract
Marketing campaigns directed to randomly selected customers often generate huge costs and a weak response. Moreover, such campaigns tend to unnecessarily annoy customers and make them less likely to answer to future communications. Precise targeting of marketing actions can potentially results in a greater return on investment. Usually, response models are used to select good targets. They aim at achieving high prediction accuracy for the probability of purchase based on a sample of customers, to whom a pilot campaign has been sent. However, to separate the impact of the action from other stimuli and spontaneous purchases we should model not the response probabilities themselves, but instead, the change in those probabilities caused by the action. The problem of predicting this change is known as uplift modeling, differential response analysis, or true lift modeling. In this work, tree-based classifiers designed for uplift modeling are applied to real marketing data and compared with traditional response models, and other uplift modeling techniques described in literature. The experiments show that the proposed approaches outperform existing uplift modeling algorithms and demonstrate significant advantages of uplift modeling over traditional, response based targeting.
-
Integrated Routing and Network Flow Control Embracing Two Layers of TCP/IP Networks – Methodological Issues
Abstract
A cross-layer network optimization problem is considered. It involves network and transport layers, treating both routing and flows as decision variables. Due to the nonconvexity of the capacity constraints, when using Lagrangian relaxation method a duality gap causes numerical instability. It is shown that the rescue preserving separability of the problem may be the application of the augmented Lagrangian method, together with Cohen’s Auxiliary Problem Principle.
-
Auction Models Supporting End-to-End Connection Trading
Abstract
The paper concerns bandwidth allocation problem on the telecommunication market where there are many sellers and buyers. Sellers offer the bandwidth of telecommunication links. Buyers are interested in the purchase of the bandwidth of several links that makes up an end-to-end connection between two nodes of telecommunication network. We analyze three auction models supporting such a bandwidth exchange: NSP (network second price), BCBT (model for balancing communication bandwidth trading) and BCBT-CG which is a modification of BCBT that applies column generation technique. All of these models concern divisible network resources, treat bandwidth of telecommunication links as an elementary commodity offered for sale, and allow for purchasing bandwidth along multiple paths joining two telecommunication nodes. All of them also aim at maximizing the social welfare. Considered auction models have been compared in the respect of economic and computational efficiency. Experimental studies have been performed on several test instances based on the SNDlib library data sets.
-
Analysis and Modeling of Domain Registration Process
Abstract
The paper presents analysis of the domain name reservation process for the polish .pl domain. Two models of various time scale are constructed and finally combined to build long range high resolution model. The results of prediction are verified using real data.
-
RTT+ – Time Validity Constraints in RTT Language
Abstract
Most of the traditional access control models, like mandatory, discretionary and role based access control make authorization decisions based on the identity, or the role of the requester, who must be known to the resource owner. Thus, they may be suitable for centralized systems but not for decentralized environments, where the requester and service provider or resource owner are often unknown to each other. To overcome the shortcomings of traditional access control models, trust management models have been presented. The topic of this paper is three different semantics (set-theoretic, operational, and logic- programming) of RTT , language from the family of role-based trust management languages (RT). RT is used for representing security policies and credentials in decentralized, distributed access control systems. A credential provides information about the privileges of users and the security policies issued by one or more trusted authorities. The set-theoretic semantics maps roles to a set of sets of entity names. Members of such a set must cooperate in order to satisfy the role. In the case of logic-programming semantics, the credentials are translated into a logic program. In the operational semantics the credentials can be established using a simple set of inference rules. It turns out to be fundamental mainly in large- scale distributed systems, where users have only partial view of their execution context. The core part of this paper is the introduction of time validity constraints to show how that can make RTT language more realistic. The new language, named RTT+ takes time validity constraints into account. The semantics for RTT+ language will also be shown. Inference system will be introduced not just for specific moment but also for time intervals. It will evaluate maximal time validity, when it is possible to derive the credential from the set of available credentials. The soundness and completeness of the inference systems with the time validity constraints with respect to the set-theoretic semantics of RTT+ will be proven.
-
Application of Social Network Analysis to the Investigation of Interpersonal Connections
Abstract
Social network analysis (SNA) is an important and valuable tool for knowledge extraction from massive and unstructured data. Social network provides a powerful abstraction of the structure and dynamics of diverse kinds of interpersonal connection and interaction. In this paper, we address issues associated with the application of SNA to the investigation and analysis of social relationships of people. We provide a brief introduction to representation and analysis of social networks, SNA models and methods. The main objective is to investigate the application of SNA techniques to data mining in case of two social networks Facebook and Twitter. The presented simulations illustrate how social analysis can be used to determine the interpersonal connections, importance of actors in a given social network and detect communities of people. We then discuss strength and weakness of SNA techniques.
-
Effective Design of the Simulated Annealing Algorithm for the Flowshop Problem with Minimum Makespan Criterion
Abstract
In this paper we address the n-job, m-machine flowshop scheduling problem with minimum completion time (makespan) as the performance criterion. We describe an efficient design of the Simulated Annealing algorithm for solving approximately this NP-hard problem. The main difficulty in implementing the algorithm is no apparent analogy for the temperature as a parameter in the flowshop combinatorial problem. Moreover, the quality of solutions is dependent on the choice of cooling scheme, initial temperature, number of iterations, and the temperature decrease rate at each step as the annealing proceeds. We propose how to choose the values of all the aforementioned parameters, as well as the Boltzmann factor for the Metropolis scheme. Three perturbation techniques are tested and their impact on the solutions quality is analyzed. We also compare a heuristic and randomly generated solutions as initial seeds to the annealing optimization process. Computational experiments indicate that the proposed design provides very good results – the quality of solutions of the Simulated Annealing algorithm is favorably compared with two different heuristics.
-
Diffusion in Networks
Abstract
In this paper a concept of method and its application examining a dynamic of diffusion processes in networks is considered. Presented method was used as a core framework for system CARE (Creative Application to Remedy Epidemics).
-
Compact Broadband Rat-Race Coupler in Multilayer Technology Designed with the Use of Artificial Right- and Left-Handed Transmission Lines
Abstract
The paper presents a compact broadband rat-race coupler for the first time designed and realized in a mul- tilayer microstrip technology. To achieve both broad operational bandwidth and a compact size the 270◦ transmission line of a conventional rat-race, coupler has been replaced by a –90◦ left-handed transmission line realized with the use of a quasi-lumped element technique. Moreover, to achieve better compactness of the resulting coupler, all 90◦ right-handed transmission lines have been realized with the use of the same technique. It has been also proved that simple LC approximation of a left-handed transmission line can be successfully used for the design. Moreover, it has been shown that when appropriately chosen, the multilayer dielectric structure allows for realization of structures designed with the use of this simple approximation, for both right-handed and left-handed transmission lines, without loosing too much of a performance.
