combinatorial optimization – Page 14

Lagrangian relaxation

Published: 2001/03/13, Updated: 2003/11/04

Combinatorial Optimization, Convex Optimization bundle method, column generation, combinatorial optimization, cutting planes, duality, kelley's method, lower bounds, relaxation, subgradient

Lagrangian relaxation is a tool to find upper bounds on a given (arbitrary) maximization problem. Sometimes, the bound is exact and an optimal solution is found. Our aim in this paper is to review this technique, the theory behind it, its numerical aspects, its relation with other techniques such as column generation. Citation in: Computational … Read more

Probability distribution of solution time in GRASP: An experimental investigation

Published: 2001/02/16, Updated: 2001/02/19

Renata M. Aiex

Mauricio G.C. Resende

Celso C. Ribeiro

Meta Heuristics combinatorial optimization, experimental analysis of algorithms, grasp, meta-heuristic, parallel algorithm, probability distribution

A GRASP (greedy randomized adaptive search procedure) is a multi-start metaheuristic for combinatorial optimization. We study the probability distributions of solution time to a sub-optimal target value in five GRASPs that have appeared in the literature and for which source code is available. The distributions are estimated by running 12,000 independent runs of the heuristic. … Read more