Skip to Main content Skip to Navigation

Proximal Convexification Procedures in Combinatorial Optimization

Aris Daniilidis 1 Claude Lemaréchal 1
1 NUMOPT - Numerical Optimization
Inria Grenoble - Rhône-Alpes
Abstract : Lagrangian relaxation is useful to bound the optimal value of a given optimization problem, and also to obtain relaxed solutions. To obtain primal solutions, it is conceivable to use a convexification procedure suggested by D.P. Bertsekas in 1979, based on the proximal algorithm in the primal space. The present paper studies the theory assessing the approach in the framework of combinatorial optimization. Our results indicate that very little can be expected in theory, even though fairly good practical results have been obtained for the unit-commitment problem.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:36:58 PM
Last modification on : Thursday, February 11, 2021 - 2:54:02 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:50:11 PM


  • HAL Id : inria-00072038, version 1



Aris Daniilidis, Claude Lemaréchal. Proximal Convexification Procedures in Combinatorial Optimization. [Research Report] RR-4550, INRIA. 2002. ⟨inria-00072038⟩



Record views


Files downloads