The precedence constrained knapsack problem: separating maximally violated inequalities

DOI10.1016/J.DAM.2015.05.020MaRDI QIDQ494425zbMATH OpenOpenAlexWikidataFDO

Authors Marcos Goycoolea, Eduardo Moreno, Daniel G. Espinoza

Publication date 1 September 2015

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

Full work available at URL https://doi.org/10.1016/j.dam.2015.05.020

zbMATH Keywords

liftingshrinkingseparation probleminduced clique inequalityinduced cover inequalityprecedence-constrained knapsack problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Lifting cover inequalities for the precedence-constrained knapsack problem
• Lifting valid inequalities for the precedence constrained knapsack problem
• Polyhedral results for the precedence-constrained knapsack problem
• A pegging approach to the precedence-constrained knapsack problem
• On the exact separation of cover inequalities of maximum-depth

Cites work

• (1,k)-configurations and facets for packing problems
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A new algorithm for the open-pit mine production scheduling problem
• A sliding time window heuristic for open pit mine block sequencing
• A strengthened formulation and cutting planes for the open pit mine production scheduling problem
• Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
• Canonical Cuts on the Unit Hypercube
• Clique-based facets for the precedence constrained knapsack problem
• Computing with domino-parity inequalities for the traveling salesman problem (TSP)
• Faces for a linear inequality in 0–1 variables
• LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity
• Lifting cover inequalities for the precedence-constrained knapsack problem
• Lifting valid inequalities for the precedence constrained knapsack problem
• Lifting, tilting and fractional programming revisited
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Polyhedral results for the precedence-constrained knapsack problem
• Single-Machine Scheduling with Precedence Constraints
• Solving LP relaxations of large-scale precedence constrained problems
• Technical Note—Facets and Strong Valid Inequalities for Integer Programs

Cited in

(6)

• Polyhedral results for the precedence-constrained knapsack problem
• On the exact separation of cover inequalities of maximum-depth
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Production scheduling for strategic open pit mine planning: a mixed-integer programming approach
• Precedence-constrained covering problems with multiplicity constraints
• Precedence-constrained covering problems with multiplicity constraints

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: The precedence constrained knapsack problem: separating maximally violated inequalities

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