Separation is of fundamental importance in cutting-plane based techniques f
or Integer Linear Programming (ILP). In recent decades, a considerable rese
arch effort has been devoted to the definition of effective separation proc
edures for families of well-structured cuts. In this paper:we address the s
eparation of Chvatal rank-1 inequalities in the context of general ILP's of
the form min{c(T) x : Ax less than or equal to b, x integer}, where A is a
n m x n integer matrix and b an m-dimensional integer vector. In particular
, for any given integer k we study mod-k cuts of the form lambda(T) A x les
s than or equal to right perpendicular lambda(T) b left perpendicular for a
ny lambda is an element of {0, 1/k,..., (k - 1)/k}(m) such that lambda(T)A
is integer. Following the line of research recently proposed for mod-2 cuts
by Applegate, Bixby, Chvatal and Cook [1] and Fleischer and Tardos [19], w
e restrict to maximally violated cuts, i.e., to inequalities which are viol
ated by (k - 1)/k by the given fractional point. We show that. for any give
n k, such a separation requires O(mn min {m, n}) time; Applications to both
the symmetric and asymmetric TSP are discussed. In particular, for any giv
en k, we propose an O(\V\(2)\E*\)-time exact separation algorithm for mod-k
cuts which are maximally violated by a given fractional (symmetric or asym
metric) TSP solution with support graph G* = (V, E*). This implies that we
can identify a maximally violated cut for the symmetric TSP whenever a maxi
mally violated (extended) comb inequality exists. Finally, facet-defining m
od-k: cuts for the symmetric and asymmetric TSP are studied.