caa a22 4500 475769163 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000101xx s 000 0 eng 10.1007/s101079900107 doi (NATIONALLICENCE)springer-10.1007/s101079900107 On the separation of maximally violated mod- k cuts [Elektronische Daten] [Alberto Caprara, Matteo Fischetti, Adam N. Letchford] Abstract. : 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 T x: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 Ax≤⌊λ 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. Springer-Verlag Berlin Heidelberg, 2000 Key words: integer programming - separation - symmetric/asymmetric traveling salesman problem Mathematics Subject Classification (1991): Primary 90C10, 90C27 nationallicence Caprara Alberto DEIS, University of Bologna, Italy, IT aut Fischetti Matteo DEI, University of Padova, Italy, IT aut Letchford Adam N. Dept. of Man. Science, Lancaster University, England, GB aut https://doi.org/10.1007/s101079900107 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101079900107 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Caprara Alberto DEIS, University of Bologna, Italy, IT aut NATIONALLICENCE 700 1- Fischetti Matteo DEI, University of Padova, Italy, IT aut NATIONALLICENCE 700 1- Letchford Adam N. Dept. of Man. Science, Lancaster University, England, GB aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer