\(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates

DOI10.1007/BF02574740zbMath0820.90074OpenAlexW1966144616WikidataQ40817310 ScholiaQ40817310MaRDI QIDQ1804563

María Araceli Garín, Gloria Pérez, Laureano Fernando Escudero Bueno, Brenda L. Dietrich

Publication date: 1993

Published in: Top (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02574740

zbMATH Keywords

maximal cliquesknapsack constraintsLP relaxationstighteningalternatesextensions of minimal covers

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)

Related Items

Some properties of cliques in 0-1 mixed integer programs, \(O(n \log n)\) procedures for tightening cover inequalities, A correction of the justification of the Dietrich-Escudero-Garín-Pérez O(n) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems, A note for tightening 0-1 models, On identifying dominant cliques., An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in 0-1 mixed integer programs, On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0-1 knapsack constraint

Uses Software

• OSL

Cites Work

• Unnamed Item
• Unnamed Item
• Generating cuts in integer programming with families of special ordered sets
• An exact algorithm for the maximum clique problem
• S3 sets. An extension of the Beale-Tomlin special ordered sets
• On tightening cover induced inequalities
• On tightening 0-1 programs based on extensions of pure 0-1 knapsack and subset-sum problems
• Efficient reformulation for 0-1 programs -- methods and computational results
• Edmonds polytopes and a hierarchy of combinatorial problems
• Outline of an algorithm for integer solutions to linear programs
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• Solving Large-Scale Zero-One Linear Programming Problems
• Finding a Maximum Clique in an Arbitrary Graph
• Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
• Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
• Solving Mixed Integer Programming Problems Using Automatic Reformulation