A Lagrangean dual-based solution method for a special linear programming problem

DOI10.1016/0305-0548(87)90059-1MaRDI QIDQ581236zbMATH OpenOpenAlexFDO

Authors Mark H. Karwan, Balasubramanian Ram

Publication date 1987

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(87)90059-1

zbMATH Keywords

fixed charge transportationgeneralized assignment problemLagrangian relaxation-based dual method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Integer programming (90C10)

Review text

To solve a generalized assignment problem a Lagrangian relaxation-based dual method is used. The relaxed constraint is the single linking- equality. the authors describe a solution method which is similar to that of Karwan and Pan for the fixed charge transportation problem. Comparing the new algorithm with a regular simplex method the authors find out that the Lagrangian relaxation based dual method is twice as fast as the standard method.

Recommendations

• scientific article; zbMATH DE number 67669
• A dual method for solving the canonical linear programming problem
• scientific article; zbMATH DE number 3902406
• scientific article; zbMATH DE number 3880447
• A variant of the dual simplex method for a linear semidefinite programming problem
• A Lagrangian dual method for solving variational inequalities
• A nonlinear Lagrangian dual for integer programming
• A primal-dual simplex method for linear programs
• A least-squares primal-dual algorithm for solving linear programming problems
• A dual projective simplex method for linear programming

Cites work

• A branch and bound algorithm for the generalized assignment problem
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
• scientific article; zbMATH DE number 3581927 (Why is no real title available?)
• The Lagrangian Relaxation Method for Solving Integer Programming Problems

Cited in

(3)

• A new Lagrangian relaxation approach to the generalized assignment problem
• A simpler and faster algorithm for optimal total-work-content-power due data determination
• On solving the Lagrangian dual of integer programs via an incremental approach

This page was built for publication: A Lagrangean dual-based solution method for a special linear programming problem

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