Improved Lagrangean decomposition: An application to the generalized assignment problem
type: Item
instance of: scholarly article
title: Improved Lagrangean decomposition: An application to the generalized assignment problem
zbMATH Open document ID: 0711.90055
DOI: 10.1016/0377-2217(90)90300-Z
author: Paulo Barcia
author: Kurt Jörnsten
published in: European Journal of Operational Research
publication date: 1990-01-01T00:00:00Z
review text: The authors are concerned with specially structured pure integer programming problems: \[ (SP)\quad z=\min cx,\quad Ax\leq b,\quad Bx\leq d,\quad x\in X\subset {\mathbb{Z}}^ n, \] where for either of the two substructures special purpose methods are available. To solve this type of integer programming problems with moderate effort, they combine a lower bound improving technique with the variable splitting (copying) technique due to \textit{M. Guignard} and \textit{S. Kim} [Math. Program. 39, 215-228 (1987; Zbl 0638.90074)]: If \(d_ k\) is a known lower bound for z and \(X_ k:=\{x\in X|\) \(cx\geq d_ k\}\) then SP can be reformulated by \[ (SPR_ k)\quad z=\min (\alpha cx+\beta cy),\quad Ax\leq b,\quad By\leq d, \] and \(x=y\), \(x\in X_ k\), \(y\in Y\) with any \(Y\supset X_ k\). This formulation is valid if \(\alpha +\beta =1.\) By relaxing the equality constraint \(x=y\) and using the Lagrangean dual of \(SPR_ k\) one ``easily'' gets a monotone increasing sequence \((d_ k)\) of lower bounds, which dominates the sequence of lower bounds induced by ordinary Lagrangean methods. This procedure can be adapted very well to solve generalized assignment problems. A series of promising experimental results completes the paper.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 4170642
zbMATH Keywords: specially structured pure integer programming
zbMATH Keywords: lower bound improving technique
zbMATH Keywords: variable splitting
zbMATH Keywords: Lagrangean dual
zbMATH Keywords: assignment problems
reviewed by: Hartmut Noltemeier
MaRDI profile type: Publication
cites work: The bound improving sequence algorithm
cites work: Constructive dual methods for discrete programming
cites work: A revised bound improvement sequence algorithm
cites work: Nondifferentiable optimization. Transl. from the Russian by Tetsushi Sasagawa
cites work: An algorithm for the solution of the 0-1 knapsack problem
cites work: A Multiplier Adjustment Method for the Generalized Assignment Problem
cites work: Lagrangean decomposition: A model yielding stronger lagrangean bounds
cites work: Validation of subgradient optimization
cites work: A new Lagrangian relaxation approach to the generalized assignment problem
cites work: Q3929530
cites work: Lower bounds to the graph partitioning problem through generalized linear programming and network flows
cites work: Q3730365
cites work: Exact methods for the knapsack problem and its generalizations
full work available at URL: 0377-2217(90)90300-z
OpenAlex ID: W2085709429
Recommended article: The splitting of variables and constraints in the formulation of integer programming models
Recommended article: Layering strategies for creating exploitable structure in linear and integer programs
Recommended article: A note on splitting of variables in integer programming models
Recommended article: Dual network bounds for integer programming problems of a special form
Recommended article: Q5287172
Recommended article: A disjunctive cutting plane procedure for general mixed-integer linear programs
Recommended article: Lagrangean decomposition for integer programming : theory and applications
Recommended article: Q4287441
Recommended article: Nonlinear integer programming algorithms: A survey
Recommended article: Technical Note—A Langrangian Algorithm for the Multiple Choice Integer Program
description: scientific article; zbMATH DE number 4170642