2010 | OriginalPaper | Buchkapitel
Experiments with Two Row Tableau Cuts
verfasst von : Santanu S. Dey, Andrea Lodi, Andrea Tramontani, Laurence A. Wolsey
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Following the flurry of recent theoretical work on cutting planes from two row mixed integer group relaxations of an LP tableau, we report on some computational tests to evaluate the effectiveness of two row cuts based on lattice-free (type 2) triangles having more than one integer point on one side. A heuristic procedure to generate such triangles is presented, and then the coefficients of the integer variables are tightened by lifting. As a first step in testing the effectiveness of the triangle cuts, we make comparisons between the gap closed using Gomory mixed integer cuts for one round and the gap closed in one round using all the triangles generated by our heuristic. Our tests are carried out on different classes of randomly generated instances designed to represent different models in the literature by varying the number of integer non-basic variables, bounds and non-negativity constraints.