On finite generation and infinite convergence of generalized closures from the theory of cutting planes

Details On finite generation and infinite convergence of generalized closures from the theory of cutting planes On finite generation and infinite convergence of generalized closures from the theory of cutting planes

2011-06-08

arxiv.org/abs/1106.1526v1

Mathematics

Optimization and Control

Scientific paper

For convex sets $K$ and $L$ in ${\mathbb{R}}^d$ we define $R_L(K)$ to be the convex hull of all points belonging to $K$ but not to the interior of $L$. Cutting-plane methods from integer and mixed-integer optimization can be expressed in geometric terms using functionals $R_L$ with appropriately chosen sets $L$. We describe the geometric properties of $R_L(K)$ and characterize those $L$ for which $R_L$ maps polyhedra to polyhedra. For certain natural classes ${\mathcal{L}}$ of convex sets in ${\mathbb{R}}^d$ we consider the functional $R_{\mathcal{L}}$ given by $R_{\mathcal{L}}(K):= \bigcap_{L \in {\mathcal{L}}}R_L(K)$. The functional $R_{\mathcal{L}}$ can be used to define various types of closure operations considered in the theory of cutting planes (such as the Chv\'atal closure, the split closure as well as generalized split closures recently introduced by Andersen, Louveaux and Weismantel). We study conditions on ${\mathcal{L}}$ under which $R_{\mathcal{L}}$ maps rational polyhedra to rational polyhedra. We also describe the limit of the sequence of sets obtained by iterative application of $R_{\mathcal{L}}$ to $K$. A part of the presented material gives generalized formulations and unified proofs of several recent results obtained by various authors.

Affiliated with

Also associated with

No associations

Rating

On finite generation and infinite convergence of generalized closures from the theory of cutting planes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On finite generation and infinite convergence of generalized closures from the theory of cutting planes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On finite generation and infinite convergence of generalized closures from the theory of cutting planes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-320065