Survivable networks,linear programming relaxations and the parsimonious property

We consider the survivable network design problem — the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and thek-edge-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worst-case analyses of two heuristics for the survivable network design problem.The research of both authors was partially supported by the National Science Foundation under grant ECS-8717970 and the Leaders for manufacturing program at MIT.     

A probabilistic analysis of the set covering problem

A probabilistic analysis of the minimum cardinality set covering problem (SCP) is developed, considering a stochastic model of the (SCP), withn variables andm constraints, in which the entries of the corresponding (m, n) incidence matrix are independent Bernoulli distributed random variables, each with constant probabilityp of success. The behaviour of the optimal solution of the (SCP) is then investigated as bothm andn grow asymptotically large, assuming either an incremental model for the evolution of the matrix (for each size, the matrixA is obtained bordering a matrix of smaller size by new columns and rows) or an independent one (for each size, an entirely new set of entries forA are considered). Two functions ofm are identified, which represent a lower and an upper bound onn in order the (SCP) to be a.e. feasible and not trivial. Then, forn lying within these bounds, an asymptotic formula for the optimum value of the (SCP) is derived and shown to hold a.e.The performance of two simple randomized algorithms is then analyzed. It is shown that one of them produces a solution value whose ratio to the optimum value asymptotically approaches 1 a.e. in the incremental model, but not in the independent one, in which case the ratio is proved to be tightly bounded by 2 a.e. Thus, in order to improve the above result, a second randomized algorithm is proposed, for which it is proved that the ratio between the approximate solution value and the optimum approaches 1 a.e. also in the independent model.     

Colouring random graphs

We discuss some results concerned with the behaviour of colouring algorithms on large random graphs.     

An introduction to timetabling

A huge variety of timetabling models have been described in the OR literature; they range from the weekly timetable of a school to the scheduling of courses or exams in a university. Graphs and networks have proven to be useful in the formulation and solution of such problems. Various models will be described with an emphasis on graph theoretical models.     

Performance Analysis of Cyclical Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Measures for assessing the finite-time performance of GHC algorithms have been developed using this framework, including the expected number of iterations to visit a predetermined objective function value level. This paper analyzes how the expected number of iterations to visit a predetermined objective function value level can be estimated for cyclical simulated annealing. Cyclical simulated annealing uses a cooling schedule that cycles through a set of temperature values. Computational results with traveling salesman problem instances taken from TSPLIB show how the expected number of iterations to visit solutions with predetermined objective function levels can be estimated for cyclical simulated annealing.AMS 2000 Subject Classification 90-08 Computational Methods: Local Search, 90C59 Heuristics: Simulated Annealing     

Fast search algorithms for computational protein design

One of the main challenges in computational protein design (CPD) is the huge size of the protein sequence and conformational space that has to be computationally explored. Recently, we showed that state‐of‐the‐art combinatorial optimization technologies based on Cost Function Network (CFN) processing allow speeding up provable rigid backbone protein design methods by several orders of magnitudes. Building up on this, we improved and injected CFN technology into the well‐established CPD package Osprey to allow all Osprey CPD algorithms to benefit from associated speedups. Because Osprey fundamentally relies on the ability of to produce conformations in increasing order of energy, we defined new strategies combining CFN lower bounds, with new side‐chain positioning‐based branching scheme. Beyond the speedups obtained in the new ‐CFN combination, this novel branching scheme enables a much faster enumeration of suboptimal sequences, far beyond what is reachable without it. Together with the immediate and important speedups provided by CFN technology, these developments directly benefit to all the algorithms that previously relied on the DEE/ combination inside Osprey* and make it possible to solve larger CPD problems with provable algorithms. © 2016 Wiley Periodicals, Inc.     

Mechanical,Thermal and Morphological Behaviors of Castor Oil Based PU/PS Interpenetrating Polymer Network-Metakaolin Composites

The meta kaolin (MK) clay particulate filler with different weight ratios viz., 0, 5, 10, 20 and 30 wt% were incorporated into castable polyurethane (PU)/polystyrene (PS) (90/10) interpenetrating polymer network (IPN). The effects of MK particulate filler loading on the mechanical and thermal properties of PU/PS (90/10) IPN composites have been studied. From the tensile behavior, it was noticed that a significant improvement in tensile strength and tensile modulus as an increase in MK filler content. Thermogravimetric analysis (TGA) data reveals the marginal improvement in thermal stability after incorporation of MK filler. TGA studies of the IPN composites have been performed in order to establish the thermal stability and their mode of thermal degradation. It was found that degradation of all composites takes place in two steps. Degradation kinetic parameters were obtained for the composites using three mathematical models. Tensile fractured composite specimens were used to analyze the morphology of the composites by scanning electron microscopic (SEM) technique.     

ALAD基因多态性与血铅水平关系的Meta分析

对有关ALAD基因多态性与血铅水平关系的研究进行了meta分析。通过Medline、CBMDisc及同行收集 1 7篇文献 ,剔除重复报道或不合格文献后共有 9个独立研究纳入meta分析。结果表明 ,对低水平接触人群 (血铅 <1 0 μg/dL) ,效应尺度d的均值为 0 1 3 8(P =0 0 46) ;对高水平接触人群 (血铅 >2 0 μg/dL) ,效应尺度d的均值为 0 484(P =0 0 0 0 )。两组人群的基因型分布频率没有差异 ,ALAD1- 2 / 2 - 2 和ALAD1- 1分别占总人群的 89 3 %和 1 0 7%。结论为ALAD基因多态性可影响血铅水平 ,但还需完善设计进一步研究。铅接触水平可能会改变ALAD基因多态性对血铅水平的影响