TY - CHAP

T1 - On the separation of maximally violated mod-k cuts

AU - Caprara, A

AU - Fischetti, M

AU - Letchford, A N

N1 - The full version of this paper appeared as: A. Caprara, M. Fischetti & A.N. Letchford (2000) On the separation of maximally violated mod-k cuts. Math. Program., 87(1), 37-56.

PY - 1999

Y1 - 1999

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 Chvatal 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 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^TA)x <= floor lambda^Tb floor¸ for any lambda in {0,1/2}^m such that lambda^TA is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvatal and Cook, and Fleischer and Tardos, 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 the TSP are discussed.

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 Chvatal 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 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^TA)x <= floor lambda^Tb floor¸ for any lambda in {0,1/2}^m such that lambda^TA is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvatal and Cook, and Fleischer and Tardos, 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 the TSP are discussed.

KW - integer programming

KW - cutting planes

KW - travelling salesman problem

U2 - 10.1007/3-540-48777-8_7

DO - 10.1007/3-540-48777-8_7

M3 - Chapter (peer-reviewed)

SN - 978-3-540-66019-4

T3 - Lecture Notes in Computer Science

SP - 87

EP - 98

BT - Integer Programming and Combinatorial Optimization

A2 - Cornuéjols, Gérard

A2 - Burkard, Rainer E.

A2 - Woeginger, Gerhard J.

PB - Springer

CY - Berlin

T2 - 7th International IPCO Conference

Y2 - 9 June 1999 through 11 June 1999

ER -