A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations

DOI10.1051/ro/1987210201051zbMath0644.90061OpenAlexW1441739641MaRDI QIDQ3787788

Michel Minoux

Publication date: 1987

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/104917

zbMATH Keywords

column generationclusteringlower boundsgraph partitioningcrew schedulingNP-completesatellite communicationsforestsset partitioninglinear relaxationsgeneralized linear programmingplant locationchromatic index problemk-center-summinimum weighted partitioning of a matroidvery large size set covering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Integer programming (90C10) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Inventory, storage, reservoirs (90B05)

Related Items

On combined minmax-minsum optimization, A column generation approach to job grouping for flexible manufacturing systems, Graph partitioning applied to the logic testing of combinational circuits, An exact algorithm for IP column generation, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, A column generation approach to capacitated \(p\)-median problems, Performance modeling and optimization of networks of bridged LANs, Column-Generation in Integer Linear Programming, An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment, Solving combinatorial problems with combined min-max-min-sum objective and applications