The precedence constrained knapsack problem: separating maximally violated inequalities

DOI10.1016/j.dam.2015.05.020zbMath1330.90091OpenAlexW2137984373WikidataQ57707457 ScholiaQ57707457MaRDI QIDQ494425

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)

Related Items

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

Uses Software

• CPLEX

Cites Work

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