We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this approach...

We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this...

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $\mathrm{STAB}\left(G\right)$ coincides with the fractional stable set polytope $\mathrm{QSTAB}\left(G\right)$. For all imperfect graphs $G$ it holds that $\mathrm{STAB}\left(G\right)\subset \mathrm{QSTAB}\left(G\right)$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three...

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) coincides with the fractional stable set polytope QSTAB(G). For all imperfect graphs G it holds that STAB(G) ⊂ QSTAB(G). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away...

The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems with both twice differentiable function and constraint, we can propose an efficient algorithm based on Branch and Bound techniques. The method is first displayed in the simple case with an interval constraint. The extension is displayed afterwards to the general case with an additional nonconvex twice differentiable constraint. A quadratic bounding function which is better than the well known...