Edmonds polytopes and a hierarchy of combinatorial problems

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

Yanyan Li

Publication date: 1973

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

Mathematics Subject Classification ID

52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

90C10: Integer programming

05C65: Hypergraphs

90C27: Combinatorial optimization

Related Items

Lower bounds for cutting planes proofs with small coefficients, Lower bounds for resolution and cutting plane proofs and monotone computations, A branch and bound algorithm for the minimum storage-time sequencing problem, Polyhedral techniques in combinatorial optimization I: Theory, Two algorithms to get strong Gomory cuts, Discrete subadditive functions as Gomory functions, Edmonds polytopes and weakly hamiltonian graphs, Elementary closures for integer programs., Some new hereditary classes where graph coloring remains NP-hard, On the complexity of cutting-plane proofs, On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\), Cutting planes in integer and mixed integer programming, Constructive characterizations of the value-function of a mixed-integer program. I, Optimizing over the subtour polytope of the travelling salesman problem, Optimizing over the first Chvátal closure, Chvátal closures for mixed integer programming problems, The mixing-MIR set with divisible capacities, The stable set polytope of quasi-line graphs, Valid inequalities for mixed integer linear programs, A finitely converging cutting plane technique, Constructive characterizations of the value function of a mixed-integer program. II, Cutting planes in combinatorics, 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), Representability in mixed integer programming. I: Characterization results, Resolution vs. cutting plane solution of inference problems: Some computational experience, Matrices with the Edmonds-Johnson property, On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\), On cutting-plane proofs in combinatorial optimization, Logic applied to integer programming and integer programming applied to logic, Comments on practical implementation of Gomory's fractional algorithm, Polytope des independants d'un graphe série-parallèle, Discrete extremal problems, On total dual integrality, On stable set polyhedra for K//(1,3)free graphs, Circuits in graphs embedded on the torus, A note on symmetric doubly-stochastic matrices, Cutting-plane theory: Algebraic methods, On surrogating 0-1 knapsack constraints, A primal dual integer programming algorithm, Logic cuts for processing networks with fixed charges, Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts, Generalized resolution for 0--1 linear inequalities, On certain polytopes associated with graphs, Clique family inequalities for the stable set polytope of quasi-line graphs., Totally tight Chvatal-Gomory cuts, Strengthening Chvátal-Gomory cuts and Gomory fractional cuts, Chvatal--Gomory--tier cuts for general integer programs, Efficient reformulation for 0-1 programs -- methods and computational results, Deterministic network interdiction, \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, 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, Facets and algorithms for capacitated lot sizing, 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 Chvátal rank of polytopes in the 0/1 cube, Facets of the three-index assignment polytope, The story of perfectly orderable graphs, MIPping closures: An instant survey, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, Optimal placement of stereo sensors, Projected Chvátal-Gomory cuts for mixed integer linear programs, A constraint generation algorithm for large scale linear programs using multiple-points separation, Several notes on the power of Gomory-Chvátal cuts, Duality in mathematics and linear and integer programming, Resolution Width and Cutting Plane Rank Are Incomparable, LP extreme points and cuts for the fixed-charge network design problem, Sensitivity theorems in integer linear programming, Integer programming duality: Price functions and sensitivity analysis, The value function of an integer program, Semiantichains and Unichain Coverings in Direct Products of Partial Orders, Vertex packings: Structural properties and algorithms, Facet of regular 0–1 polytopes, Lineare Charakterisierungen von Travelling Salesman Problemen

Cites Work