Dissertations / Theses on the topic 'Network of problem'
To see the other types of publications on this topic, follow the link: Network of problem.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Network of problem.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Araújo, Ricardo Matsumura de. "Memetic networks : problem-solving with social network models." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2010. http://hdl.handle.net/10183/25515.
Full textAbstract:
Sistemas sociais têm se tornado cada vez mais relevantes para a Ciência da Computação em geral e para a Inteligência Artificial em particular. Tal interesse iniciou-se pela necessidade de analisar-se sistemas baseados em agentes onde a interação social destes agentes pode ter um impacto no resultado esperado. Uma tendência mais recente vem da área de Processamento Social de Informações, Computação Social e outros métodos crowdsourced, que são caracterizados por sistemas de computação compostos de pessoas reais, com um forte componente social na interação entre estas. O conjunto de todas interações sociais e os atores envolvidos compõem uma rede social, que pode ter uma forte influência em o quão eficaz ou eficiente o sistema pode ser. Nesta tese, exploramos o papel de estruturas de redes em sistemas sociais que visam a solução de problemas. Enquadramos a solução de problemas como uma busca por soluções válidas em um espaço de estados e propomos um modelo - a Rede Memética - que é capaz de realizar busca utilizando troca de informações (memes) entre atores interagindo em uma rede social. Tal modelo é aplicado a uma variedade de cenários e mostramos como a presença da rede social pode melhorar a capacidade do sistema em encontrar soluções. Adicionalmente, relacionamos propriedades específicas de diversas redes bem conhecidas ao comportamento observado para os algoritmos propostos, resultando em um conjunto de regras gerais que podem melhorar o desempenho de tais sistemas sociais. Por fim, mostramos que os algoritmos propostos são competitivos com técnicas tradicionais de busca heurística em diversos cenários.Social systems are increasingly relevant to computer science in general and artificial intelligence in particular. Such interest was first sparkled by agent-based systems where the social interaction of such agents can be relevant to the outcome produced. A more recent trend comes from the general area of Social Information Processing, Social Computing and other crowdsourced systems, which are characterized by computing systems composed of people and strong social interactions between them. The set of all social interactions and actors compose a social network, which may have strong influence on how effective the system can be. In this thesis, we explore the role of network structure in social systems aiming at solving problems, focusing on numerical and combinatorial optimization. We frame problem solving as a search for valid solutions in a state space and propose a model - the Memetic Network - that is able to perform search by using the exchange of information, named memes, between actors interacting in a social network. Such model is applied to a variety of scenarios and we show that the presence of a social network greatly improves the system capacity to find good solutions. In addition, we relate specific properties of many well-known networks to the behavior displayed by the proposed algorithms, resulting in a set of general rules that may improve the performance of such social systems. Finally, we show that the proposed algorithms can be competitive with traditional heuristic search algorithms in a number of scenarios.
2
Balakrishnan, Anantaram, Thomas L. Magnanti, and Prakash Mirchandani. "The Multi-Network Design Problem." Massachusetts Institute of Technology, Operations Research Center, 1991. http://hdl.handle.net/1721.1/5200.
Full textAbstract:
This paper studies a new multi-facility network synthesis problem, called the Multi-level Network Design (MLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks whose nodes have varying levels of importance:the more critical or higher level nodes require higher grade interconnections. Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the MLND problem seeks a connected design that minimizes total fixed cost while spanning all the nodes, and connecting nodes at each level via facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem. In this paper, we describe alternative model formulations for this problem and analyze the worst-case performance for heuristics based upon Steiner and spanning tree computations. For one model that we consider, the heuristic worst-case bounds on the performance ratio are either 4/3 or the worst-case performance ratio p of the embedded Steiner tree heuristic. A companion paper develops and tests a dual ascent procedure that generates tight upper and lower bounds on the optimal value of the problem. Keywords: Network design, integer programming, valid inequalities, worstcase analysis of heuristics.
3
Leung, Cheuk Fun Bede. "Subnet generation problem : solutions to a new network routing problem." Thesis, Imperial College London, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.444214.
Full text
4
Livada, M. "Implicit network descriptions of RLC networks and the problem of re-engineering." Thesis, City, University of London, 2017. http://openaccess.city.ac.uk/17916/.
Full textAbstract:
The thesis deals with aspects of Systems Re-engineering specialised to the case of passive electrical networks. Re-engineering is a problem different from traditional control problems and this emerges when it is realised that the systems designed in the past cannot perform according to the new performance requirements and such performance cannot be improved by traditional control activities. Re-engineering implies that we intervene in early stages of system design involving sub-processes, values of physical elements, interconnection topology, selection of systems of inputs and outputs and of course retuning of control structures. This is a very challenging problem which has not been addressed before in a systematic way and needs fundamental new thinking, based on understanding of structure evolution during the stages of integrated design. A major challenge in the study of this problem is to have a system representation that allows study of evolution of system properties as well as structural invariants. For linear systems the traditional system representations, such as transfer functions, state space models and polynomial type models do not provide a suitable framework for study structure and property evolutions, since for every change we need to compute again these models and the transformations we have used do not appear in an explicit form in such models. It is for this reason, for a general system, such system representations are not suitable for study of system representations on re-engineering. It has been recognized that for the special family of systems defined by the passive electrical networks (RLC), there exists a representation introduced by the loop/ nodal analysis, expressed by the impedance/admittance integral-differential models, which have the property of re-engineering transformations of the following type: 1. Changing the values or possible nature of existing elements without changing the network topology, 2. Modifying the network topology without changing network cardinality, that is number of independent loops or nodes, 3. Augmenting or reducing the network by addition or deletion of sub-networks, 4. Combination of all the above transformations. These kinds of transformations may be represented as perturbations on the original impedance/admittance models. The above indicates that impedance/admittance integral-differential models, which from now on will be referred to as Implicit Network Descriptions is the natural vehicle for studying re-engineering on electrical networks. Although issues related to realisation of impedance/admittance transfer functions within RLC topologies, has been the topic of classical network synthesis, the system aspects of such descriptions have not been properly considered. Addressing problems of network re-engineering requires the development of the fundamental system aspects of such new descriptions in terms of McMillan degree, regularity and a number of other properties. Certain problems of evolution (of system properties) are linked to Frequency Assignment, as far as natural frequencies under re-engineering and this requires use of techniques developed within control theory for Frequency Assignment Problems.
5
Hojati, Mehran. "Network synthesis problem : cost allocation and algorithms." Thesis, University of British Columbia, 1987. http://hdl.handle.net/2429/27318.
Full textAbstract:
This thesis is concerned with a network design problem which is referred to in the literature as the network synthesis problem. The objective is to design an undirected network, at a minimum cost, which satisfies known requirements, i.e., lower bounds on the maximum flows, between every pair of nodes. If the requirements are to be satisfied nonsimultaneously, i.e., one at a time, the problem is called the nonsimultaneous network
synthesis problem, whereas if the requirements are to be satisfied simultaneously, the problem is called the simultaneous network synthesis problem. The total construction
cost of the network is the sum of the construction cost of capacities on the edges, where the construction cost of a unit capacity is fixed for any edge, independent of the size of the capacity, but it may differ from edge to edge. The capacities are allowed to assume noninteger nonnegative values. The simultaneous network synthesis problem was efficiently solved by Gomory and Hu [60], whereas the nonsimultaneous network synthesis problem can only be formulated and solved as a linear program with a large number of constraints. However, the special equal-cost case, i.e., when the unit construction
costs are equal across the edges, can be efficiently solved, see Gomory and Hu [60], by some combinatorial method, other than linear programming. A cost allocation problem which is associated with the network synthesis problem would naturally arise, if we assume that the various nodes in the network represent different users or communities.
In this case, we need to find a fair method for allocating the construction cost of the network among the different users. An interesting generalization of the nonsimultaneous
network synthesis problem, the Steiner network synthesis problem, is derived, when only a proper subset of the nodes have positive requirements from each other.
The thesis is concerned with two issues. First, we will analyze the cost allocation problems arising in the simultaneous and the equal cost nonsimultaneous network synthesis
problem. Secondly, we will consider the Steiner network synthesis problem, with particular emphasis on simplifying the computations in some special cases, not considered
before. We will employ cooperative game theory to formulate the cost allocation problems, and we will prove that the derived games are 'concave', which implies the existence of the core and the inclusion of the Shapley value and the nucleolus in the core, and then we will present irredundant representations of the cores. For the equal cost nonsimultaneous network synthesis game, we will use the irredundant representation of the core to provide an explicit closed form expression for the nucleolus of the game, when the requirement structure is a spanning tree; then, we will develop, in a special case, a decomposition of the game, which we will later use to efficiently compute the Shapley value of the game when the requirement structure is a tree; the decomposition will also be used for the core and the nucleolus of the game in the special case. For the simultaneous network synthesis game, we will also use the irredundant representation of the core to derive an explicit closed form expression for the nucleolus, and we will also decompose the core of this game in the special case, and prove that the Shapley value and the nucleolus coincide.
Secondly, for the Steiner network synthesis problem, two conceptually different contributions
have been made, one being a simplifying transformation, and the other being the case when the network has to be embedded in (i.e., restricted to) some special graphs. Namely, when the requirement structure is sparse (because there are only a few demand nodes and the rest are just intermediate nodes) and the positive requirements are equal, we will employ a transformation procedure to simplify the computations. This will enable us to efficiently solve the Steiner network synthesis problem with five or less nodes which have equal positive requirements from each other. Finally, when the solution network to the Steiner network synthesis problem is to be embedded in (restricted to) some special graphs, namely trees, rings (circles), series-parallel graphs, or M₂ and M₃-free graphs, we will provide combinatorial algorithms which are expected to simplify the computations.Business, Sauder School of
Graduate
6
Ramahi, Muhannad Hasan. "Resident Scheduling Problem." Thesis, Virginia Tech, 1998. http://hdl.handle.net/10919/37057.
Full textAbstract:
This thesis is concerned with the Resident Scheduling Problem (RSP) in which a good schedule is desired that will meet both departmental requirements and residents' preferences. Three scenarios that represent most situations and account for various departmental requirements and needs are described. Although similar scheduling problems are considered in the literature, no analysis exists that adequately deals with this specific problem. The problem is modeled as a mixed-integer program (MIP) and heuristic solution procedures are developed for the different identified scheduling scenarios. These procedures exploit the network structure of the problem which is an important feature that enhances problem solvability. For the sake of comparison, the problem is also solved exactly via the CPLEX-MIP package. The contribution of this work is important since many hospitals are still utilizing manual techniques in preparing their own schedules, expending considerable effort and time with less scheduling flexibility.Master of Science
7
鄭國榮 and Kwok-wing Philip Cheng. "Some results on the location problem." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1998. http://hub.hku.hk/bib/B31215051.
Full text
8
Cheng, Kwok-wing Philip. "Some results on the location problem /." Hong Kong : University of Hong Kong, 1998. http://sunzi.lib.hku.hk/hkuto/record.jsp?B19589074.
Full text
9
Magnanti, Thomas L., Prakash Mirchandani, and Rita Vachani. "Modeling and Solving the Capacitated Network Loading Problem." Massachusetts Institute of Technology, Operations Research Center, 1991. http://hdl.handle.net/1721.1/5375.
Full textAbstract:
This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-topoint demand between various pairs of nodes of a network must be met by installing (loading) capacitated facilities on the arcs. The facilities are chosen from a small set of alternatives and loading a particular facility incurs an arc specific and facility dependent cost. The problem is to determine the configuration of facilities to be loaded on the arcs of the network that will satisfy the given demand at minimum cost. Since we need to install (load) facilities to carry the required traffic, we refer to the problem as the network loading problem. In this paper, we develop modeling and solution approaches for the problem. We consider two approaches for solving the underlying mixed integer programming model: (i) a Lagrangian relaxation strategy, and (ii) a cutting plane approach that uses three classes of valid inequalities that we identify for the problem. In particular, we show that a linear programming formulation that includes the valid inequalities always approximates the value of the mixed integer program at least as well as the Lagrangian relaxation bound (as measured by the gaps in the objective functions). We also examine the computational effectiveness of these inequalities on a set of prototypical telecommunications data. The computational results show that the addition of these inequalities considerably improves the gap between the integer programming formulation of the problem and its linear programming relaxation: for 6 - 15 node problems from an average of 25% to an average of 8%. These results show that strong cutting planes can be an effective modeling and algorithmic tool for solving problems of the size that arise in the telecommunications industry.
10
Fréchette, Alexandre. "Hub routing for the robust network design problem." Thesis, McGill University, 2013. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=114431.
Full textAbstract:
Robust network design (RND) applies the concept of robustness from optimization with uncertainty to the area of network design. Primary motivations stem from applications in telecommunication networks. The main presupposition is that demands across the networks are variable or unpredictable. They originate from a predefined demand set, called a demand universe. Moreover, practical impediments of network design enforce the routing of the demands to be oblivious, or fixed in advance, and to not depend on a particular instantiation from the demand universe. Additional restrictions, referred to as a routing model, are often enforced on the routing's structure. Shortest paths (SP) and hub (HUB) routing models have received particular attention, both on the theoretical and practical level. In this work, we introduce a new routing model, called the hierarchical hub routing model (HH), as a generalization to HUB. We study the theoretical properties of RND restricted to HH (RNDHH). Namely, we show its APX-hardness and provide a O(log n)-approximation algorithm. We then show how RNDHH is tractable when the problem is constrained to a particular demand universe based on demands routable on a tree. We also compare the costs of optimal solutions to RND using HH and other important oblivious routing models. Finally, we leverage HH in a practical study of a new demand universe called the capped hose model, which is a blend of the hose and the pipe model, two widely used demand universes. We use the capped hose model to shed light on which demand universes favour more a SP-like as opposed to a HH-like routing. To do so, we develop a heuristic algorithm for RNDHH, and benchmark our approach against SP using representative carrier networks and a variety of capped hose demands, parametrized by their similitude to a hose or pipe model. This study reveals conditions under which multi-hub routings, that is HH, gives improvements over single-hub and shortest path routings.Le design de réseaux robustes (RND) est celui qui applique le concept de robustesse, issu de l'optimisation avec incertitude, au domaine de la conception de réseaux. Les principales motivations derrière cette application découlent de demandes provenant des réseaux de télécommunication. La prémisse principale est que les demandes à travers les réseaux sont variables ou imprévisibles. Toutefois, nous savons que ces demandes proviennent d'un ensemble prédéfini appelé univers de demandes. De plus, des contraintes pratiques du design de réseaux requiert que le routage des demandes soit inconscient, ou fixé d'avance, et qu'il ne dépende pas d'une instanciation particulière de l'univers de demandes. Des contraintes additionnelles, connues sous le nom de modèle de routage, s'appliquent souvent à la structure du routage. Les routages par chemins les plus courts (SP) et par moyeu unique (HUB) ont reçu une attention importante, tant au niveau théorique que pratique. Dans cette thèse, nous introduisons un nouveau modèle de routage appelé routage hiérarchique par moyeux (HH), qui est une généralisation de HUB. Nous étudions les propriétés théoriques de RND restreint à HH (RNDHH). Plus particulièrement, nous démontrons son caractère APX-difficile et fournissons un algorithme O(log n)-approché. Par la suite, nous montrons comment RNDHH devient facilement soluble lorsque restreint à un univers de demandes particulier, basé sur des demandes qui peuvent être routées sur un arbre donné. Nous comparons également le coût des solutions optimales lorsque RND utilise HH ainsi que d'autres modèles de routage inconscients importants. Finalement, nous exploitons HH dans une étude pratique sur un nouvel univers de demandes, appelé modèle par tuyaux restreints, qui est un mélange de deux univers de demandes largement utilisés soit le modèle par tuyaux et le modèle par conduits. Nous utilisons le modèle par tuyaux restreints pour caractériser quel univers de demandes favorise un routage similaire à SP contrairement à un routage HH. Pour ce faire, nous développons un algorithme heuristique pour RNDHH et évaluons notre approche par rapport à SP à l'aide de réseaux d'opérateur ainsi que plusieurs types de demandes du modèle par tuyaux restreints, ceux-ci ayant été paramétrés par leur similitude à un modèle par tuyaux ou un modèle par conduits. Cette étude révèle les conditions à travers lesquelles le routage par multiples moyeux, c'est-à-dire HH, surpasse celui par HUB et SP.
11
Djannaty, Farhad. "Network based heuristics for the set covering problem." Thesis, Brunel University, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.320547.
Full text
12
Akgun, Ibrahim. "The K-group maximum-flow network-interdiction problem." Thesis, Monterey, California. Naval Postgraduate School, 2000. http://hdl.handle.net/10945/32947.
Full textAbstract:
We study the K-group network-interdiction problem (KNIP) in which a "network user" attempts to maximize flow among K >/= 3 "node groups", while an "interdictor" interdicts (destroys) network arcs, using limited interdiction resources, to minimize this maximum flow. We develop two models to solve or approximately solve KNIP. The multi-partition network-interdiction model (MPNIM) is an approximating model. It partitions the node set N into K different subsets, each containing one prespecified node group, and interdicts arcs using limited resources so that the total capacity of uninterdicted arcs crossing between subsets is minimized. The multi-commodity network-interdiction model (MCNIM) explicitly minimizes the maximum amount of flow that can potentially be moved among node groups using K single-commodity flow models connected by joint capacity constraints. It is a min-max model but is converted into an equivalent integer program MCNIM-IP. Both MPNIM and MCNIM-IP are tested using four artificially constructed networks with up to 126 nodes, 333 arcs, K = 5, and 20 interdictions allowed. Using a 333 MHz Pentium II personal computer, maximum solution times are 563.1 seconds for MPNIM but six of 16 MCNIM-IP problems cannot be solved in under 3,600 seconds.
13
Dahan, Mathieu. "Network security and min-cost max-flow problem." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/104555.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2016.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 92-93).
Network optimization has widely been studied in the literature for a variety of design and operational problems. This has resulted in the development of computational algorithms for the study of classical operations research problems such as the maximum flow problem, the shortest path problem, and the network interdiction problem. However, in environments where network components are subject to adversarial failures, the network operator needs to strategically allocate at least some of her resources (e.g., link capacities, network flows, etc.) while accounting for the presence of a strategic adversary. This motivates the study of network security games. This thesis considers a class of network security games on flow networks, and focuses on utilizing well-known results in network optimization toward the characterization of Nash equilibria of this class of games. Specifically, we consider a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. Linear programming duality and the Max-Flow Min-Cut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. Using graph theoretic arguments, we give a characterization of the support of the equilibrium strategies. Finally, we study the conditions under which these results extend to a revised version of the game where both players face budget constraints. Thus, our contribution can be viewed as a generalization of the classical minimum cost maximum flow problem and the minimum cut problem to adversarial environments.
by Mathieu Dahan.
S.M.
14
Haiba, Mohamed Salem. "A study and implementation of the network flow problem and edge integrity of networks." Virtual Press, 1991. http://liblink.bsu.edu/uhtbin/catkey/834644.
Full textAbstract:
Fundamental problems in graph theory are of four types existence, construction, enumeration and optimization problems. Optimization problems lie at the interface between computer science and the field of operations research and are of primary importance in decision-making. In this thesis, two optimization problems are studied: the edge-integrity of networks and the network flow problem. An implementation of the corresponding algorithms is also realized.The edge integrity of a communication network provides a way to assess the vulnerability of the network to disruption through the destruction or failure of some of its links. While the computation of the edge-integrity of graphs in general has been proven to be NPcomplete, a recently published paper was devoted to a good algorithm using a technique of edge separation sequence for computing the edge integrity of trees. The main results of this paper will be presented and an implementation of this algorithm is achieved.The network flow problem models a distribution system in which commodities are flowing through an interconnected network. The goal is to find a maximum feasible flow and its value, given the capacity constraints for each edge. The three majors algorithms for this problem (Ford -Fulkerso n, Edmonds-Karp method, MPKM algorithm) are discussed, their complexities compared and an implementation of the Ford-Fulkerson and the MPKM algorithms is presented.Department of Computer Science
15
Colajanni, Gabriella. "Constrained Optimization Problems in Network Models." Doctoral thesis, Università di Catania, 2019. http://hdl.handle.net/10761/4105.
Full textAbstract:
Operations Research is the field of mathematics that deals with solving various application problems. Constrained optimization problems are one of the most important and useful fields of mathematics, particularly in Operations Research.
In this thesis, we focus our attention on some mathematical models that are decision problems and which are all based on networks and applied to different real situations.
We analyze different thematic areas such as Cloud Computing, Financial Market, Business Management and Cybersecurity and for each of them we formulate the associated linear or nonlinear constrained problems which allows us to solve the decision problems related to the specific applications.
The purpose of one of our mathematical models, in this thesis, is to represent a cloud environment. This mathematical model could allows us to identify a rational strategy for reaching a final goal, which is to maximize the Iaas provider's profit. We get a mixed-Integer nonlinear programming problem, which can be solved through the proposed computational algorithm. A second step is the linearization of the problem. The effectiveness of the model and of the algorithm is tested, by comparing the final data with the results obtained by solving the linearized problem through an existing software.
Another topic we have dealt with in depth in this thesis is the financial market. We studied some optimization models based on networks which allow us to formulate two new multi-period portfolio selection problems as Markowitz mean-variance optimization problems with intermediaries, and therefore with transaction costs, the addition of capital gains tax, but also with short selling and transfer of securities.
We proposed two constrained Integer nonlinear programming problems with which it is possible to establish if and when it is suitable to buy and to sell financial securities, not only while maximizing the profits, but also while minimizing the risk (through the use of a weight). We applied the Lagrange theory and analyzed the variational inequality studying an optimization model for business management and cybersecurity investments.
16
Bouras, Ikram. "Fixed charge network design problem with user-optimal flows." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS136.
Full textAbstract:
Cette thèse s'adresse à la classe des problèmes de conception de réseaux bi-niveaux. Nous nous sommes intéressés à l'étude des applications des différents domaines et au développement d'algorithmes exacts pour la résolution des problème de réseaux bi-niveau correspondants. En particulier, nous avons étudié le problème de conception de réseau bi-niveau dans lequel le ``leader" sélectionne une partie du réseau à activer, puis, dans le deuxième niveau, la solution doit être optimale pour un problème de flot dans le sous-réseau sélectionné. Dans cette thèse, trois applications de ce problème sont étudiées : le transport de matières dangereuses, les réseaux de télécommunication et les réseaux sociaux. Le problème de deuxième niveau dans la première et la dernière application est un problème de plus court chemin alors qu'un flot de coûts minimum est requis dans la deuxième application.Le premier problème étudié est le problème de conception de réseau avec coût fixe avec contraintes de plus court chemin. Le problème est modélisé comme un programme bi-niveaux qui peut être appliqué dans le transport des matières dangereuses. Pour ce problème, nous proposons deux nouvelles formulations de programmation en nombres entiers (PLNE) inspirées par des inégalités de chemin et de cycle. Nous incorporons ces formulations dans des algorithmes de branch-and-cut et de plans coupants. Des tests numériques sont effectués sur des instances réelles et sur un ensembles d'instances aléatoires qui sont générées avec différents critères pour examiner la difficulté de ces instances. Les résultats montrent que les algorithmes de plan coupants proposés peuvent résoudre jusqu’à 19% d’instances de plus que les formulations compactes.Le deuxième problème étudié concerne la gestion de la consommation d'énergie dans les réseaux de télécommunication en utilisant un protocole de routage multi-chemins pour minimiser la capacité des liens utilisée. Nous proposons un modèle d'optimisation bi-niveaux dans lequel le premier niveau représente la fonction de gestion de l'énergie et le deuxième est un protocole de routage multi-chemins. Ensuite, le problème est reformulé par des formulations PLNE en remplaçant le problème du deuxième niveau par ses conditions d'optimalité. Ces formulations sont utilisées pour résoudre le problème avec les algorithmes classiques de plans coupants et de branch-and-cut. Les expérimentations sont effectuées sur des instances réelles afin de comparer les algorithmes proposés et d'évaluer l'efficacité de notre modèle par rapport aux modèles existants à un seul chemin et de multi-objectifs.Enfin, nous étudions le problème de la maximisation d’influence dans les réseaux sociaux signés. A notre connaissance, c'est la première fois que ce problème est considéré comme un problème de programmation à deux niveaux. Nous reformulons le problème en modèles PLNE à un niveau en utilisant trois différentes conditions d'optimalité du problème de plus court chemin apparaissant dans le deuxième niveau. Ces formulations sont renforcées en ajoutant un ensemble d'inégalités valides. Des tests numériques sont effectués sur des instances aléatoires pour comparer les différentes formulations proposées. Enfin, des solutions optimales en temps polynomial sont proposées pour des cas particuliers des graphesThis thesis addresses a class of bi-level network design problems. We are interested in investigating applications from different domains and in developing exact algorithms to solve the corresponding bi-level network problem. In particular, we study a bi-level network design problem where the leader selects a part of the network to be activated, then, in the second level, the solution must be optimal for a network flow problem in the selected sub-network. In this thesis, three applications of this problem are studied: hazmats transportation, telecommunication, and social networks analysis. The second level problem in the first and the last applications is a shortest path problem while a minimum cost flow is required in the second application.The first studied problem is the fixed charge network design problem with shortest path constraints, which is modeled as a bi-level program and can be applied in hazardous transportation. For this problem, we propose two new binary integer programming (BILP) formulations inspired by path and cycle inequalities. We incorporate these formulations in a branch-and-cut algorithm and another cutting-plane based method. Numerical experiments are performed on real instances, and random data sets generated with different criteria to examine the difficulty of the instances. The results show that the proposed cutting plane algorithms can solve up to 19% more instances than the compact formulations.The second studied problem is the energy-aware traffic engineering while using multi-path routing to minimize link capacity utilization in ISP backbone networks. We propose a bi-level optimization model where the upper level represents the energy management function, and the lower one refers to the deployed multi-path routing protocol. Then, we reformulate it as a one-level MILP replacing the second level problem by different sets of flow optimality conditions. We further use these formulations to solve the problem with classical cutting plane and branch-and-cut algorithms. The computational experiments are performed on real instances to compare the proposed algorithms and to evaluate the efficiency of our model against existing single-path and multi-objective models.Finally, we study the problem of maximization influence in signed social networks. To the best of our knowledge, it is the first time that this problem is modeled as a bi-level programming problem. We reformulate the problem as one-level MILP models using three different optimality conditions of the shortest path problem appearing in the second level. These formulations are strengthened by adding a set of valid inequalities. Computational experiments are performed using random instances to compare the different proposed formulations. Finally, explicit solutions and bounds are proposed for particular cases of instances
17
Barnhart, Cynthia. "A network-based primal-dual solution methodology for the multi-commodity network flow problem." Thesis, Massachusetts Institute of Technology, 1988. http://hdl.handle.net/1721.1/14614.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Civil Engineering, 1988.Includes bibliographical references.
Work sponsored by North American Van Lines and the Center for Transportation Studies at M.I.T.
by Cynthia Barnhart.
Ph.D.
18
Rasmusson, Lars. "Network capacity sharing with QoS as a financial derivative pricing problem : algorithms and network." Doctoral thesis, SICS, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:ri:diva-22556.
Full textAbstract:
A design of an automatic network capacity markets, often referred to as a bandwidth market, is presented. Three topics are investigated. First, a network model is proposed. The proposed model is based upon a trisection of the participant roles into network users, network owners, and market middlemen. The network capacity is defined in a way that allows it to be traded, and to have a well defined price. The network devices are modeled as core nodes, access nodes, and border nodes. Requirements on these are given. It is shown how their functionalities can be implemented in a network. Second, a simulated capacity market is presented, and a statistical method for estimating the price dynamics in the market is proposed. A method for pricing network services based on shared capacity is proposed, in which the price of a service is equivalent to that of a financial derivative contract on a number of simple capacity shares.Third, protocols for the interaction between the participants are proposed. The market participants need to commit to contracts with an auditable protocol with a small overhead. The proposed protocol is based on a public key infrastructure and on known protocols for multi party contract signing. The proposed model allows network capacity to be traded in a manner that utilizes the network efficiently. A new feature of this market model, compared to other network capacity markets, is that the prices are not controlled by the network owners. It is the end-users who, by middlemen, trade capacity among each other. Therefore, financial, rather than control theoretic, methods are used for the pricing of capacity.
19
Tjandra, Stevanus Adrianto. "Dynamic network optimization with application to the evacuation problem." [S.l.] : [s.n.], 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=967999448.
Full text
20
Bingol, Levent. "A Lagrangian Heuristic for solving a network interdiction problem." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2001. http://handle.dtic.mil/100.2/ADA401595.
Full textAbstract:
Thesis (M.S. in Operations Research) Naval Postgraduate School, December 2001.Thesis Advisor(s): Wood, R. Kevin. "December 2001." Includes bibliographical references (p. 35-36). Also Available online.
21
Poetranto, Groß Dwi Retnani. "Network flow and location (FlowLoc) : the source location problem /." München : Verl. Dr. Hut, 2009. http://bvbr.bib-bvb.de:8991/F?func=service&doc_library=BVB01&doc_number=017179775&line_number=0001&func_code=DB_RECORDS&service_type=MEDIA.
Full text
22
Wu, Yanghui. "Problem dependent metaheuristic performance in Bayesian network structure learning." Thesis, Robert Gordon University, 2012. http://hdl.handle.net/10059/790.
Full textAbstract:
Bayesian network (BN) structure learning from data has been an active research area in the machine learning field in recent decades. Much of the research has considered BN structure learning as an optimization problem. However, the finding of optimal BN from data is NP-hard. This fact has driven the use of heuristic algorithms for solving this kind of problem. Amajor recent focus in BN structure learning is on search and score algorithms. In these algorithms, a scoring function is introduced and a heuristic search algorithm is used to evaluate each network with respect to the training data. The optimal network is produced according to the best score evaluated. This thesis investigates a range of search and score algorithms to understand the relationship between technique performance and structure features of the problems. The main contributions of this thesis include (a) Two novel Ant Colony Optimization based search and score algorithms for BN structure learning; (b) Node juxtaposition distribution for studying the relationship between the best node ordering and the optimal BN structure; (c) Fitness landscape analysis for investigating the di erent performances of both chain score function and the CH score function; (d) A classifier method is constructed by utilizing receiver operating characteristic curve with the results on fitness landscape analysis; and finally (e) a selective o -line hyperheuristic algorithm is built for unseen BN structure learning with search and score algorithms. In this thesis, we also construct a new algorithm for producing BN benchmark structures and apply our novel approaches to a range of benchmark problems and real world problem.
23
Bossert, John M. (John Meyer) 1973. "Modeling and solving variations of the Network Loading Problem." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/29263.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002.Includes bibliographical references (p. 146-149).
We examine three variations of a class of network design problems known as Network Loading Problems (NLP). For'each variation we develop a tailored branch and bound solution approach equipped with heuristic procedures and problem specific cutting planes. The first variation formulates a logistics problem known as Pup Matching that involves matching semitrailers to cabs that are able to tow one or two of the trailers simultaneously. Theoretically, we show that four heuristics each yield a 2-approximation and we specify facet defining conditions for a cut family that we refer to as odd flow inequalities. Computationally, we solved to optimality 67 percent of test instances randomly generated from realistic data. The average minimum heuristic error among solved instances was 1.3 percent. Cutting planes reduced the average relative difference between upper and lower bounds prior to branching from 18.8 percent to 6.4 percent. The second problem variation concerns three NLP generalizations (segregated, nested, and general compartments) that we refer to collectively as Compartmentalized Network Loading (CNLP). We model these problems, extend to the case of segregated compartments convex hull results of Magnanti, Mirchandani, and Vachani on single arc and three node problems, and employ the routine of Atamtiirk and Rajan to efficiently separate certain (residual capacity) inequalities for all three CNLP models.
(cont.) On randomly generated instances, we conducted four series of tests designed to isolate the computational impact of problem parameters including graph density and model type. The third variation, Single Commodity Network Loading (SCNLP), requires loading discrete capacity units sufficient to satisfy the demand for standard network flow (multiple source, multiple destination problem). We cast the limiting case of large capacity within the constrained forest framework of Goemans and Williamson, characterize the optimal solution to the single cut special case, and describe cutset, residual capacity, and three partition inequalities for this variation. We solved five randomly generated 15 node SCNLP instances in an average of 19.1 CPU seconds, but only three of five similarly defined NLP instances.
by John M. Bossert.
Ph.D.
24
Moura, Leonardo Fernando dos Santos. "Branch & price for the virtual network embedding problem." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2015. http://hdl.handle.net/10183/115213.
Full textAbstract:
Virtualização permite o compartilhamento de uma rede física entre uma ou mais redes virtuais. O Problema de Mapeamento de Redes Virtuais é um dos principais desafios na virtualização de redes. Esse problema consiste em mapear uma rede virtual em uma rede física, respeitando restrições de capacidade. O presente trabalho mostra que encontrar uma solução factível para esse problema é NP-Difícil. Mesmo assim, muitas instâncias podem ser pode ser resolvidas na prática através da exploração de sua estrutura. Nós apresentamos um algoritmo de Branch & Price aplicado a instâncias de diferentes topologias e tamanhos. Os experimentos realizados sugerem que o algoritmo proposto é superior ao modelo de programação linear resolvido com CPLEX.Virtualization allows one or more virtual networks to share physical infrastructures. The Virtual Network Embedding problem (VNEP) is one of the main challenges in the virtualization of physical networks. This problem consists in mapping a virtual network into a physical network while respecting capacity constraints. This work shows that finding a feasible solution for this problem is NP-Hard. However, many instances can be solved up to optimality in practice by exploiting the problem structure. We present a Branch & Price algorithm applied to instances of different topologies and sizes. The experimental results suggest that the proposed algorithm is superior to the Integer Linear Programming model solved by CPLEX.
25
Poetranto, Gross Dwi Retnani. "Network flow and location (FlowLoc) the source location problem." München Verl. Dr. Hut, 2008. http://d-nb.info/992662664/04.
Full text
26
Shim, Sangho. "Large scale group network optimization." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/31737.
Full textAbstract:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010.Committee Chair: Ellis L. Johnson; Committee Member: Brady Hunsaker; Committee Member: George Nemhauser; Committee Member: Jozef Siran; Committee Member: Shabbir Ahmed; Committee Member: William Cook. Part of the SMARTech Electronic Thesis and Dissertation Collection.
27
Grigoleit, Mark Ted. "Optimisation of large scale network problems." Thesis, Curtin University, 2008. http://hdl.handle.net/20.500.11937/1405.
Full textAbstract:
The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of Constraint Programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node.We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic for filtering along the meridian provide an aggressive method for finding near-optimal solutions in a short time. Two network problems are studied in this work. The first is a Submarine Transit Path problem in which the transit field contains four sonar detectors at known locations, each with the same detection profile. The side constraint is the total transit time, with the submarine capable of 2 speeds. For the single-speed case, the initial LR duality gap may be as high as 30%. The first hybrid method uses a single centre meridian to constrain the network based on the unused time resource, and is able to produce solutions that are generally within 1% of optimal and always below 3%. Using the computation time for the initial Lagrange Relaxation as a baseline, the average computation time for the first hybrid method is about 30% to 50% higher, and the worst case CPU times are 2 to 4 times higher. The second problem is a random valued network from the literature. Edge costs, times, and lengths are uniform, randomly generated integers in a given range. Since the values given in the literature problems do not yield problems with a high duality gap, the values are varied and from a population of approximately 100,000 problems only the worst 200 from each set are chosen for study. These problems have an initial LR duality gap as high as 40%. A second hybrid method is developed, using values for the unused time resource and the lower bound values computed by Dijkstra’s algorithm as part of the LR method. The computed values are then used to position multiple constraining meridians in order to allow LR to find better solutions.This second hybrid method is able to produce solutions that are generally within 0.1% of optimal, with computation times that are on average 2 times the initial Lagrange Relaxation time, and in the worst case only about 5 times higher. The best method for solving the Constrained Shortest Path Problem reported in the literature thus far is the LRE-A method of Carlyle et al. (2007), which uses Lagrange Relaxation for preprocessing followed by a bounded search using aggregate constraints. We replace Lagrange Relaxation with the second hybrid method and show that optimal solutions are produced for both network problems with computation times that are between one and two orders of magnitude faster than LRE-A. In addition, these hybrid methods combined with the bounded search are up to 2 orders of magnitude faster than the commercial CPlex package using a straightforward MILP formulation of the problem. Finally, the second hybrid method is used as a preprocessing step on both network problems, prior to running CPlex. This preprocessing reduces the network size sufficiently to allow CPlex to solve all cases to optimality up to 3 orders of magnitude faster than without this preprocessing, and up to an order of magnitude faster than using Lagrange Relaxation for preprocessing. Chapter 1 provides a review of the thesis and some terminology used. Chapter 2 reviews previous approaches to the CSPP, in particular the two current best methods. Chapter 3 applies Lagrange Relaxation to the Submarine Transit Path problem with 2 speeds, to provide a baseline for comparison. The problem is reduced to a single speed, which demonstrates the large duality gap problem possible with Lagrange Relaxation, and the first hybrid method is introduced.Chapter 4 examines a grid network problem using randomly generated edge costs and weights, and introduces the second hybrid method. Chapter 5 then applies the second hybrid method to both network problems as a preprocessing step, using both CPlex and a bounded search method from the literature to solve to optimality. The conclusion of this thesis and directions for future work are discussed in Chapter 6.
28
Grigoleit, Mark Ted. "Optimisation of large scale network problems." Curtin University of Technology, Department of Mathematics and Statistics, 2008. http://espace.library.curtin.edu.au:80/R/?func=dbin-jump-full&object_id=115092.
Full textAbstract:
The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of Constraint Programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node.We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic for filtering along the meridian provide an aggressive method for finding near-optimal solutions in a short time. Two network problems are studied in this work. The first is a Submarine Transit Path problem in which the transit field contains four sonar detectors at known locations, each with the same detection profile. The side constraint is the total transit time, with the submarine capable of 2 speeds. For the single-speed case, the initial LR duality gap may be as high as 30%. The first hybrid method uses a single centre meridian to constrain the network based on the unused time resource, and is able to produce solutions that are generally within 1% of optimal and always below 3%. Using the computation time for the initial Lagrange Relaxation as a baseline, the average computation time for the first hybrid method is about 30% to 50% higher, and the worst case CPU times are 2 to 4 times higher. The second problem is a random valued network from the literature. Edge costs, times, and lengths are uniform, randomly generated integers in a given range. Since the values given in the literature problems do not yield problems with a high duality gap, the values are varied and from a population of approximately 100,000 problems only the worst 200 from each set are chosen for study. These problems have an initial LR duality gap as high as 40%. A second hybrid method is developed, using values for the unused time resource and the lower bound values computed by Dijkstra’s algorithm as part of the LR method. The computed values are then used to position multiple constraining meridians in order to allow LR to find better solutions.
This second hybrid method is able to produce solutions that are generally within 0.1% of optimal, with computation times that are on average 2 times the initial Lagrange Relaxation time, and in the worst case only about 5 times higher. The best method for solving the Constrained Shortest Path Problem reported in the literature thus far is the LRE-A method of Carlyle et al. (2007), which uses Lagrange Relaxation for preprocessing followed by a bounded search using aggregate constraints. We replace Lagrange Relaxation with the second hybrid method and show that optimal solutions are produced for both network problems with computation times that are between one and two orders of magnitude faster than LRE-A. In addition, these hybrid methods combined with the bounded search are up to 2 orders of magnitude faster than the commercial CPlex package using a straightforward MILP formulation of the problem. Finally, the second hybrid method is used as a preprocessing step on both network problems, prior to running CPlex. This preprocessing reduces the network size sufficiently to allow CPlex to solve all cases to optimality up to 3 orders of magnitude faster than without this preprocessing, and up to an order of magnitude faster than using Lagrange Relaxation for preprocessing. Chapter 1 provides a review of the thesis and some terminology used. Chapter 2 reviews previous approaches to the CSPP, in particular the two current best methods. Chapter 3 applies Lagrange Relaxation to the Submarine Transit Path problem with 2 speeds, to provide a baseline for comparison. The problem is reduced to a single speed, which demonstrates the large duality gap problem possible with Lagrange Relaxation, and the first hybrid method is introduced.
Chapter 4 examines a grid network problem using randomly generated edge costs and weights, and introduces the second hybrid method. Chapter 5 then applies the second hybrid method to both network problems as a preprocessing step, using both CPlex and a bounded search method from the literature to solve to optimality. The conclusion of this thesis and directions for future work are discussed in Chapter 6.
29
Dai, Hong. "Network approach to impedance computerized tomography." Ohio : Ohio University, 1985. http://www.ohiolink.edu/etd/view.cgi?ohiou1183994407.
Full text
30
Lam, Yan-yan, and 林欣欣. "Algorithms for the minimum cost flow problem." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2004. http://hub.hku.hk/bib/B30246052.
Full text
31
Abrar, Mirza Kashif, and Imran Pervaiz. "Reliability and Load Handling Problem in Internet Service Provider’s Network." Thesis, Halmstad University, School of Information Science, Computer and Electrical Engineering (IDE), 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-4228.
Full textAbstract:
This thesis puts forward a new solution to provide the reliable network to the Internet Service Provider (ISP). This study mainly focuses on the ISPs network to provide reliability and the load balancing. It offers a guide line for the best reliable solution to the ISPs, individual organizations or other types of service providers which are engaged in providing reliable communications to their subscribers. These reliable services may be real time communications which include weather forecasts, tracking systems, online Internet protocol TV (IPTV) programs and many other ISPs services which are totally depend on the reliable network.
With the appearance and expansion of Internet subscribers all over the world, ISPs services are becoming more popular. The rapid increase of connection-demand and highly traffic network is the main reason behind the need to scale reliable network. To offer better solutions, a new theoretical and practical approach should be considered that can cover the reliable network.
The suggested network structure monitors the links, spreads the network traffic with multiple devices and takes a backup (redundant) link automatically when changes occur in the network topology. In order to support the redundancy, load balancing and reduce the failover time, the hot standby routing protocol (HSRP) is implemented on the suggested network. As we have analyzed that in any network, scalability bringing to raised the network traffic broadcast issue. Broadcast storms can be prevented by setting threshold values of traffic-filters. The threshold level helps to control broadcast traffic in networks.
With regard to suggested solutions, it is necessary to observe the limitations and advantages of the recommended reliable network structure. Therefore, this research will include the advantages and limitations of the techniques used to offer ISP services such as scalability, security and IPv6.
32
Wismath, Stephen Kenneth. "Bar-representable visibility graphs and a related network flow problem." Thesis, University of British Columbia, 1989. http://hdl.handle.net/2429/29320.
Full textAbstract:
A bar layout is a set of vertically oriented non-intersecting line segments in the plane called bars. The visibility graph associated with a layout is defined as the graph whose vertices correspond to the bars and whose edges represent the horizontal visibilities between pairs of bars.
This dissertation is concerned with the characterization of bar-representable graphs: those graphs which are the visibility graphs of some bar layout. A polynomial time algorithm for determining if a given graph is bar-representable, and the subsequent construction of an associated layout are provided. Weighted and directed versions of the problem are also formulated and solved; in particular, polynomial time algorithms for the layout of such graphs are developed.
The Planar Full Flow problem is to determine a plane embedding and an (acyclic) orientation of an undirected planar network that admits a feasible flow, that uses all arcs (except those incident upon the source or sink) to full capacity and maintains planarity. The connection of this flow problem to bar-representable graphs is exploited to solve the weighted case of the latter. As evidence that both the acyclicity and planarity constraints are necessary to obtain a polynomial algorithm for this problem, two natural variants of the Full Flow problem are shown to be strongly NP-Complete.Science, Faculty of
Computer Science, Department of
Graduate
33
Ceylan, Halim. "A genetic algorithm approach to the equilibrium network design problem." Thesis, University of Newcastle Upon Tyne, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.391956.
Full text
34
ALOISE, DANIEL. "HEURISTICS FOR THE NETWORK DESIGN PROBLEM WITH DISCRETE COST FUNCTIONS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2005. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6665@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIORProblemas de multifluxos surgem como modelos básicos no contexto de várias aplicações de fluxos em redes, tais como redes de telecomunicações, redes de transporte e logística. Em tais aplicações, os fluxos que atravessam a rede compartilham simultaneamente os mesmos recursos disponíveis e são definidos por suas próprias restrições. A cada uma das arestas ligando os pontos da rede está associado um custo, fixo ou proporcional à sua utilização. Este trabalho trata problemas de projeto de redes multifluxos, em que os custos estão associados às capacidades instaladas nas arestas. Particularmente, será estudado o caso em que a função de custo nas arestas possui o comportamento de uma função escada crescente e descontínua, para o qual métodos exatos de resolução são ineficientes. Métodos heurísticos são propostos para a resolução aproximada do problema e sintetizados em um algoritmo de multi-partida com memória adaptativa. Um mecanismo de intensificação, conhecido na literatura como construção de vocabulário, é também explorado e aplicado. Finalmente, experimentos computacionais são realizados e o método de resolução proposto é analisado quanto aos seus resultados e os resultados obtidos pelo método de resolução proposto são analisados. O método obtém as melhores soluções conhecidas para algumas instâncias da literatura.
Multicommodity flow problems arise widely as basic models in the context of network flows applications such as telecommunication networks, transportation problems, and logistic. In these applicatons, the flows that cross the networks share the same avaiable resources simultaneously and are defined by their own constraints. Each edge connecting two nodes in the network has an associated cost that is either fixed or proportional to its use. This work focuses on a network design problem in which the cost are associated with the capacities installed in the edges. Particularly, the network design problem studied has discrete and step increasing cost functions on the edges, for which exact methods are inefficient. Heuristics are proposed for the approximate memory algorithm. An intensification mechanism, known in the literature as vocabulary building, is also explored and applied. Finally, computational experiments are performed and the results obtained with the proposed solution method are evaluated. The method obtains the best known solutions for some instances in the literature.
35
Erken, Ozgur. "A branch-and-bound algorithm for the network diversion problem." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2002. http://library.nps.navy.mil/uhtbin/hyperion-image/02Dec%5FErken.pdf.
Full textAbstract:
Thesis (M.S. in Operations Research)--Naval Postgraduate School, December 2002.Thesis advisor(s): R. Kevin Wood, Matthew Carlyle. Includes bibliographical references (p. 35). Also available online.
36
Sadoghi, Amirhossein [Verfasser]. "Essays on Financial Network and Optimal Liquidation Problem / Amirhossein Sadoghi." Frankfurt am Main : Frankfurt School of Finance & Management gGmbH, 2019. http://d-nb.info/1214331025/34.
Full text
37
SENG, Kruy. "Cost-sensitive deep neural network ensemble for class imbalance problem." Digital Commons @ Lingnan University, 2018. https://commons.ln.edu.hk/otd/32.
Full textAbstract:
In data mining, classification is a task to build a model which classifies data into a given set of categories. Most classification algorithms assume the class distribution of data to be roughly balanced. In real-life applications such as direct marketing, fraud detection and churn prediction, class imbalance problem usually occurs. Class imbalance problem is referred to the issue that the number of examples belonging to a class is significantly greater than those of the others. When training a standard classifier with class imbalance data, the classifier is usually biased toward majority class. However, minority class is the class of interest and more significant than the majority class. In the literature, existing methods such as data-level, algorithmic-level and cost-sensitive learning have been proposed to address this problem. The experiments discussed in these studies were usually conducted on relatively small data sets or even on artificial data. The performance of the methods on modern real-life data sets, which are more complicated, is unclear. In this research, we study the background and some of the state-of-the-art approaches which handle class imbalance problem. We also propose two costsensitive methods to address class imbalance problem, namely Cost-Sensitive Deep Neural Network (CSDNN) and Cost-Sensitive Deep Neural Network Ensemble (CSDE). CSDNN is a deep neural network based on Stacked Denoising Autoencoders (SDAE). We propose CSDNN by incorporating cost information of majority and minority class into the cost function of SDAE to make it costsensitive. Another proposed method, CSDE, is an ensemble learning version of CSDNN which is proposed to improve the generalization performance on class imbalance problem. In the first step, a deep neural network based on SDAE is created for layer-wise feature extraction. Next, we perform Bagging’s resampling procedure with undersampling to split training data into a number of bootstrap samples. In the third step, we apply a layer-wise feature extraction method to extract new feature samples from each of the hidden layer(s) of the SDAE. Lastly, the ensemble learning is performed by using each of the new feature samples to train a CSDNN classifier with random cost vector. Experiments are conducted to compare the proposed methods with the existing methods. We examine their performance on real-life data sets in business domains. The results show that the proposed methods obtain promising results in handling class imbalance problem and also outperform all the other compared methods. There are three major contributions to this work. First, we proposed CSDNN method in which misclassification costs are considered in training process. Second, we incorporate random undersampling with layer-wise feature extraction to perform ensemble learning. Third, this is the first work that conducts experiments on class imbalance problem using large real-life data sets in different business domains ranging from direct marketing, churn prediction, credit scoring, fraud detection to fake review detection.
38
Nahabedian, Aaron Joseph. "A Primal-Dual Approximation Algorithm for the Concurrent Flow Problem." Digital WPI, 2010. https://digitalcommons.wpi.edu/etd-theses/474.
Full textAbstract:
The multicommodity flow problem involves shipping multiple commodities simultaneously through a network so that the total flow over each edge does not exceed the capacity of that edge. The concurrent flow problem also associates with each commodity a demand, and involves finding the maximum fraction z, such that z of each commodity's demand can be feasibly shipped through the network. This problem has applications in message routing, transportation, and scheduling problems. It can be formulated as a linear programming problem, and the best known solutions take advantage of decomposition techniques for linear programming. Often, quickly finding an approximate solution is more important than finding an optimal solution. A solution is epsilon-optimal if it lies within a factor of (1+epsilon) of the optimal solution. We present a combinatorial approximation algorithm for the concurrent flow problem. This algorithm consists of finding an initial flow, and gradually rerouting this flow from more to less congested paths, until an epsilon-optimal flow is achieved. This algorithm theoretically runs much faster than linear programming based algorithms.
39
Alkhelaiwi, Ali Mani Turki. "Network partitioning techniques based on network natural properties for power system application." Thesis, Brunel University, 2002. http://bura.brunel.ac.uk/handle/2438/5065.
Full textAbstract:
In this thesis, the problem of partitioning a network into interconnected sub-networks is addressed. The goal is to achieve a partitioning which satisfies a set of specific engineering constraints, imposed in this case, by the requirements of the decomposed state-estimation (DSE) in electrical power systems. The network-partitioning problem is classified as NP-hard problem. Although many heuristic algorithms have been proposed for its solution, these often lack directness and computational simplicity. In this thesis, three new partitioning techniques are described which (i) satisfy the DSE constraints, and (ii) simplify the NP-hard problem by using the natural graph properties of a network. The first technique is based on partitioning a spanning tree optimally using the natural property of the spanning tree branches. As with existing heuristic techniques, information on the partitioning is obtained only at the end of the partitioning process. The study of the DSE constraints leads to define conditions of an ideal balanced partitioning. This enables data on the balanced partitioning to be obtained, including the numbers of boundary nodes and cut-edges. The second partitioning technique is designed to obtain these data for a given network, by finding the minimum covering set of nodes with maximum nodal degree. Further simplification is then possible if additional graph-theoretical properties are used. A new natural property entitled the 'edge state phenomenon' is defined. The edge state phenomenon may be exploited to generate new network properties. In the third partitioning technique, two of these, the 'network external closed path' and the 'open internal paths', are used to identify the balanced partitioning, and hence to partition the network. Examples of the application of all three methods to network partitioning are provided.
40
Iqbal, Muhamad Syamsu. "Performance of IEEE 802.15.4 beaconless-enabled protocol for low data rate ad hoc wireless sensor networks." Thesis, Brunel University, 2016. http://bura.brunel.ac.uk/handle/2438/12852.
Full textAbstract:
This thesis focuses on the enhancement of the IEEE 802.15.4 beaconless-enabled MAC protocol as a solution to overcome the network bottleneck, less flexible nodes, and more energy waste at the centralised wireless sensor networks (WSN). These problems are triggered by mechanism of choosing a centralised WSN coordinator to start communication and manage the resources. Unlike IEEE 802.11 standard, the IEEE 802.15.4 MAC protocol does not include method to overcome hidden nodes problem. Moreover, understanding the behaviour and performance of a large-scale WSN is a very challenging task. A comparative study is conducted to investigate the performance of the proposed ad hoc WSN both over the low data rate IEEE 802.15.4 and the high data rate IEEE 802.11 standards. Simulation results show that, in small-scale networks, ad hoc WSN over 802.15.4 outperforms the WSN where it improves 4-key performance indicators such as throughput, PDR, packet loss, and energy consumption by up to 22.4%, 17.1%, 34.1%, and 43.2%, respectively. Nevertheless, WSN achieves less end-to-end delay; in this study, it introduces by up to 2.0 ms less delay than that of ad hoc WSN. Furthermore, the ad hoc wireless sensor networks work well both over IEEE 802.15.4 and IEEE 802.11 protocols in small-scale networks with low traffic loads. The performance of IEEE 802.15.4 declines for the higher payload size since this standard is dedicated to low rate wireless personal access networks. A deep performance investigation of the IEEE 802.15.4 beaconless-enabled wireless sensor network (BeWSN) in hidden nodes environment has been conducted and followed by an investigation of network overhead on ad hoc networks over IEEE 802.11 protocol. The result of investigation evinces that the performance of beaconless-enabled ad hoc wireless sensor networks deteriorates as indicated by the degradation of throughput and packet reception by up to 72.66 kbps and 35.2%, respectively. In relation to end-to-end delay, however, there is no significant performance deviation caused by hidden nodes appearance. On the other hand, preventing hidden node effect by implementing RTS/CTS mechanism introduces significant overhead on the network that applies low packet size. Therefore, this handshaking method is not suitable for low rate communications protocol such as IEEE 802.15.4 standard. An evaluation study of a 101-node large-scale beaconless-enabled wireless sensor networks over IEEE 802.15.4 protocol has been carried out after the nodes deployment model was arranged. From the experiment, when the number of connection densely increases, then the probability of packet delivery decreases by up to 40.5% for the low payload size and not less than of 44.5% for the upper payload size. Meanwhile, for all sizes of payload applied to the large-scale ad hoc wireless sensor network, it points out an increasing throughput whilst the network handles more connections among sensor nodes. In term of dropped packet, it confirms that a fewer data drops at smaller number of connecting nodes on the network where the protocol outperforms not less than of 34% for low payload size of 30 Bytes. The similar trend obviously happens on packet loss. In addition, the simulation results show that the smaller payload size performs better than the bigger one in term of network latency, where the payload size of 30 Bytes contributes by up to 41.7% less delay compared with the contribution of the payload size of 90 Bytes.
41
Tseng, Li-Ching, and 曾麗青. "Network Topology Display Problem." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/48736757097714084161.
Full textAbstract:
碩士國立交通大學
資訊管理研究所
82
Since networks continue to grow at a rapid pace and with greater complexity, to have an efficient network management system becomes more important than ever. The network topology display service is one of the essential services that Configuration Management provides. For most existing network management systems, this service is supported by either an X-window based drawing tool or an automatic detection and drawing procedure. When the network grows larger and becomes more complicate, user must spend a great deal of time in adjusting network devices’ ICON, so as to get a good graphic layout. How to acquire a symmetric network topology display is called the Network Topology Display Problem (NTDP). Usually, NTDP is solved by a two-step procedure. In the first step, Intra-subnetwork algorithms are developed according to the types of the subnetwork. such as Ring、Bus etc.. In the second step, the inter-subnetworks algorithm is used to adjust the relative position between subnetworks. A Heuristic method had been proposed to handle the inter-subnetworks display problem. However, this method has difficulties in solving large size problems. The purpose of this paper is to find an efficient and effectiveness inter-subnetworks algorithm. Three methods, Modified Heuristic Method、Operations Research Method, and Neural Network Methods, are proposed Computational results obtained from these four methods are analyzed with respect to their effectiveness, running speed, and complexity. From the analysis, the following conclusions can be drawn. The Modified Heuristic Method performs best when the number of subnetworks is less than 50. However, once the number of subnetworks is over 50, the Operations Research Method has the best result in both running time and effectiveness.
42
Charkhgard, Parisa. "The network maintenance problem." Thesis, 2020. http://hdl.handle.net/1959.13/1416256.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)In this thesis, we describe an optimisation problem motivated by the need to maintain infrastructure networks over time. We consider infrastructure networks in which a product is transported between distinct origin-destination pairs, and at the same time the infrastructure assets need to be maintained by resources moving in the network. In order to perform maintenance the assets have to be shut down from time to time which potentially reduces the system capacity in those time periods. The objective is to maximise the total throughput of product by aligning the maintenance activities appropriately. This problem combines flow maximisation with maintenance scheduling capturing some important aspects of the motivating practical problem: (1) the interaction between the utilisation of network assets such as nodes and arcs, and their maintenance demands; (2) the limited number of resources available to perform the maintenance; and (3) the time taken to move maintenance resources between different locations in the network. Depending on the application context, there are a number of natural ways to reflect these in a mathematical model, and this gives rise to a rich and challenging optimisation problem which we call the network maintenance problem. In this thesis, we formally introduce the problem, present a mixed integer linear programming formulation, and prove that even a simple variant of the problem with a single origin-destination pair and unrestricted resource movement is already NP-hard. Next, we study a number of variants of the problem in which the network has a special structure. More precisely, we focus almost completely on the case where the network is a path (with the exceptions of Sections 3.1 and 6.3. The problems that we study are of interest for the following reasons. Firstly, they generalise variants of well-studied problems in the literature such as the lot-sizing problem and the warehouse problem. Secondly, we believe that understanding these special cases will be useful in tackling more general variants of the network maintenance problem. In this thesis, we focus on designing efficient algorithms to solve these problem variants and identifying the ones whose optimal objective value can be computed in polynomial time. Furthermore, we study the polyhedral structure of some of these variants and present compact perfect extended formulations which can be solved in polynomial time.
43
"The multi-level network design problem." Sloan School of Management, Massachusetts Institute of Technology, 1991. http://hdl.handle.net/1721.1/2381.
Full text
44
Shu, Jia, Chung Piaw Teo, and Zuo-Jun Max Shen. "Stochastic Transportation-Inventory Network Design Problem." 2002. http://hdl.handle.net/1721.1/4018.
Full textAbstract:
In this paper, we study the stochastic transportation-inventory network design problem involving one supplier and multiple retailers. Each retailer faces some uncertain demand. Due to this uncertainty, some amount of safety stock must be maintained to achieve suitable service levels. However, risk-pooling benefits may be achieved by allowing some retailers to serve as distribution centers (and therefore inventory storage locations) for other retailers. The problem is to determine which retailers should serve as distribution centers and how to allocate the other retailers to the distribution centers. Shen et al. (2000) and Daskin et al. (2001) formulated this problem as a set-covering integer-programming model. The pricing subproblem that arises from the column generation algorithm gives rise to a new class of submodular function minimization problem. They only provided efficient algorithms for two special cases, and assort to ellipsoid method to solve the general pricing problem, which run in O(n⁷ log(n)) time, where n is the number of retailers. In this paper, we show that by exploiting the special structures of the pricing problem, we can solve it in O(n² log n) time. Our approach implicitly utilizes the fact that the set of all lines in 2-D plane has low VC-dimension. Computational results show that moderate size transportation-inventory network design problem can be solved efficiently via this approach.Singapore-MIT Alliance (SMA)
45
Casadiego, Bastidas Jose Luis. "Network Dynamics as an Inverse Problem." Doctoral thesis, 2016. http://hdl.handle.net/11858/00-1735-0000-002B-7CE4-3.
Full text
46
LI, HAN-MING, and 李漢銘. "Training neural networks with automatic network generating ability for the classification problem." Thesis, 1991. http://ndltd.ncl.edu.tw/handle/79680559920648678103.
Full text
47
Hsieh, Hui-Ching, and 謝惠菁. "The Agreement Problem in the Mobile Network." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/74016573124192508495.
Full textAbstract:
碩士朝陽科技大學
資訊管理系碩士班
92
Due to the network technology that has advanced at an astounding speed, the topology of networks is trending wireless. It is imperative for us to develop mobile commerce or related applications in this wireless network. There are a lot of properties in the wireless network that play important roles. For example, the processors in wireless network have highly mobile capability. In other words, processors can immigrate into or move away from the network at any time. Although the mobile technology has brought greater convenience to us, it is comparatively more dangerous under such wireless environment. For instance, processors have mobility and the illegal processors can intrude the network more easily and do any illegitimate behaviors. In other words, it is not only difficult to ensure its security but it is also susceptible to security flaws such as attacks by the hackers. It will also decrease the allowable number of faulty components in the system. Basically speaking, there are plenty of applications that can be used in the wireless mobile network. For example, it is common to develop the mobile agents in the wireless network. However all problems mentioned will have the mobile agents in fault. It may affect the result of other mobile agents in the middle of carrying out some assignment. Fortunately enough, the Byzantine Agreement problem can help us to solve these problems. Basically, the protocols about Byzantine Agreement (BA) problem used in static wired networks, however, the previous protocols do not perform well in a dynamically changing mobile network. In addition, the problem of mobility and security is more difficult to solve. Hence, how to solve the BA problem in unsafe and unreliable environment is eager for us to solve. In order to increase the number of allowable faulty components and ensure the security of the network, the proposed protocols RAP, BAMN and GBAIM will help us to solve the BA problem when the faulty components are transmission media only, processors only and both transmission media and processors may in fault simultaneously. These protocols uses the minimum number of rounds of message exchange to achieve an agreement and can tolerate the maximum number of allowable faulty components and will also ensure the message security and increase the fault tolerant capability of the system. Furthermore, the receiver can always identify the dormant faults if the protocol appropriately encodes a transmitted message by either the Non-Return-to-Zero code or the Manchester code before transmission. In other words, the behavior of malicious faults might be unpredictable and unidentifiable. In this thesis, we also review the BA problem to enlarge the fault tolerant capability by allowing dormant faults and malicious faults (dual failure modes) to simultaneously exist in the wireless mobile network.
48
Chen, Szu-Jung, and 陳思蓉. "Approximating the Wireless Sensor Network Scheduling Problem." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/03284455701819190238.
Full textAbstract:
碩士國立清華大學
工業工程與工程管理學系
102
A wireless sensor network (WSN) consists of one or more wireless data collectors and many autonomous sensors to monitor physical phenomena or collect environmental information. Each sensor usually uses a battery to enable its function, which limits its lifetime. In order to prolong the lifetime of WSNs, it is important to schedule the sensors to be activated in WSNs, which is called the wireless sensor network scheduling problem. The WSN scheduling problem is described as follows: Given a set of sensors, and a set of regions to be monitored, each region can be monitored by a subset of the sensors, and a sensor also can monitor more than one region. In order to prolong the lifetime of WSN, we decompose the sensors into disjoint subsets such that every subset of sensors needs to monitor all the regions, i.e. activating a subset of sensors to observe all the regions in each time slot, and the number of times slots (i.e. the number of subsets of sensors), that is, the lifetime of the WSN, is maximized. We investigate the WSN scheduling problem in two different models, and provide several polynomial time algorithms for approximating this problem. When the monitored range of each sensor is the same, i.e. the distance r, and the distance between any two regions is at least √3 r+ε, we present a 3/4 -ratio approximation algorithm to solve the WSN scheduling problem. In addition, when every monitored region is represented by a closed area, and each sensor can monitor at most three regions, we provide a 3/8 -ratio approximation algorithm to solve this model. Moreover, we also can identify critical sensors of WSNs; a sensor is called critical if the lifetime of WSNs must decrease when the sensor is broken. The identification of critical sensors can assist the reliability analysis of wireless sensor networks.
49
Yan, Hong Xu, and 顏宏旭. "A neural network approach for scheduling problem." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/51589834193749053356.
Full text
50
莊舜方. "A neural network for solving nonlinear programming problem." Thesis, 1992. http://ndltd.ncl.edu.tw/handle/75669789102323753891.
Full text