Set Partitioning: A survey
From MaRDI portal
Publication:4117604
DOI10.1137/1018115zbMath0347.90064OpenAlexW2001341021MaRDI QIDQ4117604
Manfred W. Padberg, Egon Balas
Publication date: 1976
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1018115
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Lattice packing and covering (number-theoretic aspects) (11H31)
Related Items (99)
The column subtraction algorithm: An exact method for solving weighted set covering, packing and partitioning problems ⋮ An algorithm for the planar three-index assignment problem ⋮ Survivability in hierarchical telecommunications networks ⋮ Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ A column generation approach to the coalition formation problem in multi-agent systems ⋮ The matching relaxation for a class of generalized set partitioning problems ⋮ Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms ⋮ Modeling the parallel machine scheduling problem with step deteriorating jobs ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ Aggregation of constraints in integer programming ⋮ Strategic design of distribution systems with economies of scale in transportation ⋮ Solving the anti-covering location problem using Lagrangian relaxation ⋮ Tighter representations for set partitioning problems ⋮ On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ On the 0,1 facets of the set covering polytope ⋮ The Boolean quadratic polytope: Some characteristics, facets and relatives ⋮ A comparison of two methods for solving 0-1 integer programs using a general purpose simulated annealing algorithm ⋮ A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems ⋮ Ideal polytopes and face structures of some combinatorial optimization problems ⋮ Graph theoretic relaxations of set covering and set partitioning problems ⋮ On the complete set packing and set partitioning polytopes: properties and rank 1 facets ⋮ A modeling framework for incorporating DEA efficiency into set covering, packing, and partitioning formulations ⋮ New variants of the simple plant location problem and applications ⋮ Implicit enumeration algorithms for the set-partitioning problem ⋮ Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities ⋮ Set partitioning mit linearen Randbedingungen ⋮ Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs ⋮ A Branch-and-Price Algorithm for Solving the Hamiltonian p-Median Problem ⋮ Valid Inequalities and Separation Algorithms for the Set Partitioning Problem ⋮ An approximation algorithm for \(P\)-prize-collecting set cover problem ⋮ Discrete extremal problems ⋮ A districting procedure for social organizations ⋮ Heuristics and their design: A survey ⋮ A unified approach to approximating partial covering problems ⋮ An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem ⋮ An effective structured approach to finding optimal partitions of networks ⋮ Order batching in walk-and-pick order picking systems ⋮ On optimal flip-flop grouping for VLSI power minimization ⋮ Limited memory rank-1 cuts for vehicle routing problems ⋮ A new modeling and solution approach for the set-partitioning problem ⋮ Modeling profit sharing in combinatorial exchanges by network flows ⋮ On a posterior evaluation of a simple greedy method for set packing ⋮ Rounding to an integral program ⋮ Covering arrays via set covers ⋮ A matheuristic for the cell formation problem ⋮ An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts ⋮ Experiments with the “Oregon Trail Knapsack Problem” ⋮ Transitive packing ⋮ On the mixed set covering, packing and partitioning polytope ⋮ A dual ascent procedure for the set partitioning problem ⋮ General cut-generating procedures for the stable set polytope ⋮ An integer programming approach to generating airline crew pairings ⋮ A tutorial on branch and cut algorithms for the maximum stable set problem ⋮ Modelling transfer line design problem via a set partitioning problem ⋮ Pseudo-Boolean optimization ⋮ A set packing model for the ground holding problem in congested networks ⋮ A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints ⋮ A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery ⋮ A branch-and-cut algorithm for the maximum cardinality stable set problem ⋮ Facility location models for distribution system design ⋮ Hyperbolic set covering problems with competing ground-set elements ⋮ The stochastic transportation problem with single sourcing ⋮ A branch-and-cut algorithm for the pallet loading problem ⋮ Facets of the three-index assignment polytope ⋮ A branch-and-cut algorithm for partition coloring ⋮ On the multisource hyperplanes location problem to fitting set of points ⋮ A constraint programming approach to extract the maximum number of non-overlapping test forms ⋮ Efficient solutions for special zero-one programming problems ⋮ An information-theoretic framework for the lossy compression of link streams ⋮ Complementary column generation and bounding approaches for set partitioning formulations ⋮ Improving set partitioning problem solutions by zooming around an improving direction ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ Rank-Cluster-and-Prune: An algorithm for generating clusters in complex set partitioning problems ⋮ A novel modeling approach for express package carrier planning ⋮ Valid inequalities and facets of the capacitated plant location problem ⋮ A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem ⋮ Using dual network bounds in algorithms for solving generalized set packing/partitioning problems ⋮ VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH ⋮ On the resolution and optimization of a system of fuzzy relational equations with sup-\(T\) composition ⋮ Combination of local search and CLP in the vehicle-fleet scheduling problem ⋮ Facets and algorithms for capacitated lot sizing ⋮ The simple plant location problem: Survey and synthesis ⋮ Minimizing a linear fractional function subject to a system of sup-\(T\) equations with a continuous Archimedean triangular norm ⋮ A new lifting theorem for vertex packing ⋮ Adjacency on combinatorial polyhedra ⋮ COLE: a new heuristic approach for fixed charge problem computational results ⋮ Network models for vehicle and crew scheduling ⋮ Separating lifted odd-hole inequalities to solve the index selection problem ⋮ Easy and difficult exact covering problems arising in VLSI power reduction by clock gating ⋮ Algorithms for large scale set covering problems ⋮ An extension of set partitioning with application to scheduling problems ⋮ Some facets of the simple plant location polytope ⋮ Experiments with parallel branch-and-bound algorithms for the set covering problem ⋮ A concurrent processing framework for the set partitioning problem ⋮ OPTIMAL SET-PARTITIONING BASED ON GROUP QUALITY LIKELIHOOD USING PARTITION-GROWING ALGORITHM ⋮ \(K_ i\)-covers. I: Complexity and polytopes ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties ⋮ Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints ⋮ Airline crew scheduling: state-of-the-art
This page was built for publication: Set Partitioning: A survey