A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs

Given an undirected graph G with penalties associated with its vertices and costs associated with its edges, a Prize Collecting Steiner (PCS) tree is either an isolated vertex of G or else any tree of G, be it spanning or not. The weight of a PCS tree equals the sum of the costs for its edges plus the sum of the penalties for the vertices of G not spanned by the PCS tree. Accordingly, the Prize Collecting Steiner Problem in Graphs (PCSPG) is to find a PCS tree with the lowest weight. In this paper, after reformulating and re-interpreting a given PCSPG formulation, we use a Lagrangian Non Delayed Relax and Cut (NDRC) algorithm to generate primal and dual bounds to the problem. The algorithm is capable of adequately dealing with the exponentially many candidate inequalities to dualize. It incorporates ingredients such as a new PCSPG reduction test, an effective Lagrangian heuristic and a modification in the NDRC framework that allows duality gaps to be further reduced. The Lagrangian heuristic suggested here dominates their PCSPG counterparts in the literature. The NDRC PCSPG lower bounds, most of the time, nearly matched the corresponding Linear Programming relaxation bounds.     

The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

线性规划的最钝角松弛算法

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。     

Benders decomposition, Lagrangean relaxation and metaheuristic design

Large part of combinatorial optimization research has been devoted to the study of exact methods leading to a number of very diversified solution approaches. Some of those older frameworks can now be revisited in a metaheuristic perspective, as they are quite general frameworks for dealing with optimization problems. In this work, we propose to investigate the possibility of reinterpreting decompositions, with special emphasis on the related Benders and Lagrangean relaxation techniques. We show how these techniques, whose heuristic effectiveness is already testified by a wide literature, can be framed as a “master process that guides and modifies the operations of subordinate heuristics”, i.e., as metaheuristics. Obvious advantages arise from these approaches, first of all the runtime evolution of both upper and lower bounds to the optimal solution cost, thus yielding both a high-quality heuristic solution and a runtime quality certificate of that same solution.     

A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes

We consider the problem of developing an efficient algorithm for enumerating the extreme points of a convex polytope specified by linear constraints. Murty and Chung (Math Program 70:27–45, 1995) introduced the concept of a segment of a polytope, and used it to develop some steps for carrying out the enumeration efficiently until the convex hull of the set of known extreme points becomes a segment. That effort stops with a segment, other steps outlined in Murty and Chung (Math Program 70:27–45, 1995) for carrying out the enumeration after reaching a segment, or for checking whether the segment is equal to the original polytope, do not constitute an efficient algorithm. Here we describe the central problem in carrying out the enumeration efficiently after reaching a segment. We then discuss two procedures for enumerating extreme points, the mukkadvayam checking procedure, and the nearest point procedure. We divide polytopes into two classes: Class 1 polytopes have at least one extreme point satisfying the property that there is a hyperplane H through that extreme point such that every facet of the polytope incident at that extreme point has relative interior point intersections with both sides of H; Class 2 polytopes have the property that every hyperplane through any extreme point has at least one facet incident at that extreme point completely contained on one of its sides. We then prove that the procedures developed solve the problem efficiently when the polytope belongs to Class 2.     

A {(\frac 4 3) -} approximation algorithm for a special case of the two machine flow shop problem with several availability constraints

In this paper, we deal with a special case of the two-machine flow shop scheduling problem with several availability constraints on the second machine, under the resumable scenario. We develop an improved algorithm with a relative worst-case error bound of 4/3.     

Solid-state NMR and 2,3-dicyano-5,7-dimethyl-6H-1,4-diazepine

Crystalline 2,3-dicyano-5,7-dimethyl-6H-1,4-diazepine (A) was investigated by solid-state NMR spectroscopy, X-ray diffraction, and spectral simulations. The solid-state ¹³C NMR spectra of A display peculiar splittings for the methyl and cyano resonances. The crystal structure of A indicates that the methyl doublet is a consequence of two crystallographically inequivalent environments. The methyl motions associated with each site was examined via spin-lattice relaxation time (T₁) measurements, and the carbon relaxation times (T₁^C) were used to calculate energy barriers to methyl rotation. The energy barriers to rotation were then used to correlate each methyl ¹³C shift with a particular crystallographic environment. The complex cyano splittings, however, are a result of both crystallographic inequivalence and residual ¹³C–¹⁴N dipolar coupling. The multiplet patterns of the isotropic shifts (centerbands) are dependent upon the magic-angle spinning (MAS) rate. Spectral simulations, using the perturbation method, of the centerbands and first-order sidebands were used to demonstrate, and elucidate, the observed MAS rate-dependent multiplet patterns of the cyano signals.     

Cooling overall spin temperature: protein NMR experiments optimized for longitudinal relaxation effects

In experiments performed on protonated proteins at high fields, 80% of the NMR spectrometer time is spent waiting for the ¹H atoms to recover their polarization after recording the free induction decay. Selective excitation of a fraction of the protons in a large molecule has previously been shown to lead to faster longitudinal relaxation for the selected protons [K. Pervushin, B. Vögeli, A. Eletsky, Longitudinal ¹H relaxation optimization in TROSY NMR spectroscopy, J. Am. Chem. Soc. 124 (2002) 12898–12902; P. Schanda, B. Brutscher, Very fast two-dimensional NMR spectroscopy for real-time investigation of dynamic events in proteins on the time scale of seconds, J. Am. Chem. Soc. 127 (2005) 8014–8015; H.S. Attreya, T. Szyperski, G-matrix Fourier transform NMR spectroscopy for complete protein resonance assignment, Proc. Natl. Acad. Sci. USA 101 (2004) 9642–9647]. The pool of non-selected protons acts as a “thermal bath” and spin-diffusion processes (“flip-flop” transitions) channel the excess energy from the excited pool to the non-selected protons in regions of the molecule where other relaxation processes can dissipate the excess energy. We present here a sensitivity enhanced HSQC sequence (COST-HSQC), based on one selective E-BURP pulse, which can be used on protonated ¹⁵N enriched proteins (with or without ¹³C isotopic enrichment). This experiment is compared to a gradient sensitivity enhanced HSQC with a water flip-back pulse (the water flip-back pulse quenches the spin diffusion between ¹H^N and ¹H^α spins). This experiment is shown to have significant advantages in some circumstances. Some observed limitations, namely sample overheating with short recovery delays and complex longitudinal relaxation behaviour are discussed and analysed.     

The aqueous reference for ESR oximetry

The interaction of molecular oxygen with derivatives of nitroxide EPR spin labels has been investigated using nuclear spin-relaxation spectroscopy in aqueous and nonaqueous solvents. The proton spin-lattice relaxation rate induced by oxygen provides a measure of the local concentration of oxygen, which we find is dependent on solvent. In water, the hydrophobic effect increases the local concentration of oxygen in the nonpolar portions of solute molecules. For nitroxides reduced to the hydroxylamine in aqueous solutions, we find that the local concentration of oxygen is approximately twice that associated with a free diffusion hard sphere limit, while in octane, this effect is absent. These results show that nitroxide based ESR oximetry may suffer a reference concentration shift of order a factor of two if the aqueous nitroxide spectrum or relaxation is used as the reference.