Non Delayed Relax-and-Cut Algorithms |
| |
Authors: | Abilio Lucena |
| |
Institution: | 1. Departamento de Administra??o, Universidade Federal do Rio de Janeiro, Rio de Janeiro
|
| |
Abstract: | Attempts to allow exponentially many inequalities to be candidates to Lagrangian dualization date from the early 1980's. 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. |
| |
Keywords: | Lagrangian relaxation relax-and-cut valid constraints dual bound strengthening |
本文献已被 SpringerLink 等数据库收录! |
|