Integrating Relaxations for Combinatorial Optimization

In this thesis we explore two methods of computing lower bounds. We first discuss the Lagrangian Relaxation as it applies to the Golomb ruler problem, and then we explore adding multi-valued decision diagrams to an additive bounding scheme. The Golomb Ruler Problem asks to position n integer marks on a ruler such that all pairwise distances between the marks are distinct and the ruler has minimum total length. It is a notoriously challenging combinatorial problem, and provably optimal rulers are only known for n up to 27. Lower bounds can be obtained using linear programming (LP) formulations, but these are computationally expensive for large n. In Chapter 2 of this thesis, we propose a new method for finding lower bounds based on a Lagrangian relaxation. We apply a subgradient optimization scheme to find good bounds quickly, and we show experimentally that our method can find bounds that are very close to the optimal LP bound in a fraction of the time that is needed to compute the LP bound. We furthermore embed our Lagrangian bounds into a constraint programming search procedure, and show that these can help reduce the constraint programming search tree considerably. Additive bounding is a method of taking several algorithms for computing lower bounds, each of which typically exploits a different substructure of the problem, and combining them to produce a single lower bound which is larger than the lower bound that any of the individual algorithms can produce alone. Approximate multi-valued decision diagrams (MDDs) have recently been used to compute upper and lower bounds on several optimization problems. In Chapter 3 of this thesis, we show how we can integrate MDDs into an addivite bounding scheme.