Degree-two Inequalities, Clique Facets, and Biperfect Graphs

DOI10.1016/S0304-0208(08)72450-2zbMath0523.52009OpenAlexW1548435598MaRDI QIDQ3673580

Manfred W. Padberg, Ellis L. Johnson

Publication date: 1982

Published in: North-Holland Mathematics Studies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-0208(08)72450-2

zbMATH Keywords

inequalities polyhedra convex hull set packing perfect graphs Boolean programming vertex covering clique inequality 0-1 solutions

Mathematics Subject Classification ID

Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Boolean programming (90C09) Graph theory (05C99) Polytopes and polyhedra (52Bxx)

Related Items (20)

Supernode processing of mixed-integer models ⋮ A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization ⋮ Refined proximity and sensitivity results in linearly constrained convex separable integer programming ⋮ A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities ⋮ Theoretical challenges towards cutting-plane selection ⋮ Binary integer programs with two variables per inequality ⋮ Some properties of cliques in 0-1 mixed integer programs ⋮ Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model ⋮ Constraint Integer Programming: A New Approach to Integrate CP and MIP ⋮ Conflict graphs in solving integer programming problems ⋮ Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs ⋮ Progress in computational mixed integer programming -- a look back from the other side of the tipping point ⋮ Cutting planes in integer and mixed integer programming ⋮ Perfect, ideal and balanced matrices ⋮ SCIP: solving constraint integer programs ⋮ Structure-driven fix-and-propagate heuristics for mixed integer programming ⋮ Presolve Reductions in Mixed Integer Programming ⋮ Worst-case analysis of clique MIPs ⋮ The maximum clique problem ⋮ Uniquely solvable quadratic Boolean equations

This page was built for publication: Degree-two Inequalities, Clique Facets, and Biperfect Graphs