An optimization problem arising in the design of optical fibre networks is considered. Initially, it proved very difficult to solve using constraint programming: a straightforward CP model could only solve very small instances. It was remodelled using a variety of CP modelling techniques that are by now standard: symmetry breaking, implied constraints, new variables linked to the original search variables by channelling constraints. A novel two-phase search has been introduced; first assigning values to a set of intermediate variables in order to guide the subsequent assignments to the original search variables. Variable ordering heuristics have a huge impact on search effort; the two-phase search complicates the choice, but good heuristics have been found which allow the test instances to be solved. Finally, the optimization process has been changed to guide the search better.
Back to "Barbara Smith - Publications on Constraint Programming"