Separation is of fundamental importance in cutting-plane based techniques forInteger 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{cTx : 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 κ we studymod-κ cuts of the form λT Ax [≤ λTb] for any λ ∈ {0,1/κ, … ,(κ−1)/κ}m such that λTA 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 [16], we restrict tomaximally violatedcuts, i.e., to inequalities which are violated by (κ−1)/κ by the given fractional point. We show that, for any givenk, such a separation requires O(mn min{m, n})time. Applications to the TSP are discussed. In particular, for any given κ, we propose an O(|V|2|E∗|)-time exact separation algorithm for mod-κ cuts which are maximally violated by a given fractional TSP solution with support graph G∗ = (V, E∗). This implies that we can identify a maximally violated TSP cut whenever a maximally violated(extended) comb inequalityexists. Finally, specific classes of (sometimes new) facetdefining mod-κ cuts for the TSP are analyzed.

On the separation of maximally violated mod-κ cuts

Fischetti M.;
1999

Abstract

Separation is of fundamental importance in cutting-plane based techniques forInteger 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{cTx : 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 κ we studymod-κ cuts of the form λT Ax [≤ λTb] for any λ ∈ {0,1/κ, … ,(κ−1)/κ}m such that λTA 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 [16], we restrict tomaximally violatedcuts, i.e., to inequalities which are violated by (κ−1)/κ by the given fractional point. We show that, for any givenk, such a separation requires O(mn min{m, n})time. Applications to the TSP are discussed. In particular, for any given κ, we propose an O(|V|2|E∗|)-time exact separation algorithm for mod-κ cuts which are maximally violated by a given fractional TSP solution with support graph G∗ = (V, E∗). This implies that we can identify a maximally violated TSP cut whenever a maximally violated(extended) comb inequalityexists. Finally, specific classes of (sometimes new) facetdefining mod-κ cuts for the TSP are analyzed.
1999
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-3-540-66019-4
978-3-540-48777-7
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3389525
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 1
social impact