Integer programming and convex analysis: Intersection cuts from outer polars

Recently a new, geometrically motivated approach was proposed [1] for integer programming, based on generating intersection cuts from some convex setS whose interior contains the linear programming optimum but no feasible integer point. Larger sets tend to produce stronger cuts, and in this paper convex analysis is used to construct sets as large as possible within the above requirements. Information is generated from all problem constraints within a unit cubeK containing The key concept is that of outer polars, viewed as maximal convex extensions of the ballB circumscribingK, relative to the problem constraints. The outer polarF ^* of the feasible setF overB is shown to be a convex set whose boundary contains all feasible vertices ofK, and whose interior contains no feasible integer point. The existence of a dual correspondence betweenF andF ^*, and the fact that polarity is inclusion-reversing, leads to a dualization of operations onF. As one possible procedure based on this approach, we construct a generalized intersection cut, that can be strengthened whenever some vertex ofF is cut off. This makes it possible to fruitfully combine intersection cuts with implicit enumeration or branch-and-bound. While valid for arbitrary integer programs, the theory developed here is relevant primarily to (pure or mixed-integer) 0–1 problems. Other topics discussed include: generalized polars, intersection cuts from related problems, connections with asymptotic theory.This paper was presented at the 7th Mathematical Programming Symposium, 1970, The Hague, The Netherlands.The research underlying this paper was partially supported by the National Science Foundation under grant GP-31699 and by the Office of Naval Research under contract N00014-67-A-0314-0007 NR 047-048.     

A logarithmic Gauss curvature flow and the Minkowski problem

Let X₀ be a smooth uniformly convex hypersurface and f a postive smooth function in Sⁿ. We study the motion of convex hypersurfaces X(·,t) with initial X(·,0)=θX₀ along its inner normal at a rate equal to log(K/f) where K is the Gauss curvature of X(·,t). We show that the hypersurfaces remain smooth and uniformly convex, and there exists θ^*>0 such that if θ<θ^*, they shrink to a point in finite time and, if θ>θ^*, they expand to an asymptotic sphere. Finally, when θ=θ^*, they converge to a convex hypersurface of which Gauss curvature is given explicitly by a function depending on f(x).     

On reduced convex bodies

A convex bodyK ⊂R ^d is called reduced if for each convex bodyK′ ⊂K,K′ ≠K, the width ofK′ is less than the width ofK. We prove that reduced bodyK is of constant width if (i) the bodyK has a supporting sphere almost everywhere in ∂K. (The radius of the sphere may vary with the point in ∂K; the condition (i) and strict convexity do not imply each other.) Supported by an N.S.E.R.C. Grant of Canada.     

Skew *-derivations with power-central values

Let R be a prime ring with involution * and d be a nonzero derivation on R such that d(x ^*) = -d(x)^* for all x ∈ R. Suppose that n ≥ 1 is a fixed integer. Then (I) if d(s) ⁿ = 0 for all s = s ^*, then R is either a commutative domain or an order in a 4-dimensional central simple algebra; (II) if d(s) ⁿ ∈Z, the center of R for all s = s ^*, then R is either a commutative domain or an order in a simple algebra of dimension 4 or 16 over its center.     

Successive minima,intrinsic volumes,and lattice determinants

In Euclideand-spaceE ^d we prove a lattice-point inequality for arbitrary lattices and for the intrinsic volumesV _i (i.e., normalized quermassintegrals) of convex bodies. TheV _i are not equi-affine invariant (except the volume), hence suitable functionals of the lattice have to be introduced. The result generalizes an earlier result of Henk for the integer lattice ℤ ^d .     

On lattice points in polyhedral cross-sections

(a) We prove that the convex hull of anyk ^d +1 points of ad-dimensional lattice containsk+1 collinear lattice points. (b) For a convex polyhedron we consider the numbers of its lattice points in consecutive parallel lattice hyperplanes (levels). We prove that if a polyhedron spans no more than 2 ^d−1 levels, then this string of numbers may be arbitrary. On the other hand, we give an example of a string of 2 ^d−1+1 numbers to which no convex polyhedron corresponds inR ^d .     

