Non delayed relax-and-cut algorithms

Non delayed relax-and-cut algorithms

0.00 Avg rating0 Votes
Article ID: iaor20061823
Country: Netherlands
Volume: 140
Issue: 1
Start Page Number: 375
End Page Number: 410
Publication Date: Nov 2005
Journal: Annals of Operations Research
Authors:
Abstract:

Attempts to allow exponentially many inequalities to be candidates to Lagrangian dualization date from the early 1980s. In this paper, the term Relax-and-Cut, introduced elsewhere, is used to denote the whole class of Lagrangian Relaxation algorithms where Lagrangian bounds are attempted to be improved by dynamically strengthening relaxations with the introduction of valid constraints. An algorithm in that class, denoted here Non Delayed Relax-and-Cut, is described in detail, together with a general framework to obtain feasible integral solutions. Specific implementations of NDRC are presented for the Steiner Tree Problem and for a Cardinality Constrained Set Partitioning Problem.

Reviews

Required fields are marked *. Your email address will not be published.