Optimization Methods for Constraint Resource Problems
Daniel D. Sabin, Eugene C. Freuder · 1999
In this paper we present resource optimization meth-ods for solving efficiently synthesis problems in a constraint-based framework. We obtain a tight lower bound of the problem optimum by adding redundant constraints that take into account the "wastage " in a partial solution. Abstraction through focusing on rele-vant features permits added interchangeability to deal with equivalent sets of partial solutions. Combining these two ideas allows us to discover fast the optimal solution, and also to prove very quickly its optimality.