12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > On the separation of maximally violated mod-k cuts
View graph of relations

« Back

On the separation of maximally violated mod-k cuts

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)

Published

Publication date1999
Host publicationInteger Programming and Combinatorial Optimization: Proceedings of the 7th International IPCO Conference
EditorsGérard Cornuéjols, Rainer E. Burkard, Gerhard J. Woeginger
Place of publicationBerlin
PublisherSpringer
Pages87-98
Number of pages12
ISBN (Print)978-3-540-66019-4
Original languageEnglish

Conference

Conference7th International IPCO Conference
CountryAustria
CityGraz
Period9/06/9911/06/99

Publication series

NameLecture Notes in Computer Science
Volume1610
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International IPCO Conference
CountryAustria
CityGraz
Period9/06/9911/06/99

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 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.

Bibliographic note

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.