Graph theoretic relaxations of set covering and set partitioning problems

DOI10.1016/0377-2217(94)00115-SzbMath0914.90255OpenAlexW2001536197MaRDI QIDQ1390264

Elia El-Darzi, Gautam Mitra

Publication date: 14 July 1998

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(94)00115-s

zbMATH Keywords

set coveringminimum spanning treeassignmentset partitioningshortest routegreedy methodgraph theoretic relaxationsnetwork relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

A column generation approach to the coalition formation problem in multi-agent systems, The matching relaxation for a class of generalized set partitioning problems, A dual ascent procedure for the set partitioning problem, Genetic clustering algorithms., Automatic production planning of press brakes for sheet metal bending, A concurrent processing framework for the set partitioning problem, OPTIMAL SET-PARTITIONING BASED ON GROUP QUALITY LIKELIHOOD USING PARTITION-GROWING ALGORITHM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An extension of set partitioning with application to scheduling problems
• A new approach for crew pairing problems by column generation with an application to air transportation
• A network relaxation based enumeration algorithm for set partitioning
• Algorithms for large scale set covering problems
• Future paths for integer programming and links to artificial intelligence
• An algorithm for set covering problem
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• Dioïds and semirings: Links to fuzzy sets and other applications
• Covers and packings in a family of sets
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Technical Note—Equivalence of the 0-1 Integer Programming Problem to Discrete Generalized and Pure Networks
• A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem
• On some characterisations of totally unimodular matrices
• Optimal set partitioning, matchings and lagrangian duality
• Solution of Set-Covering and Set-Partitioning Problems Using Assignment Relaxations
• Set Partitioning: A survey
• Paths, Trees, and Flowers
• Balanced matrices