ALCOMFT-TR-01-100

Meinolf Sellmann and Torsten Fahle
CP-based Lagrangian Relaxation for a Multimedia Application
Paderborn. Work packages 2 and 4. May 2001.

Abstract: Whereas CP methods are strong with respect to the detection of local infeasibilities, OR approaches have powerful optimization abilities that ground on tight global bounds on the objective. An integration of propagation ideas from CP and Lagrangian relaxation techniques from OR combines the merits of both approaches. We introduce a general way of how linear optimization constraints can strengthen their propagation abilities via Lagrangian relaxation. The algorithm is evaluated on a set of benchmark problems steming from a multimedia application. The experiments show the superiority of the combined method compared with pure CP and OR approaches and an algorithm based on two independent optimization constraints.

Postscript file: ALCOMFT-TR-01-100.ps.gz (98 kb).