A new class of cutting planes for the symmetric travelling salesman problem

A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known comb inequalities, the path inequalities and the 3-star constraints as special cases. Its relation to the clique tree inequalities is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and—under certain conditions—to define facets of the polyhedron associated with this problem.     

Applying a fuzzy relation to describe influence of flux behaviour in a printed coil

Summary Being a subject of expectedly fuzzy character, an attempt is made to apply fuzzy functions, more precisely fuzzy relations to investigate the problem of flux distortion in a printed coil.

---

Zusammenfassung Da die Vorgänge in einer gedruckten Spule sich aus einer Vielzahl schwerer erfaßbarer Einzeleinflüsse zusammensetzen, die insbesondere den Magnetfluß verzerren, lag es nahe, den Versuch zu machen, die Fuzzy Functions (die logische Algebra, gemäß [1]) darauf anzuwenden. Die Fuzzy Functions sind gedacht für das Beschreiben von Vorgängen, oder Ereignissen, die im Ansatz ein breit gefächertes (fuzzy) Verhalten, ohne scharfe Grenzen aufweisen; siehe Fig. 4.Dieser gefächerten logischen Funktion entspricht eine reguläre mathematische Kurvenschar, die meßtechnisch nachgewiesen werden muß.Im vorliegenden Falle ergab sich eine Korrekturfunktion (5), die es gestattet, die Induktivität gedruckter Spulen, in einem weiten Bereich von Abmessungen und Windungen, mit einer Genauigkeit von –2% bis +5% zu bestimmen.

     

Approximation of continuous vector functions

We study the possibility of uniform approximation of continuous mappings of metric compact sets into metric spaces. Notions of weak dimension and weak Kolmogorov width are introduced to compare approximating properties of infinite-dimensional subspaces. For classes of mappings specified by the majorant of the modulus of continuity, we present bilateral estimates of weak widths that may coincide under certain conditions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 11, pp. 1435–1448, November, 1994.     

A Niche Width Model of Optimal Specialization

Niche width theory, a part of organizational ecology, predicts whether specialist or generalist forms of organizations have higher fitness, in a continually changing environment. To this end, niche width theory uses a mathematical model borrowed from biology. In this paper, we first loosen the specialist-generalist dichotomy, so that we can predict the optimal degree of specialization. Second, we generalize the model to a larger class of environmental conditions, on the basis of the model's underlying assumptions. Third, we criticize the way the biological model is treated in sociological theory. Two of the model's dimensions seem to be confused, i.e., that of trait and environment; the predicted optimal specialization is a property of individual organizations, not of populations; and, the distinction between fine and coarse grained environments is superfluous.     

A Kantorovich-type convergence analysis for the Gauss-Newton-Method

Summary We present a (semilocal) Kantorovich-type convergence analysis for the Gauss-Newton-Method which reduces to the wellknown Newton-Kantorovich-Theorem for the Newton-Method in a natural way. Additionnally a classification of the nonlinear regression problem into adequate and not-adequate models is obtained.     

Types in a mixed language system

As a support for writing software, a comprehensive set of problem oriented languages appears preferable to any so-called universal language, as soon as static checking is sufficient to ensure type correctness of the mixed language program. We lay the basis for a mixed language system where this requirement is fulfilled. The general outline of the system is first sketched. Detailed consideration is then given to our basic constructs for establishing communication between languages, namely standard types and foreign types. Abstract types, such as defined in CLU, are finally shown to be a particular class of foreign types.     

Staircase kernels for orthogonald-polytopes

LetS be a finite union of boxes inR ^d . Forx inS, defineA _x ={yx is clearly visible fromy via staircase paths inS}, and let KerS denote the staircase kernel ofS. Then KerS={A _x x is a point of local nonconvexity ofS}. A similar result holds with clearly visible replaced by visible and points of local nonconvexity ofS replaced by boundary points ofS.Supported in part by NSF grant DMS-9207019.     

Chapter 1 Introduction: Extensions and new developments in DEA

