Edmonds polytopes and a hierarchy of combinatorial problems

DOI10.1016/0012-365X(73)90167-2zbMath0253.05131OpenAlexW2145243417WikidataQ59699141 ScholiaQ59699141MaRDI QIDQ2557712

Yanyan Li

Publication date: 1973

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(73)90167-2

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Integer programming (90C10) Hypergraphs (05C65) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Anti-blocking polyhedra
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Integral Extreme Points
• Letter to the Editor—A Note on the Branch-and-Bound Principle
• Minimum partition of a matroid into independent subsets
• Remarks on a Problem of Moser
• The complexity of theorem-proving procedures
• Hypergraphs and Ramseyian Theorems
• Edmonds polytopes and weakly hamiltonian graphs
• The Factorization of Linear Graphs
• Some remarks on the theory of graphs

Related Items (only showing first 100 items - show all)

Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts ⋮ Polyhedral proof methods in combinatorial optimization ⋮ Eine Min-Max Beziehung für das Exakte Matroid Problem. (A min-max relation for the exact matroid problem) ⋮ On the pseudo-periodicity of the integer hull of parametric convex polygons ⋮ Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts ⋮ Representability in mixed integer programming. I: Characterization results ⋮ MIR closures of polyhedral sets ⋮ Characterization of the split closure via geometric lifting ⋮ Generalized resolution for 0--1 linear inequalities ⋮ Resolution vs. cutting plane solution of inference problems: Some computational experience ⋮ Matrices with the Edmonds-Johnson property ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ Theoretical challenges towards cutting-plane selection ⋮ A column-and-cut generation algorithm for planning of Canadian armed forces tactical logistics distribution ⋮ A closed-form representation of mixed-integer program value functions ⋮ On the partial order polytope of a digraph ⋮ Constructing the value function for an integer linear programme over a cone ⋮ On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Optimizing over the first Chvátal closure ⋮ On the enumerative nature of Gomory's dual cutting plane method ⋮ DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips ⋮ Logic applied to integer programming and integer programming applied to logic ⋮ On finitely generated closures in the theory of cutting planes ⋮ A survey of dual-feasible and superadditive functions ⋮ Comments on practical implementation of Gomory's fractional algorithm ⋮ On disks of the triangular grid: an application of optimization theory in discrete geometry ⋮ On certain polytopes associated with graphs ⋮ On the membership problem for the \({0, 1/2}\)-closure ⋮ Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank ⋮ Polytope des independants d'un graphe série-parallèle ⋮ Discrete extremal problems ⋮ Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube ⋮ Random half-integral polytopes ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ On total dual integrality ⋮ On the Chvátal rank of polytopes in the 0/1 cube ⋮ Chvátal closures for mixed integer programming problems ⋮ On stable set polyhedra for K//(1,3)free graphs ⋮ The mixing-MIR set with divisible capacities ⋮ Limited memory rank-1 cuts for vehicle routing problems ⋮ Kernels by properly colored paths in arc-colored digraphs ⋮ On matrices with the Edmonds-Johnson property arising from bidirected graphs ⋮ The stable set polytope of quasi-line graphs ⋮ Integer linear programming for the Bayesian network structure learning problem ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ On the mixed set covering, packing and partitioning polytope ⋮ Integer programming as projection ⋮ On semantic cutting planes with very small coefficients ⋮ Circuits in graphs embedded on the torus ⋮ Three enhancements for optimization-based bound tightening ⋮ Cutting planes and the parameter cutwidth ⋮ Mingling: mixed-integer rounding with bounds ⋮ Hooked on IP ⋮ A branch-and-cut procedure for the Udine course timetabling problem ⋮ Cutting planes in integer and mixed integer programming ⋮ On the complexity of cutting-plane proofs using split cuts ⋮ On the separation of disjunctive cuts ⋮ A note on symmetric doubly-stochastic matrices ⋮ Some new hereditary classes where graph coloring remains NP-hard ⋮ On convergence in mixed integer programming ⋮ Chvatal--Gomory--tier cuts for general integer programs ⋮ On the complexity of cutting-plane proofs ⋮ On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set ⋮ Valid inequalities for mixed integer linear programs ⋮ Separation routine and extended formulations for the stable set problem in claw-free graphs ⋮ On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank ⋮ Efficient reformulation for 0-1 programs -- methods and computational results ⋮ Cutting-plane theory: Algebraic methods ⋮ Deterministic network interdiction ⋮ \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates ⋮ A geometric characterization of ``optimality-equivalent relaxations ⋮ Valid inequalities for mips and group polyhedra from approximate liftings ⋮ Fractional matroid matchings ⋮ Matchings and covers in hypergraphs ⋮ A recursive procedure to generate all cuts for 0-1 mixed integer programs ⋮ Cutting-plane proofs in polynomial space ⋮ Strengthened clique-family inequalities for the stable set polytope ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets ⋮ On the Chvátal rank of the pigeonhole principle ⋮ Facets and algorithms for capacitated lot sizing ⋮ Computing in combinatorial optimization ⋮ On matroid parity and matching polytopes ⋮ Stable sets, corner polyhedra and the Chvàtal closure ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ The aggregation closure is polyhedral for packing and covering integer programs ⋮ On surrogating 0-1 knapsack constraints ⋮ Constructive characterizations of the value-function of a mixed-integer program. I ⋮ A primal dual integer programming algorithm ⋮ A finitely converging cutting plane technique ⋮ Numerical experiments with LP formulations of the maximum clique problem ⋮ Constructive characterizations of the value function of a mixed-integer program. II ⋮ Optimizing over the subtour polytope of the travelling salesman problem ⋮ Logic cuts for processing networks with fixed charges ⋮ Computing the integer hull of convex polyhedral sets ⋮ Cutting planes in combinatorics ⋮ On a generalization of the Chvátal-Gomory closure ⋮ Totally tight Chvatal-Gomory cuts ⋮ Strengthening Chvátal-Gomory cuts and Gomory fractional cuts

This page was built for publication: Edmonds polytopes and a hierarchy of combinatorial problems