On the facial structure of set packing polyhedra
From MaRDI portal
Publication:5181532
DOI10.1007/BF01580121zbMath0272.90041MaRDI QIDQ5181532
Publication date: 1973
Published in: Mathematical Programming (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
A Lagrangean decomposition for the maximum independent set problem applied to map labeling ⋮ The facets and the symmetries of the approval-voting polytope ⋮ Accurate optimization models for interference constrained bandwidth allocation in cellular networks ⋮ A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming ⋮ Tramp ship routing and scheduling with voyage separation requirements ⋮ A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem ⋮ An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem ⋮ A cutting plane method for knapsack polytope ⋮ Stability critical graphs and ranks facets of the stable set polytope ⋮ The summed start-up costs in a unit commitment problem ⋮ New facets for the two-stage uncapacitated facility location polytope ⋮ An evolutionary algorithm based hyper-heuristic framework for the set packing problem ⋮ Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem ⋮ Time-tables, polyhedra and the greedy algorithm ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems ⋮ Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model ⋮ Cover by disjoint cliques cuts for the knapsack problem with conflicting items ⋮ Total coloring and total matching: polyhedra and facets ⋮ On the facets of stable set polytopes of circular interval graphs ⋮ Integral simplex using decomposition with primal cutting planes ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ On the complete set packing and set partitioning polytopes: properties and rank 1 facets ⋮ A branch-and-cut algorithm for the generalized traveling salesman problem with time windows ⋮ Structural Investigation of Piecewise Linearized Network Flow Problems ⋮ The clique problem with multiple-choice constraints under a cycle-free dependency graph ⋮ On the 2-Club Polytope of Graphs ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Optimizing the Layout of Proportional Symbol Maps: Polyhedra and Computation ⋮ The time dependent traveling salesman problem: polyhedra and algorithm ⋮ Single-facility scheduling by logic-based Benders decomposition ⋮ 2-clique-bond of stable set polyhedra ⋮ The rank pricing problem: models and branch-and-cut algorithms ⋮ On the facets of lift-and-project relaxations under graph operations ⋮ Facets from gadgets ⋮ Adding incompatibilities to the simple plant location problem: formulation, facets and computational experience ⋮ Conflict graphs in solving integer programming problems ⋮ A new approach for modeling and solving set packing problems ⋮ A relax-and-cut algorithm for the set partitioning problem ⋮ The \(k\)-Track assignment problem on partial orders ⋮ A smaller extended formulation for the odd cycle inequalities of the stable set polytope ⋮ A cutting plane algorithm for graph coloring ⋮ A branch-and-price algorithm for the scheduling of customer visits in the context of multi-period service territory design ⋮ Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph ⋮ On the mixed set covering, packing and partitioning polytope ⋮ On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs ⋮ On the Lovász theta function and some variants ⋮ The generalized independent set problem: polyhedral analysis and solution approaches ⋮ The strength of Dantzig-Wolfe reformulations for the stable set and related problems ⋮ A model predictive control approach for discrete-time rescheduling in complex central railway station areas ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ A branch-and-cut algorithm for graph coloring ⋮ Exploring the relationship between max-cut and stable set relaxations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A new class of facets for the Latin square polytope ⋮ A branch and cut algorithm for hub location problems with single assignment ⋮ On multi-index assignment polytopes ⋮ New facets of the STS polytope generated from known facets of the ATS polytope ⋮ Searching for mutually orthogonal Latin squares via integer and constraint programming ⋮ Strong IP formulations need large coefficients ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ A branch-and-cut algorithm for the pallet loading problem ⋮ Facets of the three-index assignment polytope ⋮ Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints ⋮ The double-assignment plant location problem with co-location ⋮ A polyhedral study on 0-1 knapsack problems with set packing constraints ⋮ Hybridization of GRASP metaheuristic with data mining techniques ⋮ The (not so) trivial lifting in two dimensions ⋮ Extended formulations for vertex cover ⋮ A fast approximation algorithm for solving the complete set packing problem ⋮ The graphical relaxation: A new framework for the symmetric traveling salesman polytope ⋮ Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut ⋮ On identifying dominant cliques. ⋮ An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope. ⋮ A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem ⋮ On the complexity of surrogate and group relaxation for integer linear programs ⋮ Strengthened clique-family inequalities for the stable set polytope ⋮ On Latin squares and the facial structure of related polytopes ⋮ A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching ⋮ Facets and algorithms for capacitated lot sizing ⋮ Strengthening Chvátal-Gomory Cuts for the Stable Set Problem ⋮ A Set Covering Approach for the Double Traveling Salesman Problem with Multiple Stacks ⋮ Frequency assignment in mobile radio systems using branch-and-cut techniques ⋮ A New Facet Generating Procedure for the Stable Set Polytope ⋮ A new lifting theorem for vertex packing ⋮ Strong bounds for resource constrained project scheduling: preprocessing and cutting planes ⋮ Worst-case analysis of clique MIPs ⋮ On the facets of the simple plant location packing polytope ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph ⋮ A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming ⋮ Dynamic node packing ⋮ Routing trains through a railway station based on a node packing model ⋮ On cycles and the stable multi-set polytope ⋮ The wheels of the orthogonal Latin squares polytope: classification and valid inequalities ⋮ A characterization of odd-hole inequalities related to Latin squares ⋮ Erratum to ``Comparison of column generation models for channel assignment in cellular networks ⋮ A concurrent processing framework for the set partitioning problem ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches ⋮ Persistency of linear programming relaxations for the stable set problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some polyhedra related to combinatorial problems
- Covers and packings in a family of sets
- Maximum matching and a polyhedron with 0,1-vertices
- The Set-Partitioning Problem: Set Covering with Equality Constraints
- Extensions of the Group Theoretic Approach in Integer Programming
- On the Set-Covering Problem
- Blocking and anti-blocking pairs of polyhedra
This page was built for publication: On the facial structure of set packing polyhedra
