Alternative formulations for the set packing problem and their application to the winner determination problem

DOI10.1007/S10479-011-1039-4MaRDI QIDQ367639zbMATH OpenOpenAlexFDO

Authors Mercedes Landete, Antonio M. Rodríguez-Chía, Juan F. Monge

Publication date 16 September 2013

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-011-1039-4

zbMATH Keywords

set packingvalid inequalityBoolean quadric polytope

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• A fast approximation algorithm for solving the complete set packing problem
• Application of implicit enumeration to solve the packing problem
• Decomposing combinatorial auctions and set packing problems
• Solving the set packing problem via a maximum weighted independent set heuristic
• A new approach for modeling and solving set packing problems

Cites work

• scientific article; zbMATH DE number 3699703 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3619917 (Why is no real title available?)
• scientific article; zbMATH DE number 1302177 (Why is no real title available?)
• scientific article; zbMATH DE number 1538622 (Why is no real title available?)
• A new approach for modeling and solving set packing problems
• A new pricing scheme based on DEA for iterative multi-unit combinatorial auctions
• Auction Algorithms for Market Equilibrium
• CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions
• Combinatorial auction design
• Combinatorial auctions
• Combinatorial auctions: a survey
• Computationally manageable combinational auctions
• Data dependent worst case bounds for weighted set packing
• Exploiting special structures in constructing a hierarchy of relaxations for \(0-1\) mixed integer problems
• Facet Obtaining Procedures for Set Packing Problems
• Facets and lifting procedures for the set covering polytope
• Facets of the Complementarity Knapsack Polytope
• New facets for the set packing polytope
• On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0-1 knapsack constraint
• Properties of vertex packing and independence system polyhedra
• The Boolean quadratic polytope: Some characteristics, facets and relatives

Cited in

(2)

• Solving the set packing problem via a maximum weighted independent set heuristic
• A fast approximation algorithm for solving the complete set packing problem

Describes a project that uses

Uses Software

• CABOB

This page was built for publication: Alternative formulations for the set packing problem and their application to the winner determination problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q367639)