Totally tight Chvatal-Gomory cuts (Q1612006): Difference between revisions

Let \(P_1\) be the integral hull of \(P:=\{x\in R^n:Ax\leq b\}\). A Chvátal-Gomory cut is a valid inequality for \(P\) of the form \((\lambda^T A)x\leq [\lambda^Tb]\), where \(\lambda\in R^m_t\), \(\lambda^TA\in Z^n\), \(\lambda^Tb \notin Z\), and \([\lambda^Tb]\) denotes lower integer part \(\lambda^Tb\). The author gives a polynomial-time algorithm which, given some \(x^*\in P\), detects whether a totally tight cut exist, i.e. whether there is a Chvátal-Gomory cut such that \((\lambda^TA)x^*=\lambda^Tb\).