Circuit delay optimization as a multiple choice linear knapsack program

An efficient way for optimizing timing under constraints as an integer programming problem is presented. Actually, a surrogate dual of a mathematical programming problem is solved within global enumeration schemes. The kernel of each iteration is nothing else than an instance of the multiple choice linear knapsack problem, for which a O( n) algorithm exists. Arbitrary, discrete cost-delay functions for modeling circuits, which are especially suitable for Sea of Gates designs are used. Experiments confirm usefulness of this approach