bc–opt: a branch-and-cut code for mixed integer programs

A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted 0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities, path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints. The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the tree and cut management, so that the user only essentially needs to develop the cut separation routines. Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features. Received May 11, 1997 / Revised version received March 8, 1999?Published online June 11, 1999     

On the Minimum Average Distance Spanning Tree of the Hypercube

Given an undirected and connected graph G, with a non-negative weight on each edge, the Minimum Average Distance (MAD) spanning tree problem is to find a spanning tree of G which minimizes the average distance between pairs of vertices. This network design problem is known to be NP-hard even when the edge-weights are equal. In this paper we make a step towards the proof of a conjecture stated by A.A. Dobrynin, R. Entringer and I. Gutman in 2001, and which says that the binomial tree B _n is a MAD spanning tree of the hypercube H _n . More precisely, we show that the binomial tree B _n is a local optimum with respect to the 1-move heuristic which, starting from a spanning tree T of the hypercube H _n , attempts to improve the average distance between pairs of vertices, by adding an edge e of H _n -T and removing an edge e′ from the unique cycle created by e. We also present a greedy algorithm which produces good solutions for the MAD spanning tree problem on regular graphs such as the hypercube and the torus.     

Initial oxidation of duplex stainless steel

Three different techniques were used to produce thin oxide layers on polished and sputter-cleaned duplex stainless-steel samples. These samples were exposed to 10⁻⁵ mbar of pure oxygen inside the vacuum chamber, exposed to ambient conditions for 24 h, and plasma oxidized. The oxide layers thus produced were analysed using XPS depth profiling in order to determine the oxide layers’ compositions with depth. We found that all the techniques produce oxide layers with different traces of metallic components and with the maximum concentration of chromium oxide shifted towards the oxide-layer-bulk-metal interface. A common characteristic of all the oxide layers investigated is a double-oxide stratification, with regions closer to the surface exhibiting higher concentrations of iron oxide and those more in-depth exhibiting higher concentrations of chromium oxide. A simple non-destructive Thickogram procedure was used to corroborate the thickness estimates for the thinnest oxide layers.     

Vortex glass and vortex liquid in oscillatory media

We study the disordered, multispiral solutions of two-dimensional oscillatory media for parameter values at which the single-spiral/vortex solution is fully stable. Using the complex Ginzburg-Landau (CGLE) equation, we show that these states, heretofore believed to be static, actually evolve extremely slowly. This is achieved via a reduction of the CGLE to the evolution of the sole vortex coordinates. This true defect-mediated turbulence occurs in two distinct phases, a vortex liquid characterized by normal diffusion of spirals, and a slowly relaxing, intermittent, "vortex glass."     

Numerical description of the edge mode at the beveled extremity of a plate

This paper deals with the reflection of a two-dimensional harmonic Lamb wave at the beveled end of a plate. The existence of a resonant edge mode is described by a numerical model. It is proved that the edge mode is the resonance of different complex modes. The behavior of this mode as a function of the bevel angle is studied. Its amplitude decreases and its resonance frequency shifts as the bevel angle decreases from 90 to 85 deg. An unexpected strong variation of the repartition of the reflected energy is linked to this phenomenon.     

Langevin description of critical phenomena with two symmetric absorbing states

On the basis of general considerations, we propose a Langevin equation accounting for critical phenomena occurring in the presence of two symmetric absorbing states. We study its phase diagram by mean-field arguments and direct numerical integration in physical dimensions. Our findings fully account for and clarify the intricate picture known so far from the aggregation of partial results obtained with microscopic models. We argue that the direct transition from disorder to one of two absorbing states is best described as a (generalized) voter critical point and show that it can be split into an Ising and a directed percolation transition in dimensions larger than one.