ALCOMFT-TR-01-87

Meinolf Sellmann and Torsten Fahle
Coupling Variable Fixing Algorithms for the Automatic Recording Problem
Paderborn. Work package 2. May 2001.

Abstract: Variable fixing is an important technique when solving combinatorial optimization problems. Unique profitable variable values are detected with respect to the objective function and to the constraint structure of the problem. Relying on that specific structure, effective variable fixing algorithms (VFAs) are only suited for the problems they have been designed for. Frequently, new combinatorial optimization problems evolve as a combination of simpler structured problems. For such combinations, we show how VFAs for linear optimization problems can be coupled via Lagrangian relaxation. The method is applied on a multimedia problem incorporating a knapsack and a maximum weighted stable set problem.

Postscript file: ALCOMFT-TR-01-87.ps.gz (81 kb).