Enumeration of three-dimensional convex polygons

A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice ℤ ^d withd≥2, is a well-known unsolved problem, which is studied both for its combinatorial and probabilistic interest and its connections with statistical mechanics. Of course, polygons on ℤ ^d are defined up to a translation, and the relevant statistic is their perimeter. A SAP on ℤ ^d is said to beconvex if its perimeter is “minimal”, that is, is exactly twice the sum of the side lengths of the smallest hyper-rectangle containing it. In 1984, Delest and Viennot enumerated convex SAPs on the square lattice [6], but no result was available in a higher dimension. We present an elementar approach to enumerate convex SAPs in any dimension. We first obtain a new proof of Delest and Viennot's result, which explains combinatorially the form of the generating function. We then compute the generating function for convex SAPs on the cubic lattice. In a dimension larger than 3, the details of the calculations become very cumbersome. However, our method suggests that the generating function for convex SAPs on ℤ ^d is always a quotient ofdifferentiably finite power series.     

Hit-and-run mixes fast

It is shown that the “hit-and-run” algorithm for sampling from a convex body K (introduced by R.L. Smith) mixes in time O ^*(n ² R ²/r ²), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O ^*(n ³), which matches the best known bound for other sampling algorithms. We show that the bound is best possible in terms of R,r and n. Received January 26, 1998 / Revised version received October 26, 1998?Published online July 19, 1999     

Constructing a polytope to approximate a convex body

We develop an algorithm to construct a convex polytopeP withn vertices, contained in an arbitrary convex bodyK inR ^d , so that the ratio of the volumes |K/P|/|K| is dominated byc ·. d/n ^2/(d–1).Supported in part by the fund for the promotion of research in the Technion     

An inequality for the volume of inscribed ellipsoids

LetK be a convex body inR ⁿ, and letx* intK be the center of the ellipsoid of the maximal volume inscribed in the body. An arbitrary hyperplane throughx* cutsK into two convex bodiesK ⁺ andK ^–. We show thatw(K ^±)/w(K)0.844..., wherew(·) is the volume of the inscribed ellipsoid.     

A counterexample to a ‘simplex algorithm’ for convex bodies

A counterexample, in E ³, is given to the following conjecture. Suppose f ^* is a linear functional, and e an exposed point of a convex body K such that f ^* does not attain its maximum on K at e; then there is an f ^*-strictly increasing path in the one-skeleton of K emanating from e. The counterexample shows that a certain generalized simplex algorithm fails. Furthermore for a different linear functional f, there are no three disjoint f-strictly increasing paths in the one-skeleton of K leading to e.     

A Blichfeldt-type inequality for the surface area

In 1921, Blichfeldt gave an upper bound on the number of integral points contained in a convex body in terms of the volume of the body. More precisely, he showed that #(K?\Bbb Zⁿ) ￡ n! vol(K)+n\#(K\cap{\Bbb Z}^n)\le n! {\rm vol}(K)+n , whenever K ì \Bbb RⁿK\subset{\Bbb R}^n is a convex body containing n + 1 affinely independent integral points. Here we prove an analogous inequality with respect to the surface area F(K), namely #(K?\Bbb Zⁿ) < vol(K) + ((?n+1)/2) (n-1)! F(K)\#(K\cap{\Bbb Z}^n) < {\rm vol}(K) + ((\sqrt{n}+1)/2) (n-1)! {\rm F}(K) . The proof is based on a slight improvement of Blichfeldt’s bound in the case when K is a non-lattice translate of a lattice polytope, i.e., K = t + P, where t ? \Bbb Rⁿ\\Bbb Zⁿt\in{\Bbb R}^n\setminus{\Bbb Z}^n and P is an n-dimensional polytope with integral vertices. Then we have #((t+P)?\Bbb Zⁿ) ￡ n! vol(P)\#((t+P)\cap{\Bbb Z}^n)\le n! {\rm vol}(P) . Moreover, in the 3-dimensional case we prove a stronger inequality, namely #(K?\Bbb Zⁿ) < vol(K) + 2 F(K)\#(K\cap{\Bbb Z}^n)< {\rm vol}(K) + 2 {\rm F}(K) .     