The extensions, new developments and new interpretations for DEA covered in this paper include: (1) new measures of efficiency, (2) new models and (3) new ways of implementing established models with new results and interpretations presented that include treatments of congestion, returns-to-scale and mix and technical inefficiencies and measures of efficiency that can be used to reflect all pertinent properties. Previously used models, such as those used to identify allocative inefficiencies, are extended by means of assurance region approaches which are less demanding in their information requirements and underlying assumptions. New opportunities for research are identified in each section of this chapter. Sources of further developments and possible sources for further help are also suggested with references supplied to other papers that appear in this volume and which are summarily described in this introductory chapter.     

On the continuity of midpoint hull convex set-valued functions

Summary The concept of hull convexity (midpoint hull convexity) for set-valued functions in vector spaces is examined. This concept, introduced by A. V. Fiacco and J. Kyparisis (Journal of Optimization Theory and Applications,43 (1986), 95–126), is weaker than one of convexity (midpoint convexity).The main result is a sufficient condition for a midpoint hull convex set-valued function to be continuous. This theorem improves a result obtained by K. Nikodem (Bulletin of the Polish Academy of Sciences, Mathematics,34 (1986), 393–399).     

Topology optimization of multi-purpose structures

Whilst most of the literature on topology optimization of structures deals with so-called selfadjoint problems involving highly idealized, single-purpose structures, this paper discusses topology optimization of multi-purpose structures which concerns nonselfadjoint problems. General methods based on the so-called layout theory, application to trusses and perforated plates and computational difficulties are discussed.     

Role of information in the stochastic zero-sum differential game

In this paper, a linear-quadratic Gaussian zero-sum differential game is studied. Maneuverability is defined to measure players' strength. It is shown that a more maneuverable player would prefer a more observable information system. An example is given to show that a more controllable player might not prefer more observable measurements in the stochastic environment.The research reported in this paper was made possible through support extended to the Division of Engineering and Applied Physics, Harvard University, by the US Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-c-0648 and by the National Science Foundation under Grant No. GK31511.     

Discrete Newton methods and iterated defect corrections

Summary In this paper we present a general theory for discrete Newton methods, iterated defect corrections via neighbouring problems and deferred corrections based on asymptotic expansions of the discretization error.Dedicated to Professor Dr. J. Weisinger on the occasion of his sixty-fifth birthday     

Stability of axial motions of nonlinearly elastic loops

We establish the stability of axial motions (steady motions along the lengthwise direction) of nonlinearly elastic loops of string. A key observation here is that a linear combination of the total energy and the total circulation of the string, both of which are conserved quantities, yields an appropriate Liapunov function. From our previous work [5], we know that there are uncountably many shapes corresponding to a given axial speed. Accordingly, we establish orbitai stability (modulo this collection of relative equilibria). For a well-defined class of soft materials, there is an upper bound on the axial speed sufficient for stability; stiff materials are shown to be orbitally stable at any axial speed.     

Parallel continuation-based global optimization for molecular conformation and protein folding

This paper presents our recent work on developing parallel algorithms and software for solving the global minimization problem for molecular conformation, especially protein folding. Global minimization problems are difficult to solve when the objective functions have many local minimizers, such as the energy functions for protein folding. In our approach, to avoid directly minimizing a difficult function, a special integral transformation is introduced to transform the function into a class of gradually deformed, but smoother or easier functions. An optimization procedure is then applied to the new functions successively, to trace their solutions back to the original function. The method can be applied to a large class of nonlinear partially separable functions including energy functions for molecular conformation and protein folding. Mathematical theory for the method, as a special continuation approach to global optimization, is established. Algorithms with different solution tracing strategies are developed. Different levels of parallelism are exploited for the implementation of the algorithms on massively parallel architectures.     

Polling systems with synchronization constraints

We introduce a new service discipline, called thesynchronized gated discipline, for polling systems. It arises when there are precedence (or synchronization) constraints between the order that jobs in different qucues should be served. These constraints are described as follows: There areN stations which are fathers of (zero or more)synchronized stations (children). Jobs that arrive at synchronized stations have to be processed only after jobs that arrived prior to them at their corresponding father station have been processed. We analyze the performance of the synchronized gated discipline and obtain expressions for the first two moments and the Laplace-Stieltjes transform (LST) of the waiting times in different stations, and expressions for the moments and LST of other quantities of interest, such as cycle duration and generalized station times. We also obtain a pscudo conservation law for the synchronized gated discipline, and determine the optimal network topology that minimizes the weighted sum of the mean waiting times, as defined in the pseudo conservation law. Numerical examples are given for illustrating the dependence of the performance of the synchronized gated discipline on different parameters of the network.Supported by a Grant from the France-Israel Scientific Cooperation (in Computer Science and Engineering) between the French Ministry of Research and Technology and the Israeli Ministry of Science and Technology, Grant No. 3321190.     

