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.     

Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

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.     

Influence of molecular geometry on the adsorption orientation for oligophenylene-ethynylenes on Au(111)

The adsorption structures formed from a class of oligophenylene-ethynylenes on Au(111) under ultrahigh vacuum conditions is compared based on high-resolution scanning tunneling microscopy (STM) measurements. The molecules consist of three or four benzene rings connected by ethynylene spokes and are all functionalized identically with an aldehyde, a hydroxyl, and a bulky tert-butyl group. Compounds with the conjugated spokes placed in the para, meta, and threefold configurations were previously found to exclusively form molecular layers with flat-lying adsorption geometries. In contrast, the associated compound with spokes in the ortho configuration surprisingly differs in its adsorption by forming only structures with an upright adsorption orientation. The packing density for the structures formed by the compound with the ortho configuration is less dense than that in conventional self-assembled monolayers while still keeping the conducting backbone in an upright orientation. These structures are thus interesting from the perspective of performing single-molecule conduction measurements on the oligophenylene-ethynylene backbones.     

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.