Unimodularity of the Clar number problem

We study the generalization to bipartite and 2-connected plane graphs of the Clar number, an optimization model proposed by Clar [E. Clar, The Aromatic Sextet, John Wiley & Sons, London, 1972] to compute indices of benzenoid hydrocarbons. Hansen and Zheng [P. Hansen, M. Zheng, The Clar number of a benzenoid hydrocarbon and linear programming, J. Math. Chem. 15 (1994) 93–107] formulated the Clar problem as an integer program and conjectured that solving the linear programming relaxation always yields integral solutions. We establish their conjecture by proving that the constraint matrix of the Clar integer program is always unimodular. Interestingly, in general these matrices are not totally unimodular. Similar results hold for the Fries number, an alternative index for benzenoids proposed earlier by Fries [K. Fries, Uber Byclische Verbindungen und ihren Vergleich mit dem Naphtalin, Ann. Chem. 454 (1927) 121–324].     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.     

On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}

In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research.     

On the set covering polytope: I. All the facets with coefficients in {0, 1, 2}

While the set packing polytope, through its connection with vertex packing, has lent itself to fruitful investigations, little is known about the set covering polytope. We characterize the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and give necessary and sufficient conditions for such an inequality to be minimal and to be facet defining. We show that all inequalities in the above class are contained in the elementary closure of the constraint set, and that 2 is the largest value ofk such that all valid inequalities for the set covering polytope with integer coefficients no greater thank are contained in the elementary closure. We point out a connection between minimal inequalities in the class investigated and certain circulant submatrices of the coefficient matrix. Finally, we discuss conditions for an inequality to cut off a fractional solution to the linear programming relaxation of the set covering problem and to improve the lower bound given by a feasible solution to the dual of the linear programming relaxation.Research supported by the National Science Foundation through grant ECS-8503198 and the Office of Naval Research through contract N0001485-K-0198.     

Decorated hypertrees

C. Jensen, J. McCammond and J. Meier have used weighted hypertrees to compute the Euler characteristic of a subgroup of the automorphism group of a free product. Weighted hypertrees also appear in the study of the homology of the hypertree poset. We link them to decorated hypertrees after a general study on decorated hypertrees, which we enumerate using box trees.     

Enumerative problems for arborescences and monotone paths on polytope graphs

Every generic linear functional $f$ on a convex polytope $P$ induces an orientation on the graph of $P$. From the resulting directed graph one can define a notion of $f$-arborescence and $f$-monotone path on $P$, as well as a natural graph structure on the vertex set of $f$-monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of $f$-arborescences, the number of $f$-monotone paths, and the diameter of the graph of $f$-monotone paths for polytopes $P$ in terms of their dimension and number of vertices or facets.     

Longest run of equal parts in a random integer composition

This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the longest run of consecutive equal parts in a composition of size n$n$. The problem was posed by Herbert Wilf at the Analysis of Algorithms conference in July 2009 (see arXiv:0906.5196).