Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - On the separation of maximally violated mod-k cuts
AU - Caprara, A
AU - Fischetti, M
AU - Letchford, A N
PY - 2000
Y1 - 2000
N2 - Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min {c^Tx: Ax≤b,x integer}, where A is an m×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 λ^T A x ≤ ⌊λ T b⌋ for any λ ∈ {0,1/k,...,(k−1)/k}^m such that λ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given 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 given 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 asymmetric) TSP solution with support graph G *=(V,E*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied.
AB - Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min {c^Tx: Ax≤b,x integer}, where A is an m×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 λ^T A x ≤ ⌊λ T b⌋ for any λ ∈ {0,1/k,...,(k−1)/k}^m such that λ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given 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 given 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 asymmetric) TSP solution with support graph G *=(V,E*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied.
U2 - 10.1007/s101079900107
DO - 10.1007/s101079900107
M3 - Journal article
VL - 87
SP - 37
EP - 56
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1
ER -