Research output: Contribution in Book/Report/Proceedings › Chapter (peer-reviewed)

Published

Publication date | 1999 |
---|---|

Host publication | Integer Programming and Combinatorial Optimization: Proceedings of the 7th International IPCO Conference |

Editors | Gérard Cornuéjols, Rainer E. Burkard, Gerhard J. Woeginger |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 87-98 |

Number of pages | 12 |

ISBN (Print) | 978-3-540-66019-4 |

<mark>Original language</mark> | English |

Conference | 7th International IPCO Conference |
---|---|

Country | Austria |

City | Graz |

Period | 9/06/99 → 11/06/99 |

Name | Lecture Notes in Computer Science |
---|---|

Volume | 1610 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

Conference | 7th International IPCO Conference |
---|---|

Country | Austria |

City | Graz |

Period | 9/06/99 → 11/06/99 |

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.

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.

The full version of this paper appeared as: A. Caprara, M. Fischetti