Polyhedral results for the precedence-constrained knapsack problem

DOI10.1016/0166-218X(90)90053-FMaRDI QIDQ1208480zbMATH OpenFDO

Authors E. Andrew Boyd

Publication date 16 May 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(90)90053-F

zbMATH Keywords

facetsminimal coversprecedence constraintsrooting

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10)

Recommendations

• Lifting cover inequalities for the precedence-constrained knapsack problem
• Lifting valid inequalities for the precedence constrained knapsack problem
• Clique-based facets for the precedence constrained knapsack problem
• A pegging approach to the precedence-constrained knapsack problem
• The precedence constrained knapsack problem: separating maximally violated inequalities

Cites work

• Approximation Algorithms for Certain Scheduling Problems
• Covering, Packing and Knapsack Problems
• Easily Computable Facets of the Knapsack Polytope
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• scientific article; zbMATH DE number 4191655 (Why is no real title available?)
• scientific article; zbMATH DE number 3874956 (Why is no real title available?)
• scientific article; zbMATH DE number 4008098 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• On the facial structure of set packing polyhedra
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems
• Properties of vertex packing and independence system polyhedra
• Selected Applications of Minimum Cuts in Networks
• Solving Large-Scale Zero-One Linear Programming Problems
• Some facets of the simple plant location polytope
• Technical Note—A Note on Zero-One Programming
• The capacitated plant location problem
• The complexity of lifted inequalities for the knapsack problem
• The simple plant location problem: Survey and synthesis
• Valid inequalities and facets of the capacitated plant location problem

Cited in

(28)

• A polyhedral study of the cardinality constrained knapsack problem
• Heuristic and exact algorithms for the precedence-constrained knapsack problem
• Optimization algorithms for the disjunctively constrained knapsack problem
• Lifting valid inequalities for the precedence constrained knapsack problem
• Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
• Optimizing constrained subtrees of trees
• Stage-\(t\) scenario dominance for risk-averse multi-stage stochastic mixed-integer programs
• Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem
• A strengthened formulation and cutting planes for the open pit mine production scheduling problem
• A solution approach for optimizing long- and short-term production scheduling at LKAB's kiruna mine
• A pegging approach to the precedence-constrained knapsack problem
• Primal-dual algorithms for precedence constrained covering problems
• Algorithms for the bounded set-up knapsack problem
• Large-scale multi-period precedence constrained knapsack problem: a mining application
• Primal-dual algorithms for precedence constrained covering problems
• On discrete optimization with ordering
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
• Clique-based facets for the precedence constrained knapsack problem
• The precedence constrained knapsack problem: separating maximally violated inequalities
• Production scheduling for strategic open pit mine planning: a mixed-integer programming approach
• Integer programming approach to the printed circuit board grouping problem
• An integer programming algorithm for routing optimization in IP networks
• Precedence-constrained covering problems with multiplicity constraints
• Scenario-dominance to multi-stage stochastic lot-sizing and knapsack problems
• Lifting cover inequalities for the precedence-constrained knapsack problem
• The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications
• New cutting planes for open-pit mine scheduling with multi-period block extraction
• Knapsack polytopes: a survey

This page was built for publication: Polyhedral results for the precedence-constrained knapsack problem

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