We present here models and algorithms for the construction of efficient path systems, robust to possible variations of the characteristics of the network. We propose some interpretations of these models and proceed to numerical experimentations of the related algorithms. We conclude with a discussion of the way those concepts may be applied to the design of a Public Transportation System.
Nanonetwork is defined as a mathematical model of nanosize objects with biological, physical and chemical attributes, which are interconnected within certain dynamical process. To demonstrate the potentials of this modeling approach for quantitative study of complexity at nanoscale, in this survey, we consider three kinds of nanonetworks: Genes of a yeast are connected by weighted links corresponding to their coexpression along the cell cycle; Gold nanoparticles, arranged on a substrate, are linked...
We consider a model for the control of a linear network flow system with unknown but bounded demand and polytopic bounds on controlled flows. We are interested in the problem of finding a suitable objective function that makes robust optimal the policy represented by the so-called linear saturated feedback control. We regard the problem as a suitable differential game with switching cost and study it in the framework of the viscosity solutions theory for Bellman and Isaacs equations.
We consider a model for the control of a linear network flow system with unknown but bounded demand and polytopic bounds on controlled flows. We are interested in the problem of finding a suitable objective function that makes robust optimal the policy represented by the so-called linear saturated feedback control. We regard the problem as a suitable differential game with switching cost and study it in the framework of the viscosity solutions theory for Bellman and Isaacs equations.
A co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G. (A co-biclique is the complement of a biclique.) A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.) It is showed that a minimum-cost dependent set of G can be determined in polynomial...
Is it possible to label the edges of Kₙ with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when "Hamilton cycle" is replaced by "k-factor" for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine (up to a constant...
In this paper we introduce some improvements on an approach that we described elsewhere for solving a modification of the well-known extended rapid transit network design problem. Firstly, we propose an integer programming model for selecting the stations to be constructed and the links between them, in such a way that a connected rapid transit network is obtained. Secondly, we consider a linear 0-1 programming model for determining a route of minimum length in the rapid transit network between...
In this paper we introduce some improvements on an approach that we described elsewhere for solving a modification of the well-known extended rapid transit network design problem. Firstly, we propose an integer programming model for selecting the stations to be constructed and the links between them, in such a way that a connected rapid transit network is obtained. Secondly, we consider a linear 0-1 programming model for determining a route of minimum...
Given the directed graph G1 = (N, A1) with a node origin and a penalty matrix C, the ATSP with fixed origin and precedence relationships (hereafter, ASTP-PR) consists of finding the permutation of the nodes from the set N, such that it minimizes a matrix C based function and does not violate the precedence relationships given by the set A1. In this work we present an algorithm for improving a given feasible solution to the problem, by performing a local search that uses 3- and 4-change based procedures....
The minimization of a nonlinear function with linear and nonlinear constraints and simple bounds can be performed by minimizing an augmented Lagrangian function, including only the nonlinear constraints. This procedure is particularly interesting in case that the linear constraints are flow conservation equations, as there exist efficient techniques to solve nonlinear network problems. It is then necessary to estimate their multipliers, and variable reduction techniques can be used to carry out...
A partitioning algorithm for the Euclidean matching problem in is introduced and analyzed in a probabilistic model. The algorithm uses elements from the fixed dissection algorithm of Karp and Steele (1985) and the Zig-Zag algorithm of Halton and Terada (1982) for the traveling salesman problem. The algorithm runs in expected time and approximates the optimal matching in the probabilistic sense.