Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms

DOI10.1016/0166-218X(87)90015-1zbMath0633.90060OpenAlexW2060879564MaRDI QIDQ1096544

Ruy Eduardo Campello, Nelson F. Maculan

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90015-1

zbMATH Keywords

column generationlower boundoptimal solutionsubgradient optimizationset partitioningLagrangean Relaxationtwo additional non-trivial constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (2)

The matching relaxation for a class of generalized set partitioning problems ⋮ On a cardinality constrained linear programming knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the knapsack problem with special ordered sets
• Finding the intersection of two convex polyhedra
• Relaxation Lagrangienne: Le Probleme Du Knapsack 0–1^†
• An $0 (n^3)$ worst case bounded special $LP$ knapsack $(0-1)$ with two constraints
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• An Algorithm for Large Set Partitioning Problems
• Set Partitioning: A survey
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Validation of subgradient optimization
• Convex Analysis

This page was built for publication: Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms