Solving the p-Median Problem with a Semi-Lagrangian Relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem. This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish government, MCYT subsidy dpi2002-03330.     

On local optima in multiobjective combinatorial optimization problems

In this article, local optimality in multiobjective combinatorial optimization is used as a baseline for the design and analysis of two iterative improvement algorithms. Both algorithms search in a neighborhood that is defined on a collection of sets of feasible solutions and their acceptance criterion is based on outperformance relations. Proofs of the soundness and completeness of these algorithms are given.     

Discrete storage processes and their Poisson flow and fluid flow approximations

Consider discrete storage processes that are modulated by environmental processes. Environmental processes cause interruptions in the input and/or output processes of the discrete storage processes. Due to the difficulties encountered in the exact analysis of such discrete storage systems, often Poisson flow and/or fluid flow models with the same modulating environmental processes are proposed as approximations for these systems. The analysis of Poisson flow and fluid flow models is much easier than that of the discrete storage processes. In this paper we give sufficient conditions under which the content of the discrete storage processes can be bounded by the Poisson flow and the fluid flow models. For example, we show that Poisson flow models and the fluid flow models developed by Kosten (and by Anick, Mitra and Sondhi) can be used to bound the performance of infinite (finite) source packetized voice/data communication systems. We also show that a Poisson flow model and the fluid flow model developed by Mitra can be used to bound the buffer content of a two stage automatic transfer line. The potential use of the bounding techniques presented in this paper, of course, transcends well beyond these examples.Supported in part by NSF grant DMS-9308149.     

Upper Bound to the Expectation Value of the Squared Hamiltonian

An upper bound to the expectation value of the squared Hamiltonian H ² is derived which relies on replacing products of certain operators with products of the matrix representations of said operators to reduce the computational demands of H ². An example is given which shows the strength of the bound and an application with the Temple lower bound is shown.     

Combinatorial Synthesis and Multidimensional NMR Spectroscopy: An Approach to Understanding Protein–Ligand Interactions

Combinatorial chemistry is a laboratory emulation of natural recombination and selection processes. Strategies in this developing discipline involve the generation of diverse, molecular libraries through combinatorial synthesis and the selection of compounds that possess a desired property. Such approaches can facilitate the identification of ligands that bind to biological receptors, promoting our chemical understanding of cellular processes. This article illustrates that the coupling of combinatorial synthesis, multidimensional NMR spectroscopy, and biochemical methods has enhanced our understanding of a protein receptor used commonly in signal transduction, the Src Homology 3 (SH3) domain. This novel approach to studying molecular recognition has revealed a set of rules that govern SH3–ligand interactions, allowing models of receptor–ligand complexes to be constructed with only a knowledge of the polypeptide sequences. Combining combinatorial synthesis with structural methods provides a powerful new approach to understanding how proteins bind their ligands in general.     

Nanostructural Approach to Proton Ordering in Gas Hydrate Cages

A nanostructural approach to analysis of proton ordering in gas hydrate cages has been worked out within the framework of the topological model of strong and weak H-bonds. The approach involves rejection of the periodic boundary conditions, decomposition of the H-bond net into spherical layers, and two-dimensional drawing of the structure of spherical (spheroidal) fragments in the form of conjugate Schlegel diagrams. To analyze proton ordering in the spherical fragments composed of gas hydrate voids, we used the simulated annealing procedure and the correlation extension method proposed earlier.     

A genetic algorithm for structure-based de novo design

Genetic algorithms have properties which make them attractive in de novo drug design. Like other de novo design programs, genetic algorithms require a method to reduce the enormous search space of possible compounds. Most often this is done using information from known ligands. We have developed the ADAPT program, a genetic algorithm which uses molecular interactions evaluated with docking calculations as a fitness function to reduce the search space. ADAPT does not require information about known ligands. The program takes an initial set of compounds and iteratively builds new compounds based on the fitness scores of the previous set of compounds. We describe the particulars of the ADAPT algorithm and its application to three well-studied target systems. We also show that the strategies of enhanced local sampling and re-introducing diversity to the compound population during the design cycle provide better results than conventional genetic algorithm protocols.     

Supramolecular approaches to generate libraries of chelating bidentate ligands for homogeneous catalysis

The process of catalyst discovery and development relying on combinatorial methods has suffered so far from the difficult access to structurally diverse and large libraries of ligands, in particular the structurally more complex class of bidentate ligands. A completely new approach to streamline the difficult ligand synthesis process is to use structurally less complex monodentate ligands that self-assemble in the coordination sphere of a metal center through noncovalent attractive ligand-ligand interactions to generate bidentate, chelating ligands. When complementary attractive ligand-ligand interactions are employed, it is even possible to generate libraries of defined chelate-ligand catalysts by simply mixing two different monomeric ligands. This Minireview summarizes the first approaches and results in this new field of combinatorial homogeneous catalysis.     

Parameterized approximations for the two-sided assortment optimization

We consider the problem faced by an online service platform that matches suppliers with consumers. Unlike traditional matching models, which treat them as passive participants, we allow both sides of the market to exercise their choices. To model this setting, we introduce a two-sided assortment optimization model wherein each participant's choice is modeled using a multinomial logit choice function, and the platform's objective is to maximize its expected revenue. We first show that the problem is NP-hard even when the number of suppliers is limited to two and provide a mixed-integer linear programming formulation. Next, we discuss two simple greedy heuristics and argue that these can lead to arbitrarily bad solutions. We then develop relaxations that provide upper and lower bounds and investigate the tightness of these relaxations by obtaining parametric approximation guarantees. Finally, we present numerical results on synthetic data demonstrating the practical utility of these relaxations.     

The combinatorial game Nofil played on Steiner triple systems

We introduce an impartial combinatorial game on Steiner triple systems called Next One to Fill Is the Loser (Nofil ). Players move alternately, choosing points of the triple system. If a player is forced to fill a block on their turn, they lose. By computing nim-values, we determine optimal strategies for Nofil on all Steiner triple systems up to order 15 and a sampling for orders 19, 21 and 25. The game Nofil can be thought of in terms of play on a corresponding hypergraph which will become a graph during play. At that point Nofil is equivalent to playing the game Node Kayles on the graph. We prove necessary conditions and sufficient conditions for a graph to reached playing Nofil. We conclude that the complexity of determining the outcome of the game Nofil on Steiner triple systems is PSPACE-complete for randomized reductions.