On the capacitated vehicle routing problem

 We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY. Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002 Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Synthesis and novel reactivity of halomethyldimethylsulfonium salts

Iodomethyl-, chloromethyl-, and fluoromethyldimethylsulfonium salts, 4b-d, have been synthesized and are observed to be highly reactive molecules that exhibit extraordinary diversity with respect to the nature of their reactivity, undergoing facile direct substitution (S(N)2) reactions, but also being highly susceptible to electron-transfer reactions. Cyclic voltametry experiments indicated that the iodomethyldimethylsulfonium compound, 4b, is a potent electron acceptor, even surpassing the reactivity of perfluoro-n-alkyl iodides in that capacity. The iodo- and chloromethyldimethylsulfonium salts, 4b,c, as well as the analogous iodomethyltrimethylammonium salt, 3a, are shown to be reactive SET acceptors.     

Hamiltonicity and combinatorial polyhedra

We say that a polyhedron with 0–1 valued vertices is combinatorial if the midpoint of the line joining any pair of nonadjacent vertices is the midpoint of the line joining another pair of vertices. We show that the class of combinatorial polyhedra includes such well-known classes of polyhedra as matching polyhedra, matroid basis polyhedra, node packing or stable set polyhedra and permutation polyhedra. We show the graph of a combinatorial polyhedron is always either a hypercube (i.e., isomorphic to the convex hull of a k-dimension unit cube) or else is hamilton connected (every pair of nodes is the set of terminal nodes of a hamilton path). This implies several earlier results concerning special cases of combinatorial polyhedra.     

Balanced optimization problems

Suppose we are given a finite set E, a family F of ‘feasible’ subsets of E and a real weight c(e) associated with every e?E. We consider the problem of finding S?F for which max {c(e)?c(e′): e, e′ ?S} is minimized. In other words, the differenc value between the largest and smallest value used should be as small as possible. We show that if we can efficiently answer the feasibility question then we can efficiently solve the optimization problem. We specialize these results to assignment problems and thereby obtain on O(n⁴) algorithm for ‘balanced’ assignment problems.     

Hybrid triple systems and cubic feedback sets

Ac-hybrid triple system of orderv is a decomposition of the completev-vertex digraph intoc cyclic tournaments of order 3 and transitive tournaments of order 3. Hybrid triple systems generalize directed triple systems (c = 0) and Mendelsohn triple systems (c = v(v – 1)/3); omitting directions yields an underlying twofold triple system. The spectrum ofv andc for which ac-hybrid triple system of orderv exists is completely determined in this paper. Using (cubic) block intersection graphs, we then show that every twofold triple system of order underlies ac-hybrid triple system with . Examples are constructed for all sufficiently largev, for which this maximum is at most . The lower bound here is proved by establishing bounds onF _i (n, r), the size of minimum cardinality vertex feedback sets inn-vertexi-connected cubic multigraphs havingr repeated edges. We establish that , 8$$ " align="middle" border="0"> . These bounds are all tight, and the latter is used to derive the lower bound in the design theoretic problem.     

The maximum size of a convex polygon in a restricted set of points in the plane

Assume we havek points in general position in the plane such that the ratio between the maximum distance of any pair of points to the minimum distance of any pair of points is at mostk, for some positive constant. We show that there exist at leastk ^1/4 of these points which are the vertices of a convex polygon, for some positive constant=(). On the other hand, we show that for every fixed>0, ifk>k(), then there is a set ofk points in the plane for which the above ratio is at most 4k, which does not contain a convex polygon of more thank ^1/3+ vertices.The work of the first author was supported in part by the Allon Fellowship, by the Bat Sheva de Rothschild Foundation, by the Fund for Basic Research administered by the Israel Academy of Sciences, and by the Center for Absorbtion in Science. Work by the second author was supported by the Technion V. P.R. Fund, Grant No. 100-0679. The third author's work was supported by the Natural Sciences and Engineering Research Council, Canada, and the joint project Combinatorial Optimization of the Natural Science and Engineering Research Council (NSERC), Canada, and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).