A criterion for finite lattice coverings

For a centrally symmetric convex and a covering lattice L for K, a lattice polygon P is called a covering polygon, if . We prove that P is a covering polygon, if and only if its boundary bd(P) is covered by (L ∩ P) + K. Further we show that this characterization is false for non-symmetric planar convex bodies and in Euclidean d–space, d ≥ 3, even for the unit ball K = B ^d. This revised version was published online in June 2006 with corrections to the Cover Date.     

Exponential Lower Bound for the Translative Kissing Numbers of d -Dimensional Convex Bodies

The translative kissing number H(K) of a d -dimensional convex body K is the maximum number of mutually nonoverlapping translates of K which touch K . In this paper we show that there exists an absolute constant c > 0 such that H(K)≥ 2 ^cd for every positive integer d and every d -dimensional convex body K . We also prove a generalization of this result for pairs of centrally symmetric convex bodies. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p447.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 18, 1997, and in revised form April 15, 1997.     

Expectation of intrinsic volumes of random polytopes

Let K be a convex body in ℝ ^d , let j ∈ {1, …, d−1}, and let K(n) be the convex hull of n points chosen randomly, independently and uniformly from K. If ∂K is C ₊², then an asymptotic formula is known due to M. Reitzner (and due to I. Bárány if ∂K is C ₊³) for the difference of the jth intrinsic volume of K and the expectation of the jth intrinsic volume of K(n). We extend this formula to the case when the only condition on K is that a ball rolls freely inside K. Funded by the Marie-Curie Research Training Network “Phenomena in High-Dimensions” (MRTN-CT-2004-511953).     

The only convex body with extremal distance from the ball is the simplex

We can extend the Banach-Mazur distance to be a distance between non-symmetric sets by allowing affine transformations instead of linear transformations. It was proved in [J] that for every convex bodyK we haved(K, D)≤n. It is proved that ifK is a convex body in ℝ ⁿ such thatd(K, D)=n, thenK is a simplex. This article is an M.Sc. thesis written under the supervision of E. Gluskin and V.D. Milman at Tel Aviv University. Partially supported by a G.I.F. grant.     

Konstruktion regulärer Hüllen konstanter Breite

LetM be a compact, convex set of diameter 2 inE ^d. There exists a bodyK of constant width 2 containingM such that every symmetry ofM is one ofK and every singular boundary point ofK is a boundary point ofM, for which the set of antipodes inK is the convex hull of the antipodes, which are already inM.

---

---

Mit 1 Abbildung     

Area of Julia sets of holomorphic self-maps onC *

It is a general problem to study the measure of Julia sets. There are a lot of results for rational and entire functions. In this note, we describe the measure of Julia set for some holomorphic self-maps onC ^*. We'll prove thatJ(f) has positive area, wheref:C ^*→C ^*,f(z)=z ^m c ^P(z)+Q(1/z) ,P(z) andQ(z) are monic polynomials of degreed, andm is an integer.     

A problem about the weak Hilbert property

In this paper, we prove the main result: Let both (K, S) and (K ^*,S ^*) be preordered fields, and let (K ^*,S ^*) be a finitely generated extension of (K, S). IfK ^* is transcendental overK, then (K ^*,S ^*) has the weak Hilbert property. This result answers negatively an open problem posed by the author in reference [1]. Moreover, some results on the weak Hilbert property are established. Project supported by National Natural Science Foundation of China