Thus the convex hull of the feasible points, the so called bisection cut polytope, is a common object to study. The tightest possible description of this polytope can be utilized to improve the approximations. We incorporate the separation algorithms for the obtained new classes of valid inequalities in a branch-and-cut framework and investigate their interaction with linear and semidefinite relaxations using instances coming from VLSI design and scientific computations as well as random graphs. Generally only the linear relaxation benefits from the new inequalities. Although they also improve the bounds delivered by semidefinite relaxation, the separation time significantly slows down the solution process. The semidefinite relaxation seems to outperform the linear one due to a weakness of the primal methods applied to the linear relaxation. By means of random instances we show that combinations of the linear and the semidefinite relaxation within one solution process pay off.
|Versandkostenfrei innerhalb Deutschlands|
Wollen auch Sie Ihre Dissertation veröffentlichen?