Edmonds polytopes and a hierarchy of combinatorial problems

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

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)

Related Items

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, Narrow Proofs May Be Maximally Long, On the Chvátal-rank of Antiwebs, Rank of random half-integral polytopes — extended abstract —, Semiantichains and Unichain Coverings in Direct Products of Partial Orders, Random $ \Theta (\log n) $ -CNFs are Hard for Cutting Planes, On a Generalization of the Chvátal-Gomory Closure, Algorithms and Software for Convex Mixed Integer Nonlinear Programs, 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), Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone, Small Chvátal rank, On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank, Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point, Communication Lower Bounds via Critical Block Sensitivity, On optimizing over lift-and-project closures, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, Chvátal-Gomory cuts for the Steiner tree problem, On the tree augmentation problem, Lifting the knapsack cover inequalities for the knapsack polytope, Discrete subadditive functions as Gomory functions, On the complexity of recognizing integrality and total dual integrality of the $\{0,1/2\}$-closure, Integer programming methods for solving binary interdiction games, When the Gomory-chvátal closure coincides with the integer hull, On the complete set packing and set partitioning polytopes: properties and rank 1 facets, On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube, Structural Investigation of Piecewise Linearized Network Flow Problems, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Complexity, algorithmic, and computational aspects of a dial-a-ride type problem, Outer-product-free sets for polynomial optimization and oracle-based cuts, Valid Inequalities and Separation Algorithms for the Set Partitioning Problem, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, A knapsack intersection hierarchy, Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022, Two-halfspace closure, LP extreme points and cuts for the fixed-charge network design problem, Facet Generating Techniques, Sensitivity theorems in integer linear programming, Edmonds polytopes and weakly hamiltonian graphs, Vertex packings: Structural properties and algorithms, Facet of regular 0–1 polytopes, Facets from gadgets, Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs, Relaxations of mixed integer sets from lattice-free polyhedra, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, A note on the Chvátal-rank of clique family inequalities, Generalized Chvátal-Gomory closures for integer programs with bounds on variables, Strengthening convex relaxations of 0/1-sets using Boolean formulas, Approximate and exact merging of knapsack constraints with cover inequalities, Optimal placement of stereo sensors, Lower bounds for cutting planes proofs with small coefficients, Lower bounds for resolution and cutting plane proofs and monotone computations, On the Chvátal-Gomory Closure of a Compact Convex Set, Design and Verify: A New Scheme for Generating Cutting-Planes, Transitive packing, Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows, Design and verify: a new scheme for generating cutting-planes, On the Chvátal-Gomory closure of a compact convex set, Lattice Reformulation Cuts, Projected Chvátal-Gomory cuts for mixed integer linear programs, Cutting Planes and the Parameter Cutwidth, Lineare Charakterisierungen von Travelling Salesman Problemen, Relaxations of mixed integer sets from lattice-free polyhedra, The Gomory-Chvátal Closure of a Non-Rational Polytope is a Rational Polytope, Elementary closures for integer programs., A constraint generation algorithm for large scale linear programs using multiple-points separation, Several notes on the power of Gomory-Chvátal cuts, Resolution Width and Cutting Plane Rank Are Incomparable, Facets of the three-index assignment polytope, Unnamed Item, Cutting to the Chase Solving Linear Integer Arithmetic, Tactical optimization of the oil palm agribusiness supply chain, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, The Cutting Plane Method is Polynomial for Perfect Matchings, On the rational polytopes with Chvátal rank 1, Convex Relaxations and Integrality Gaps, A branch and bound algorithm for the minimum storage-time sequencing problem, Characterizing Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank, A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems, Presolve Reductions in Mixed Integer Programming, Polyhedral techniques in combinatorial optimization I: Theory, Integer programming duality: Price functions and sensitivity analysis, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem, Two algorithms to get strong Gomory cuts, The Chvátal closure of generalized stable sets in bidirected graphs, A lower bound on the Chvátal-rank of Antiwebs, Duality in mathematics and linear and integer programming, Virtual private network design over the first Chvátal closure, Strong bounds for resource constrained project scheduling: preprocessing and cutting planes, Combinatorial Optimization: The Interplay of Graph Theory, Linear and Integer Programming Illustrated on Network Flow, The value function of an integer program, Unnamed Item, Cutting to the chase., A note on quasi-kernels in digraphs, Reflections on Proof Complexity and Counting Principles

Cites Work