Faces for a linear inequality in 0–1 variables

DOI10.1007/BF01580441zbMath0314.90063OpenAlexW2064366623MaRDI QIDQ4074671

Publication date: 1975

Published in: Mathematical Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Related Items

The clique partitioning problem: Facets and patching facets, Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem, Lifting for the integer knapsack cover polyhedron, New classes of facets for complementarity knapsack problems, Lineare Charakterisierungen von Travelling Salesman Problemen, A Lagrangian relaxation approach to the edge-weighted clique problem, Precedence-constrained covering problems with multiplicity constraints, Discrete relaxations of combinatorial programs, Lifting, superadditivity, mixed integer rounding and single node flow sets revisited, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, A note on characterizing canonical cuts using geometry, Polyhedral techniques in combinatorial optimization I: Theory, Unnamed Item, Regular (2, 2)-systems, Computing low-capacity 0–1 knapsack polytopes, Valid inequalities for mixed 0-1 programs, Implicit cover inequalities, The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design, Online joint bid/daily budget optimization of Internet advertising campaigns, Knapsack polytopes: a survey, On the complexity of sequentially lifting cover inequalities for the knapsack polytope, Cover inequalities for robust knapsack sets-Application to the robust bandwidth packing problem, On the mixing set with a knapsack constraint, Polynomial-time algorithms for regular set-covering and threshold synthesis, Approximate Deadline-Scheduling with Precedence Constraints, A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem, Lifting inequalities: a framework for generating strong cuts for nonlinear programs, Separation algorithms for 0-1 knapsack polytopes, Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints, Polyhedral analysis for concentrator location problems, Facets of the knapsack polytope derived from disjoint and overlapping index configurations, Theoretical challenges towards cutting-plane selection, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, Exploiting nested inequalities and surrogate constraints, On facets of knapsack equality polytopes, On the complexity of separation from the knapsack polytope, Ordered matroids and regular independence systems, Lifting the knapsack cover inequalities for the knapsack polytope, On the facial structure of the set covering polytope, On cutting-plane proofs in combinatorial optimization, Facets and lifting procedures for the set covering polytope, Strong valid inequalities for Boolean logical pattern generation, The transit time constrained fixed charge multi-commodity network design problem, Cover by disjoint cliques cuts for the knapsack problem with conflicting items, A cut-and-branch algorithm for the quadratic knapsack problem, An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem, Sum-of-squares hierarchy lower bounds for symmetric formulations, Sequence independent lifting for mixed knapsack problems with GUB constraints, A characterization of threshold matroids, A branch and cut algorithm for resource-constrained project scheduling problem subject to nonrenewable resources with pre-scheduled procurement, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, LP-Based Algorithms for Capacitated Facility Location, Convex hulls of superincreasing knapsacks and lexicographic orderings, A polyhedral study of the semi-continuous knapsack problem, The generalized assignment problem: Valid inequalities and facets, Facet defining inequalities for the dichotomous knapsack problem, Bidirected and unidirected capacity installation in telecommunication networks., Multidimensional sum-up rounding for integer programming in optimal experimental design, Second-order cover inequalities, The mixing-MIR set with divisible capacities, Branch-and-cut for complementarity-constrained optimization, Generalized cover facet inequalities for the generalized assignment problem, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, The precedence constrained knapsack problem: separating maximally violated inequalities, Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes, Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities, Adjacency of the 0-1 knapsack problem, Solving a school bus scheduling problem with integer programming, Supermodular covering knapsack polytope, Lifted inequalities for \(0-1\) mixed-integer bilinear covering sets, On tightening cover induced inequalities, Monotone clutters, The complexity of lifted inequalities for the knapsack problem, Polyhedral properties for the intersection of two knapsacks, Recoverable robust knapsacks: the discrete scenario case, Strong bounds with cut and column generation for class-teacher timetabling, Polyhedral results for the precedence-constrained knapsack problem, Cutting planes in integer and mixed integer programming, Maximizing a class of submodular utility functions, Formulations and valid inequalities for the heterogeneous vehicle routing problem, A branch and cut algorithm for hub location problems with single assignment, The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs, Requiring connectivity in the set covering problem, Strong IP formulations need large coefficients, Lifting the facets of zero–one polytopes, Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints, Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem, The nucleolus and kernel for simple games or special valid inequalities for 0-1 linear integer programs, (1,k)-configurations and facets for packing problems, Aggregation-based cutting-planes for packing and covering integer programs, \(0\text{-}1\) multilinear programming as a unifying theory for LAD pattern generation, Optimization algorithms for the disjunctively constrained knapsack problem, A note on the continuous mixing set, On lifted cover inequalities: a new lifting procedure with unusual properties, New valid inequalities for the fixed-charge and single-node flow polytopes, Idealness and 2-resistant sets, Efficient reformulation for 0-1 programs -- methods and computational results, RENS. The optimal rounding, A combinatorial optimization approach to the selection of statistical units, An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope, Valid inequalities, cutting planes and integrality of the knapsack polytope, Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds, Frequency assignment in mobile radio systems using branch-and-cut techniques, The submodular knapsack polytope, Capacitated facility location: Separation algorithms and computational experience, Parametric convex quadratic relaxation of the quadratic knapsack problem, Precedence-constrained covering problems with multiplicity constraints, The aggregation closure is polyhedral for packing and covering integer programs, Some integer programs arising in the design of main frame computers, On the linear description of the 3-cycle polytope, Matroidal relaxations for 0-1 knapsack problems, Cover and pack inequalities for (mixed) integer programming, Light on the infinite group relaxation. I: Foundations and taxonomy

Cites Work