Talk:Cutting-plane method

Notation

I'm sure the mathematical presentation of cutting planes in this article makes sense to someone (other than the author) but it makes no sense to me. I came to wikipedia because I am not familiar with cutting planes, though I get the basic idea. Then I see a sequence of formulae, with practically no explanation of what they are supposed to mean. What is b-bar? (with an overbar) What does x_f stand for? What is the point that the sequence of formulae is trying to make?

Hi, I agree the description could be improved. The b-bar is the vector of right-hand side values b. transformed by left-multiplication by the B-inverse matrix, i.e., b-bar = B-inverse * b. The notation x_f represents a vector of nonbasic variables which contain (at least one) fractional component(s). Also, the text should read "Basis B", not "Base B". Hope this helps. Ralphey (talk) 00:40, 18 April 2008 (UTC)ralphey

Agree with the above! The section should really start by stating the optimization problem in the first place, thus clarifying what is A, x, B, F, etc. I can only guess what some of these are because I'm already somewhat familiar with linear programming. 115.129.23.210 (talk) 02:08, 31 March 2009 (UTC)

I would suggest adding information regarding other classes of cuts. Lift and project, split cuts, intersection cuts, various strengthened cuts, chvatal, integer rounding cuts etc... as well as their convex hulls (the intersection of all the cuts), and a comparison of their inclusion and non-inclusion.

Completely incorrect Example

The Example shown is completely wrong. The solution is $x_{1}=x_{2}=x_{3}=0.5$. While I'm not sure where the error is, there clearly is one. -- Ypnypn (talk) 18:35, 19 December 2013 (UTC)

I've deleted the section. If someone thinks it's correct, feel free to revert me, but do explain why. - Ypnypn (talk) 01:13, 5 January 2014 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Cutting-plane method/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

I would suggest adding information regarding various other classes of cuts--disjunctive, lift and project, integer rounding, chvatal etc... and the equivalences between these classes of cuts. Discussion of the convex hull of each class of cut would be important to include as well, including inclusions and non-inclusions.

Last edited at 01:29, 1 December 2008 (UTC). Substituted at 01:58, 5 May 2016 (UTC)

Something's off in the Gomory's cut section: Standard or canonical form?

It appears something has gone wrong in the presentation of Gomory's cut.

One issue is what form is used for constraints of a linear program

$\left\{{\begin{aligned}A\mathbf {x} \leqslant {}&\mathbf {b} \\\mathbf {x} \geqslant {}&0\end{aligned}}\right.$ or $\left\{{\begin{aligned}A\mathbf {x} +\mathbf {s} ={}&\mathbf {b} \\\mathbf {x} ,\mathbf {s} \geqslant {}&0\end{aligned}}\right.$

where the bold is to highlight the vector nature of those quantities. The simplex algorithm article calls the first form the canonical form and the second form the standard form, but the linear programming article uses both these terms for the first form and instead calls the second the augmented form (slack form), so there appears to be some disagreement on terminology here. It appears that the history of the present article moves on the canonical–standard axis however, so let's stick to that for now.

It appears the Gomory's cut section was originally written to use the standard form throughout. During 2020 two edits changed the introduction to use canonical form, but not the following argument, which relies quite heavily on having equalities. (To get coefficient 1 for the basic variables, one does Gauss–Jordan elimination, but that may require multiplying rows by negative coefficients, which would reverse an inequality.) That renders the presentation somewhat incomprehensible.

But merely changing it back to standard form would not fix the article. The catch is that converting a linear program from canonical form to standard form introduces extra slack variables (I made that $\mathbf {s}$ explicit above, rather than hiding it in a redefinition of $\mathbf {x}$), and there does not a priori seem to be any reason why these slack variables should be integers (indeed, for a general system of linear inequalities $A\mathbf {x} \leqslant \mathbf {b}$ they would not need to be), yet the presentation assumes that they are! Indeed, the presentation even claims that the new slack variable $x_{k}$ introduced for the Gomory cut constraint will be integer-valued, despite being the slack of an inequality with mostly fractional coefficients!

This probably needs the attention of an expert. 90.129.220.56 (talk) 15:13, 28 May 2022 (UTC)