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)
7th International Conference on Integer Programming and Combinatorial Optimization, IPCO 1999
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
  • OpenAlex ND
social impact