Semi-Lagrangian relaxation

Cesar Beltran (cesar.beltranhec.unige.ch)
Claude Tadonki (claude.tadonkiunige.ch)
Vial Jean-philippe. (jean-philippe.vialhec.unige.ch)

Abstract: Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We propose a modified Lagrangian relaxation which used in (linear) combinatorial optimization with equality constraints generates an optimal integer solution. We call this new concept semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem.

Keywords: Lagrangian relaxation, combinatorial optimization, p-median problem, ProximalACCPM

Category 1: Combinatorial Optimization

Citation: Research report, LOGILAB - HEC - University of Geneva, September 2004

Download: [PDF]

Entry Submitted: 09/15/2004
Entry Accepted: 09/15/2004
Entry Last Modified: 09/15/2004

Modify/Update this entry