Set Partitioning: A survey

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

Mathematics Subject Classification ID

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

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