Long jumps in the surface diffusion of large molecules

We have studied the diffusion of the two organic molecules DC and HtBDC on the Cu(110) surface by scanning tunneling microscopy. Surprisingly, we find that long jumps, spanning multiple lattice spacings, play a dominating role in the diffusion of these molecules--the root-mean-square jump lengths are as large as 3.9 and 6.8 lattice spacings, respectively. The presence of long jumps is revealed by a new and simple method of analysis, which is tested by kinetic Monte Carlo simulations.     

Models and solution techniques for production planning problems with increasing byproducts

We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation of this continuous-time problem is nonconvex. We present a discrete-time mixed-integer nonlinear programming (MINLP) formulation that exploits the increasing nature of the byproduct ratio function. We demonstrate that this new formulation is more accurate than a previously proposed MINLP formulation. We describe three different mixed-integer linear programming (MILP) approximation and relaxation models of this nonconvex MINLP, and we derive modifications that strengthen the linear programming relaxations of these models. We also introduce nonlinear programming formulations to choose piecewise-linear approximations and relaxations of multiple functions that share the same domain and use the same set of break points in the domain. We conclude with computational experiments that demonstrate that the proposed formulation is more accurate than the previous formulation, and that the strengthened MILP approximation and relaxation models can be used to obtain provably near-optimal solutions for large instances of this nonconvex MINLP. Experiments also illustrate the quality of the piecewise-linear approximations produced by our nonlinear programming formulations.     

Self-organization of gold-containing hydrogen-bonded rosette assemblies on graphite surface

The self-organization of supramolecular structures, in particular gold-containing hydrogen-bonded rosettes, on highly oriented pyrolytic graphite (HOPG) surfaces was investigated by tapping-mode atomic force microscopy (TM-AFM) and scanning tunneling microscopy (STM). TM-AFM and high-resolution STM results show that these hydrogen-bonded assemblies self-organize to form highly ordered domains on HOPG surfaces. We find that a subtle change in one of the building blocks induces two different orientations of the assembly with respect to the surface. These results provide information on the control over the construction of supramolecular nanoarchitectures in 2D with the potential for the manufacturing of functional materials based on structural manipulation of molecular components.     

Lift-and-project cuts for convex mixed integer nonlinear programs

We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.     

Orbital branching

We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard integer programming software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs.     

Locally ideal formulations for piecewise linear functions with indicator variables

In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context.     

The impact of sampling methods on bias and variance in stochastic linear programs

Stochastic linear programs can be solved approximately by drawing a subset of all possible random scenarios and solving the problem based on this subset, an approach known as sample average approximation (SAA). The value of the objective function at the optimal solution obtained via SAA provides an estimate of the true optimal objective function value. This estimator is known to be optimistically biased; the expected optimal objective function value for the sampled problem is lower (for minimization problems) than the optimal objective function value for the true problem. We investigate how two alternative sampling methods, antithetic variates (AV) and Latin Hypercube (LH) sampling, affect both the bias and variance, and thus the mean squared error (MSE), of this estimator. For a simple example, we analytically express the reductions in bias and variance obtained by these two alternative sampling methods. For eight test problems from the literature, we computationally investigate the impact of these sampling methods on bias and variance. We find that both sampling methods are effective at reducing mean squared error, with Latin Hypercube sampling outperforming antithetic variates. For our analytic example and the eight test problems we derive or estimate the condition number as defined in Shapiro et al. (Math. Program. 94:1–19, 2002). We find that for ill-conditioned problems, bias plays a larger role in MSE, and AV and LH sampling methods are more likely to reduce bias.     

Atomic-scale surface science phenomena studied by scanning tunneling microscopy

Following the development of the scanning tunneling microscope (STM), the technique has become a very powerful and important tool for the field of surface science, since it provides direct real-space imaging of single atoms, molecules and adsorbate structures on surfaces. From a fundamental perspective, the STM has changed many basic conceptions about surfaces, and paved the way for a markedly better understanding of atomic-scale phenomena on surfaces, in particular in elucidating the importance of local bonding geometries, defects and resolving non-periodic structures and complex co-existing phases. The so-called “surface science approach”, where a complex system is reduced to its basic components and studied under well-controlled conditions, has been used successfully in combination with STM to study various fundamental phenomena relevant to the properties of surfaces in technological applications such as heterogeneous catalysis, tribology, sensors or medical implants. In this tribute edition to Gerhard Ertl, we highlight a few examples from the STM group at the University of Aarhus, where STM studies have revealed the unique role of surface defects for the stability and dispersion of Au nanoclusters on TiO₂, the nature of the catalytically active edge sites on MoS₂ nanoclusters and the catalytic properties of Au/Ni or Ag/Ni surfaces. Finally, we briefly review how reaction between complex organic molecules can be used to device new methods for self-organisation of molecular surface structures joined by comparatively strong covalent bonds.     

A branch and cut approach to the cardinality constrained circuit problem

The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most k edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits, and a branch-and-cut solution approach using these inequalities. Received: April 1998 / Accepted: October 2000?Published online October 26, 2001