A new class of facets for the Latin square polytope

Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAP_n). In this paper, we present a new class of facets for the associated polytope, induced by odd-hole inequalities.     

An LP-based proof for the non-existence of a pair of orthogonal Latin squares of order 6

This paper presents an alternative proof for the non-existence of orthogonal Latin squares of order 6. Our method is algebraic, rather than enumerative, and applies linear programming in order to obtain appropriate dual vectors. The proof is achievable only after extending previously known results for symmetry elimination.     

On the cut polytope

The cut polytopeP _C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP _C (G). We describe three methods with which new facet-defining inequalities ofP _C (G) can be constructed from known ones. In particular, we show that inequalities associated with chordless cycles define facets of this polytope; moreover, for these inequalities a polynomial algorithm to solve the separation problem is presented. We characterize the facet defining inequalities ofP _C (G) ifG is not contractible toK ₅. We give a simple characterization of adjacency inP _C (G) and prove that for complete graphs this polytope has diameter one and thatP _C (G) has the Hirsch property. A relationship betweenP _C (G) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.     

两两正交拉丁方最大数目的新上界

记D（x）是使得TD（x，n）存在的最小的数．本文给出D（x）的一个上界．     

On the general routing polytope

The General Routing Problem (GRP) consists of finding a minimum length closed walk in an edge-weighted undirected graph, subject to containing certain sets of required nodes and edges. It is related to the Rural Postman Problem and the Graphical Traveling Salesman Problem.We examine the 0/1-polytope associated with the GRP introduced by Ghiani and Laporte [A branch-and-cut algorithm for the Undirected Rural Postman Problem, Math. Program. Ser. A 87 (3) (2000) 467-481]. We show that whenever it is not full-dimensional, the set of equations and facets can be characterized, and the polytope is isomorphic to the full-dimensional polytope associated with another GRP instance which can be obtained in polynomial time. We also offer a node-lifting method. Both results are applied to prove the facet-defining property of some classes of valid inequalities. As a tool, we study more general polyhedra associated to the GRP.     

Mutually orthogonal equitable Latin rectangles

Let ab=n². We define an equitable Latin rectangle as an a×b matrix on a set of n symbols where each symbol appears either or times in each row of the matrix and either or times in each column of the matrix. Two equitable Latin rectangles are orthogonal in the usual way. Denote a set of ka×b mutually orthogonal equitable Latin rectangles as a k– MOELR (a,b;n). When a≠9,18,36, or 100, then we show that the maximum number of k– MOELR (a,b;n)≥3 for all possible values of (a,b).     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

Facets of the clique partitioning polytope

A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW ¹,,W ^k such that eachW _i induces a clique, i.e., a complete (but not necessarily maximal) subgraph ofG, and such thatA = _i=1 ^k 1{uv|u, v W _i ,u v}. Given weightsw ^e for alle E, the clique partitioning problem is to find a clique partitioningA ofG such that _eA w _e is as small as possible. This problem—known to be-hard, see Wakabayashi (1986)—comes up, for instance, in data analysis, and here, the underlying graphG is typically a complete graph. In this paper we study the clique partitioning polytope of the complete graphK _n , i.e., is the convex hull of the incidence vectors of the clique partitionings ofK _n . We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs ofK _n induce facets of. The theoretical results described here have been used to design an (empirically) efficient cutting plane algorithm with which large (real-world) instances of the clique partitioning problem could be solved. These computational results can be found in Grötschel and Wakabayashi (1989).     

Existence of weakly pandiagonal orthogonal Latin squares

A weakly pandiagonal Latin square of order n over the number set {0, 1, . . . , n-1} is a Latin square having the property that the sum of the n numbers in each of 2n diagonals is the same. In this paper, we shall prove that a pair of orthogonal weakly pandiagonal Latin squares of order n exists if and only if n ≡ 0, 1, 3 (mod 4) and n≠3.     

Facet-inducing web and antiweb inequalities for the graph coloring polytope

For a graph G and its complement , we define the graph coloring polytope P(G) to be the convex hull of the incidence vectors of star partitions of . We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in G. We show that for an antiweb in G the corresponding inequality is facet-inducing for P(G) if and only if is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities.     

Recursive construction of non-cyclic pandiagonal Latin squares

The pandiagonal Latin squares constructed using Hedayat’s method are cyclic. During the last decades several authors have described methods for constructing pandiagonal Latin squares which are semi-cyclic. In this paper we propose a recursive method for constructing non-cyclic pandiagonal Latin squares of any given order n$n$, where n$n$ is a positive composite integer not divisible by 2 or 3. We also investigate the orthogonality properties of the constructed squares and extend our method to construct non-cyclic pandiagonal Sudoku.     

New quasi-symmetric designs constructed using mutually orthogonal Latin squares and Hadamard matrices

Using Hadamard matrices and mutually orthogonal Latin squares, we construct two new quasi-symmetric designs, with parameters 2 − (66,30,29) and 2 − (78,36,30). These are the first examples of quasi-symmetric designs with these parameters. The parameters belong to the families 2 − (2u ² − u,u ² − u,u ² − u − 1) and 2 − (2u ² + u,u ²,u ² − u), which are related to Hadamard parameters. The designs correspond to new codes meeting the Grey–Rankin bound.     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

Gear composition and the stable set polytope

We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of when G is claw-free.     

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.     

On the range of influences in back-circulant Latin squares

In this note we obtain a large lower bound for the index of a certain critical set in the back-circulant Latin squares of odd order. This resolves in the negative a conjecture of Fitina, Seberry and Chaudhry [Back-circulant Latin square and the influence of a set, Austral. J. Combin. 20 (1999) 163-180].     

On orthogonal generalized equitable rectangles

In this note, we give a complete solution of the existence of orthogonal generalized equitable rectangles, which was raised as an open problem in by Stinson (Des Codes Cryptogr 45:347–357, 2007).