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.     

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.     

Global and local expression of chirality in serine on the Cu{110} surface

Establishing a molecular-level understanding of enantioselectivity and chiral resolution at the organic-inorganic interfaces is a key challenge in the field of heterogeneous catalysis. As a model system, we investigate the adsorption geometry of serine on Cu{110} using a combination of low-energy electron diffraction (LEED), scanning tunneling microscopy (STM), X-ray photoelectron spectroscopy (XPS), and near-edge X-ray absorption fine structure (NEXAFS) spectroscopy. The chirality of enantiopure chemisorbed layers, where serine is in its deprotonated (anionic) state, is expressed at three levels: (i) the molecules form dimers whose orientation with respect to the substrate depends on the molecular chirality, (ii) dimers of L- and D-enantiomers aggregate into superstructures with chiral (-1 ?2; 4 0) lattices, respectively, which are mirror images of each other, and (iii) small islands have elongated shapes with the dominant direction depending on the chirality of the molecules. Dimer and superlattice formation can be explained in terms of intra- and interdimer bonds involving carboxylate, amino, and β-OH groups. The stability of the layers increases with the size of ordered islands. In racemic mixtures, we observe chiral resolution into small ordered enantiopure islands, which appears to be driven by the formation of homochiral dimer subunits and the directionality of interdimer hydrogen bonds. These islands show the same enantiospecific elongated shapes those as in low-coverage enantiopure layers.     

Decomposition Algorithms for Stochastic Programming on a Computational Grid

We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker type (with the workers being used to solve second-stage problems), and the MW runtime support library (which supports master-worker computations) is key to the implementation. Computational results are presented on large sample-average approximations of problems from the literature.     

Self-assembly of monodispersed, chiral nanoclusters of cysteine on the Au(110)-(1 x 2) surface

The self-assembly of monodispersed supramolecular nanoclusters was observed by scanning tunneling microscopy (STM). The clusters form from the naturally occurring amino acid cysteine by vapor deposition onto the Au(110)-(1 x 2) surface under ultrahigh vacuum conditions. Enantiomerically pure l- and d-cysteine yields clusters with mirror-image STM signatures. Racemic ld-cysteine segregates into homochiral clusters, evidencing specific intermolecular interactions during the self-assembly process.     

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.     

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.