Primal cutting plane algorithms revisited

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent.  In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.     

Generalized Longo–Rehren Subfactors and α-Induction

We study the recent construction of subfactors by Rehren which generalizes the Longo–Rehren subfactors. We prove that if we apply this construction to a non-degenerately braided subfactor N⊂M and α^±-induction, then the resulting subfactor is dual to the Longo–Rehren subfactor M⊗M ^opp⊂R arising from the entire system of irreducible endomorphisms of M resulting from α^plusmn;-induction. As a corollary, we solve a problem on existence of braiding raised by Rehren negatively. Furthermore, we generalize our previous study with Longo and Müger on multi-interval subfactors arising from a completely rational conformal net of factors on S ¹ to a net of subfactors and show that the (generalized) Longo–Rehren subfactors and α-induction naturally appear in this context. Received: 11 September 2001 / Accepted: 7 October 2001     

Complete ideals and singularities of space curves

We consider complete ideals supported on finite sequences of infinitely near points, in regular local rings with dimensions greater than two. We study properties of factorizations in Lipman special *-simple complete ideals. We relate it to a type of proximity, linear proximity, of the points, and give conditions in order to have unique factorization. Several examples are presented. Received: 2 February 2000 / in final form: 14 March 2001 / Published online: 18 January 2002     

Locally Periodic Versus Globally Periodic Infinite Words

We call a one-way infinite word w over a finite alphabet (ρ,l)-repetitive if all long enough prefixes of w contain as a suffix a ρth power (or more generally a repetition of order ρ) of a word of length at most l. We show that each (2,4)-repetitive word is ultimately periodic, as well as that there exist continuum many, and hence also nonultimately periodic, (2,5)-repetitive words. Further, we characterize nonultimately periodic (2,5)-repetitive words both structurally and algebraically.     

Rank-perfect and" weakly rank-perfect graphs

An edge e of a perfect graph G is critical if G−e is imperfect. We would like to decide whether G−e is still “almost perfect” or already “very imperfect”. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.     

Possible Loss and Recovery of Gibbsianness¶During the Stochastic Evolution of Gibbs Measures

We consider Ising-spin systems starting from an initial Gibbs measure ν and evolving under a spin-flip dynamics towards a reversible Gibbs measure μ≠ν. Both ν and μ are assumed to have a translation-invariant finite-range interaction. We study the Gibbsian character of the measure νS(t) at time t and show the following: (1) For all ν and μ, νS(t) is Gibbs for small t. (2) If both ν and μ have a high or infinite temperature, then νS(t) is Gibbs for all t > 0. (3) If ν has a low non-zero temperature and a zero magnetic field and μ has a high or infinite temperature, then νS(t) is Gibbs for small t and non-Gibbs for large t. (4) If ν has a low non-zero temperature and a non-zero magnetic field and μ has a high or infinite temperature, then νS(t) is Gibbs for small t, non-Gibbs for intermediate t, and Gibbs for large t. The regime where μ has a low or zero temperature and t is not small remains open. This regime presumably allows for many different scenarios. Received: 26 April 2001 / Accepted: 10 October 2001