Multi-constrained matroidal knapsack problems

DOI10.1007/BF01589104zbMath0682.90074MaRDI QIDQ1824560

Francesco Maffioli, Paolo M. Camerini, Carlo Vercellis

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

approximate solutions; Lagrangean relaxation; combinatorial constraints of matroidal nature; multi-constrained knapsack problems

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

90C10: Integer programming

90C27: Combinatorial optimization

05B35: Combinatorial aspects of matroids and geometric lattices

Related Items

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Decomposable multi-parameter matroid optimization problems., In memoriam Paolo M. Camerini, Note on combinatorial optimization with max-linear objective functions, Stochastic on-line knapsack problems

Cites Work

• The matroidal knapsack: A class of (often) well-solvable problems
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• A computational study of a multiple-choice knapsack algorithm
• Integer Programming Models for Sales Resource Allocation
• A mathematical programming system for preference and compatibility maximized menu planning and scheduling
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item