Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2001-04

September 2001


Clique Facets of the Orthogonal Latin Squares Polytope

G. Appa, D. Magos, I. Mourtos, and J. C. M. Janssen

Abstract

This paper presents a partial polyhedral characterisation of the Orthogonal Latin Squares (OLS) polytope. First, the dimension of the polytope is derived. Furthermore, three collectively exhaustive classes of cliques of the underlying intersection graph are described. Two of these classes induce facet-defining inequalities of Chvátal rank two, whereas the third one gives rise to the minimum equality system of the polytope. For each class of facets, a separation algorithm of the lowest possible complexity is also presented.


A PDF file (398 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2001-04, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk


Introduction to the CDAM Research Report Series.
CDAM Homepage.


Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html