On the separation of maximally violated mod-k cuts

On the separation of maximally violated mod-k cuts

0.00 Avg rating0 Votes
Article ID: iaor20011059
Country: Germany
Volume: 87
Issue: 1
Start Page Number: 37
End Page Number: 56
Publication Date: Jan 2000
Journal: Mathematical Programming
Authors: , ,
Keywords: programming: integer
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 ILPs of the form min{cTx : Axb, 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 ≤ ⌊λTb⌋ 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 et al. 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(mnmin{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 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.

Reviews

Required fields are marked *. Your email address will not be published.