Characterization of coalitionally ordered games

Summary In the sequel we will derive sufficient and necessary conditions for the existence of certain numeric representations of simple games. In § 2 the above mentioned representation is given by a so called, coalitionally ordered function, i.e. a numeric function representing the desirability of each coalition in the class of all coalitions. Simple games which possess a c.o.f are called coalitionally ordered games. Sufficient and necessary criteria are given for a simple game to be a c.o.g. Analogously weighted majority games are characterized in § 3. The criteria to be presented are linked by properties of the desirability relation of a simple game. The concept of a desirability relation was introduced by Peleg 1978.

---

Zusammenfassung Im folgenden werden wir hinreichende und notwendige Bedingungen zur Existenz von gewissen numerischen Darstellungen einfacher Spiele (simple games) herleiten. Diese oben genannte Darstellung wird in § 2 durch eine sogenannte coalitionally ordered function, gegeben, wobei wir darunter eine numerische Funktion verstehen, die die Desirability, jeder Koalition innerhalb der Klasse aller Koalitionen beschreibt. Einfache Spiele, die eine c.o.f besitzen, werden coalitionally ordered games genannt. Es werden hinreichende und notwendige Bedingungen dafür genannt, daß ein einfaches Spiel ein c.o.g ist. Analog werden gewichtete Abstimmungsspiele (weighted majority games) in § 3 charakterisiert. Die angegebenen Kriterien werden mit Eigenschaften der sogenannten desirability relation eines einfachen Spieles in Verbindung gebracht. Das Konzept einer desirability relation wurde von Peleg 1978 verwendet.

     

Computations in choice groupoids

Defining achoice as a mapping of the subsets of a setX into their respective subsets, a one-to-one (and naturally) corresponding binary operation,sequential choice, is identified under which the power set ofX is closed as achoice groupoid. A complete logical diagram is given, exhibiting all the implications between conjunctions of the seven conditions: (1) idempotence, (2) consistency, (3) absorbence, and (4) homomorphism of a choice, and (5) commutativity, (6) associativity, and (7) path-independence of the corresponding sequential choice.     

General procedures leading to correlated equilibria

Hart and Mas-Colell [2000] show that if all players play regret-matching strategies, i.e., they play with probabilities proportional to the regrets, then the empirical distribution of play converges to the set of correlated equilibria, and the regrets of every player converge to zero. Here we show that if only one player, say player i, plays with these probabilities, while the other players are not too sophisticated, then the result that player is regrets converge to zero continues to hold. The condition of not too sophisticated essentially says that the effect of one change of action of player i on the future actions of the other players decreases to zero as the horizon goes to infinity. Furthermore, we generalize all these results to a whole class of regret-based strategies introduced in Hart and Mas-Colell [2001]. In particular, these simplify the conditional smooth fictitious play of Fudenberg and Levine [1999].Received: May 2004This is a revision of the authors M.Sc. thesis, May 2000.The author thanks Professor Sergiu Hart for his help and guidance, and the Associate Editor and an anonymous referee for their comments. I am grateful to my parents and wife for everything.     

Construction of Pseudorandom Binary Sequences Using Additive Characters

In earlier papers the authors studied finite pseudorandom binary sequences, and they constructed sequences with strong pseudorandom properties. In these earlier constructions multiplicative characters were used. In this paper a new construction is presented which utilizes properties of additive characters. These new sequences can be computed fast, they are well-distributed relative to arithmetic progressions and their correlations of small order are small, but the price paid for the fast computation is that the correlations of large order can be large.     

Computing convolutions by reciprocal search

In this paper we show how certain geometric convolution operations can be computed efficiently. Here efficiently means that our algorithms have running time proportional to the input size plus the output size. Our convolution algorithms rely on new optimal solutions for certain reciprocal search problems, such as finding intersections between blue and green intervals, and overlaying convex planar subdivisions.This research was done while on leave from Cornell at DEC/SRC.