NDLI: On the separation of maximally violated mod-k cuts

Content Provider	Springer Nature Link
Author	Caprara, Alberto Fischetti, Matteo Letchford, Adam N.
Copyright Year	2000
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 ILP’s of the form min{c T x: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 k we study mod-k cuts of the form λ T Ax≤⌊λ T b⌋ 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, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], 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 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 a 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.
Starting Page	37
Ending Page	56
Page Count	20
File Format	PDF
ISSN	00255610
Journal	Mathematical Programming
Volume Number	87
Issue Number	1
e-ISSN	14364646
Language	English
Publisher	Springer-Verlag
Publisher Date	2000-01-01
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the separation of split cuts and related inequalities

On the Function w(x)=|{1≤s≤k : x≡a s (mod n s )}|

Applying mod-k-cuts for solving linear ordering problems

The Tree of Cuts and Minimal k-Connected Graphs

An algorithm for the separation of two-row cuts

Concavity cuts for disjoint bilinear programming

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

On the separation of disjunctive cuts

On the Theory of Cuts in Ordered Fields

On the separation of maximally violated mod-k cuts

Similar Documents

On the separation of split cuts and related inequalities

On the Function w(x)=|{1≤s≤k : x≡a s (mod n s )}|

Applying mod-k-cuts for solving linear ordering problems

The Tree of Cuts and Minimal k-Connected Graphs

An algorithm for the separation of two-row cuts

Concavity cuts for disjoint bilinear programming

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

On the separation of disjunctive cuts

On the Theory of Cuts in Ordered Fields

On the separation of maximally violated mod-k cuts