Lifting cover inequalities for the precedence-constrained knapsack problem

DOI10.1016/0166-218X(95)00113-6zbMath0869.90053MaRDI QIDQ674439

Sungsoo Park, Kyungchul Park

Publication date: 5 March 1997

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

cutting-plane algorithmcover inequalitylifting procedurepolyhedral structureprecedence-constrained knapsack

Mathematics Subject Classification ID

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

Related Items

Large-scale multi-period precedence constrained knapsack problem: A mining application ⋮ Knapsack polytopes: a survey ⋮ Primal-Dual Algorithms for Precedence Constrained Covering Problems ⋮ Integer knapsack problems with set-up weights ⋮ Primal-dual algorithms for precedence constrained covering problems ⋮ Cover by disjoint cliques cuts for the knapsack problem with conflicting items ⋮ Scenario-dominance to multi-stage stochastic lot-sizing and knapsack problems ⋮ Clique-based facets for the precedence constrained knapsack problem ⋮ The precedence constrained knapsack problem: separating maximally violated inequalities ⋮ Algorithms for the bounded set-up knapsack problem ⋮ An integer programming algorithm for routing optimization in IP networks ⋮ A strengthened formulation and cutting planes for the open pit mine production scheduling problem ⋮ Production planning and scheduling in mining scenarios under IPCC mining systems ⋮ Integer programming approach to the printed circuit board grouping problem ⋮ Stage-\(t\) scenario dominance for risk-averse multi-stage stochastic mixed-integer programs

Cites Work

• Unnamed Item
• Polyhedral results for the precedence-constrained knapsack problem
• Min-cut clustering
• New Procedures For Preprocessing 0–1 Models With Knapsack-Like Constraints And Conjunctive And/Or Disjunctive Variable Upper Bounds
• Solving Large-Scale Zero-One Linear Programming Problems
• Modelling and solving an FMS part selection problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Exact Algorithms For The Setup Knapsack Problem