𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem

✍ Scribed by Monique Guignard; Moshe B. Rosenwein

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
835 KB
Volume
20
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The resource‐constrained minimum weighted arborescence problem, a 0‐1 integer programming model with application in hierarchical distribution network design, is introduced. Since the model is NP‐hard, an enumeration method is required to solve it to optimality. Lagrangean decomposition, a special form of Lagrangean relaxation, is applied to the model. Both analytically and empirically, Lagrangean decomposition is shown to improve on bounds obtained by a conventional Lagrangean relaxation. An enumeration algorithm, that embeds a specialized Lagrangean dual ascent scheme to solve a Lagrangean decomposition dual, is designed, and problems with up to 1000 0‐1 variables are solved.

πŸ“œ SIMILAR VOLUMES

A branch-and-cut algorithm for the resou
A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
✍ Fischetti, Matteo; Vigo, Daniele πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 2 views

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.

The FETI family of domain decomposition
The FETI family of domain decomposition methods for inequality-constrained quadratic programming: Application to contact problems with conforming and nonconforming interfaces
✍ Philip Avery; Charbel Farhat πŸ“‚ Article πŸ“… 2009 πŸ› Elsevier Science 🌐 English βš– 372 KB

Two domain decomposition methods with Lagrange multipliers for solving iteratively quadratic programming problems with inequality constraints are presented. These methods are based on the FETI and FETI-DP substructuring algorithms. In the case of linear constraints, they do not perform any Newton-li