Generalized convex relations with applications to optimization and models of economic dynamics

We examine a notion of generalized convex set-valued mapping, extending the notions of a convex relation and a convex process. Under general conditions, we establish duality results for composite set-valued mappings and for convex programming problems involving convex set-valued mappings. We also present applications to the study of economic dynamical systems, by obtaining the characteristics of optimal paths generated by convex processes, and to optimization problems of a certain class of positively homogeneous increasing functions.     

Foundation-penalty cuts for mixed-integer programs

We propose a new class of foundation-penalty (FP) cuts for MIPs that are easy to generate by exploiting routine penalty calculations. Their underlying concept generalizes the lifting process and provides derivations of major classical cuts. (Gomory cuts arise from low level FP cuts by simply ‘plugging in’ standard penalties.)     

The heat of fusion of poly(4-methyl pentene-1)

We have combined pressure–volume–temperature measurements and high-temperature x-ray diffraction to calculate the heat of fusion of the poly(4-methyl pentene-1) crystal from the Clapeyron equation. We find ΔH_f = 14.8 cal/g, only about half as large as several literature values. The new value of the heat of fusion leads to increased degrees of crystallinity, in agreement with the highly crystalline appearance of the x-ray patterns of typical samples, in particular oriented fibers. The new entropy of fusion at constant pressure of 2.46 cal/deg per mole of monomer units is significantly lower than the values for polypropylene, polybutene-1, and polypentene-1, indicating possible ordering in the melt of this polymer.     

Two algorithms for weighted matroid intersection

Consider a finite setE, a weight functionw:E→R, and two matroidsM ₁ andM ₂ defined onE. The weighted matroid intersection problem consists of finding a setI⊆E, independent in both matroids, that maximizes Σ{w(e):e inI}. We present an algorithm of complexity O(nr(r+c+logn)) for this problem, wheren=|E|,r=min(rank(M ₁), rank (M ₂)),c=max (c ₁,c ₂) and, fori=1,2,c _i is the complexity of finding the circuit ofI∪{e} inM _i (or show that none exists) wheree is inE andI⊆E is independent inM ₁ andM ₂. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinalityk (if one exists). Our algorithm also solves this problem. In addition, we present a second algorithm that, given a feasible solution of cardinalityk, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach. Our two algorithms are related to existing algorithms. In fact, our framework provides new simple proofs of their validity. Other contributions of this paper are the existence of nonnegative reduced weights (Theorem 6), allowing the improved complexity bound, and the introduction of artificial elements, allowing an improved start and flexibility in the implementation of the algorithms. This research was supported in part by NSF grant ECS 8503192 to Carnegie-Mellon University.     

A Netform System for Resource Planning in the U.S. Bureau of Land Management

We report an effective model and solution procedure for a major resource management problem of the U.S. Bureau of Land Management (B.L.M.), enabling large practical applications to be solved 20-300 times faster than previously possible. The resulting system has proved a useful analysis tool, providing model interaction capabilities that are employed routinely by the B.L.M. an average of 700 times a month throughout the U.S.     

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|EV|+|V| ²log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (V,E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with colori in the tree, for eachi. Our algorithm for this problem has complexity O(|EV|+m ² |V|+ m|V| ²). A special case of this constrained spanning tree problem occurs whenV ^* is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV ^*. Then the complexity of our algorithm is O(|VE|+|V ^* V| ²). Finally, we discuss a new relaxation of the traveling salesman problem.This report was supported in part by NSF grant ECS 8601660.     

General Purpose Heuristics for Integer Programming—Part II

In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a class by class basis, but which apply to a broader range of problems, have significant value. We provide a theoretical framework and associated explicit proposals for generating general purpose IP heuristics. Our development, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.     

Glycopeptide and Oligosaccharide Libraries

Despite the burgeoning interest in the various biological functions and consequent therapeutic potential of the vast number of oligosaccharides found in nature on glycoproteins and cell surfaces, the development of combinatorial carbohydrate chemistry has not progressed as rapidly as expected. The reason for this imbalance is rooted in the difficulty of oligosaccharide assembly and analysis that renders synthesis a rather cumbersome endeavor. Parallel approaches that generate series of analogous compounds rather than real libraries have therefore typically been used. Since generally low affinity is obtained for interactions between carbohydrate receptors and modified oligosaccharides designed as mimetics of natural carbohydrate ligands, glycopeptides have been explored as alternative mimics. Glycopeptides have been proven in many cases to be superior ligands with higher affinity for a receptor than the natural carbohydrate ligand. High-affinity glycopeptide ligands have been found for several types of receptors including the E-, P-, and L-selectins, toxins, glycohydrolases, bacterial adhesins, and the mannose-6-phosphate receptor. Furthermore, the assembly of glycopeptides is considerably more facile than that of oligosaccharides and the process can be adapted to combinatorial synthesis with either glycosylated amino acid building blocks or by direct glycosylation of peptide templates. The application of the split and combine approach using ladder synthesis has allowed the generation of very large numbers of compounds which could be analyzed and screened for binding of receptors on solid phase. This powerful technique can be used generally for the identification and analysis of the complex interaction between the carbohydrates and their receptors.     

Lewis acid-catalyzed rearrangement of 2,2-dichloronorbornane to 1-chloronorbornane

The mechanism for the unusual AlCl(3)-catalyzed rearrangement of 2,2-dichloronorbornane to 1-chloronorbornane in pentane has been elucidated; the reaction, which also yields four isomeric dichloronorbornanes, occurs in three steps: (1). ionization to form the 2-chloro-2-norbornyl cation, which was fully characterized by two-dimensional (1)H and (13)C NMR in SbF(5)/SO(2)ClF; (2). Wagner-Meerwein shift to yield the 1-chloro-2-norbornyl cation, which was partially characterized by (1)H NMR; and (3). hydride abstraction.