An algorithm for integer solutions to linear programs

By R. Gomory. 1958

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, neutral): “a long time to converge to an optimal solution if each cut added is weak for the feasible region of interest, as illustrated for example by the poor performance of the pure cutting plane algorithm of Gomory (1958). Nonetheless, cutting planes have beenextremelysuccessfulatsolving integer programs wh”
State-of-the-art review of optimization methods for short-term scheduling of batch processes (2006, methodology): “Cutting plane techniques, which were initially proposed by Gomory (1958) , and which consist of successively generating valid inequalities for the relaxed MILP problem, have received renewed interest through the work of Crowder, Johnson, and Padberg (1983), Van Roy and Wolsey (1986), and especially”
Corner Polyhedron and Intersection Cuts (2011, background): “They are equivalent [77] to Gomory’s mixed integer (GMI) cuts [58], which are generated from a single equation.”
Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition (2000, background): “The earliest and best known class of Type I inequalities are the Gomory-Chva ´tal (GC) inequalities for PIPs introduced by Gomory in the 1950s.[ 46 , 27] If all the variables in”
Effective Algorithms for the Satisfiability of Quantifier-Free Formulas Over Linear Real and Integer Arithmetic (2014, background): “Gomory showed that a combination of cuts and solving linear systems with a simplex solver is a complete technique for guiding the solver [58,59] However, because of the resulting complexity of the derived cuts, cuts in practice tend to be generated judiciously and in combination with other technique”
The SCIP Optimization Suite 3.2 (2016, methodology): “The implementations of complemented mixed-integer rounding cuts [59], flow cover cuts [58], Gomory mixed-integer rounding cuts [41, 40], multi-commodity flow network cuts [6], strong Chvátal-Gomory cuts [56], {0, 1/2}-Chvatal-Gomory cuts [18], and ChvátalGomory cuts computed via a sub-MIP [15, 28] w”