T-space and cutting planes

 In this paper we show how knowledge about T-space translates directly into cutting planes for general integer programming problems. After providing background on Corner Polyhedra and on T-space, this paper examines T-space in some detail. It gives a variety of constructions for T-space facets, all of which translate into cutting planes, and introduces continuous families of facets. In view of the great variety of possible facets, no one of which can be dominated either by any other or by any combination of the others, a measure of merit is introduced to provide guidance on their usefulness. T-spaces based on higher dimensional groups are discussed briefly as is the idea of going beyond cutting planes to iterated approximations of Corner Polyhedra. Received: May 24, 2001 / Accepted: January 2003 Published online: March 28, 2003     

Multistars, partial multistars and the capacitated vehicle routing problem

 In an unpublished paper, Araque, Hall and Magnanti considered polyhedra associated with the Capacitated Vehicle Routing Problem (CVRP) in the special case of unit demands. Among the valid and facet-inducing inequalities presented in that paper were the so-called multistar and partial multistar inequalities, each of which came in several versions. Some related inequalities for the case of general demands have appeared subsequently and the result is a rather bewildering array of apparently different classes of inequalities. The main goal of the present paper is to present two relatively simple procedures that can be used to show the validity of all known (and some new) multistar and partial multistar inequalities, in both the unit and general demand cases. The procedures provide a unifying explanation of the inequalities and, perhaps more importantly, ideas that can be exploited in a cutting plane algorithm for the CVRP. Computational results show that the new inequalities can be useful as cutting planes for certain CVRP instances. Received: January 9, 1999 / Accepted: June 17, 2002 Published online: September 27, 2002 Key Words. vehicle routing – valid inequalities – cutting planes     

On the separation of split cuts and related inequalities

 The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols & Li CL01. In this paper we settle this question by proving strong 𝒩𝒫-completeness of separation for split cuts. As a by-product we also show 𝒩𝒫-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen 𝒩𝒫-completeness results of Caprara & Fischetti CF96 (for -cuts) and Eisenbrand E99 (for Chvátal-Gomory cuts). To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle. Received: October 23, 2000 / Accepted: October 03, 2001 Published online: September 5, 2002 Key words. cutting planes – separation – complexity – travelling salesman problem – comb inequalities     

Optimization in forestry

 Optimization models and methods have been used extensively in the forest industry. In this paper we describe the general wood-flow in forestry and a variety of planning problems. These cover planning periods from a fraction of a second to more than one hundred years. The problems are modelled using linear, integer and nonlinear models. Solution methods used depend on the required solution time and include for example dynamic programming, LP methods, branch & bound methods, heuristics and column generation. The importance of modelling and qualitative information is also discussed. Received: January 15, 2003 / Accepted: April 24, 2003 Published online: May 28, 2003 Key words. Forestry – modelling – routing – transportation – production planning Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Solving Problems with Semidefinite and Related Constraints Using Interior-Point Methods for Nonlinear Programming

 In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided. Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002 Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Existence and multiplicity of nontrivial solutions for an elliptic equation on ℝ<Superscript><Emphasis Type="Italic">N</Emphasis></Superscript> with indefinite linear part

 Via the Linking Theorem and Pseudo-index theory, we consider the existence and multiplicity of nontrivial solutions for a class of elliptic problems in all of ℝ ^N with indefinite linear part involving resonance and non-resonance at any eigenvalue. Received: 9 September 2002 / Revised version: 14 February 2003 Published online: 24 April 2003 Mathematics Subject Classification (2000): 35J20, 35J70     

An extension theorem in symplectic geometry

 We extend the ``Extension after Restriction Principle' for symplectic embeddings of bounded starlike domains to a large class of symplectic embeddings of unbounded starlike domains. Received: 21 January 2002 / Revised version: 5 July 2002 Mathematics Subject Classification (2000): Primary 53D35, Secondary 54C20     

On the structure of rotation-invariant semigroups

 We generalize the notions of Girard algebras and MV-algebras by introducing rotation-invariant semigroups. Based on a geometrical characterization, we present five construction methods which result in rotation-invariant semigroups and in particular, Girard algebras and MV-algebras. We characterize divisibility of MV-algebras, and point out that integrality of Girard algebras follows from their other axioms. Received: 7 January 2002 / Revised version: 4 April 2002 / Published online: 19 December 2002 RID="*" ID="*" Supported by the National Scientific Research Fund Hungary (OTKA F/032782). Mathematics Subject Classification (2000): 20M14, 06F05 Key words or phrases: Residuated lattice – Conjunction for non-classical logics     

Cyclic group and knapsack facets

 Any integer program may be relaxed to a group problem. We define the master cyclic group problem and several master knapsack problems, show the relationship between the problems, and give several classes of facet-defining inequalities for each problem, as well as a set of mappings that take facets from one type of master polyhedra to another. Received: May 24, 2001 / Accepted: August 2002 Published online: March 21, 2003 Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

Young's inequality in trace-class operators

 If a and b are trace-class operators, and if u is a partial isometry, then , where ∥⋅∥₁ denotes the norm in the trace class. The present paper characterises the cases of equality in this Young inequality, and the characterisation is examined in the context of both the operator and the Hilbert–Schmidt forms of Young's inequality. Received: 20 December 2001 / Revised version: 11 July 2002 / Published online: 10 February 2003 Mathematics Subject Classification (2000): 47A63, 15A60     

A characterization of certain irreducible symplectic 4-folds

 We give a characterization of irreducible symplectic fourfolds which are given as Hilbert scheme of points on a K3 surface. Received: 26 June 2002 / Revised version: 9 September 2002 Published online: 14 February 2003 Mathematics Subject Classification (2000): Primary 14J32, Secondary 32Q20     

On projective curves of maximal regularity

 Let 𝒞⊆ℙ ^r _K be a non-degenerate projective curve of degree d>r+1 of maximal regularity so that 𝒞 has an extremal secant line . We show that 𝒞∪ is arithmetically Cohen Macaulay if d<2r−1 and we study the Betti numbers and the Hartshorne-Rao module of the curve 𝒞. Received: 27 March 2002; in final form: 24 May 2002 / Published online: 1 April 2003 Mathematics Subject Classification (1991): 14H45, 13D02. The second author was partially supported by Swiss National Science Foundation (Projects No. 20-52762.97 and 20-59237.99).     

A representation of the Belavkin equation via Feynman path integrals

 The Belavkin equation, describing the continuous measurement of the position of a quantum particle, is studied. A rigorous representation of its solution by means of an infinite dimensional oscillatory integral (Feynman path integral) defined on the complex Cameron-Martin space is given. Received: 7 January 2002 / Revised version: 20 June 2002 / Published online: 19 December 2002 Mathematics Subject Classification (2000): 81, 81S40, 60H15 Key words or phrases: Belavkin equation – Continuous measurement – Quantum theory – Oscillatory integrals – Feynman path integrals     

The speed of biased random walk on percolation clusters

 We consider biased random walk on supercritical percolation clusters in ℤ². We show that the random walk is transient and that there are two speed regimes: If the bias is large enough, the random walk has speed zero, while if the bias is small enough, the speed of the random walk is positive. Received: 20 November 2002 / Revised version: 17 January 2003 Published online: 15 April 2003 Research supported by Microsoft Research graduate fellowship. Research partially supported by the DFG under grant SPP 1033. Research partially supported by NSF grant #DMS-0104073 and by a Miller Professorship at UC Berkeley. Mathematics Subject Classification (2000): 60K37; 60K35; 60G50 Key words or phrases: Percolation – Random walk     

On the Oka principle in a Banach space,I

 Let X be a complex Banach space with a countable unconditional basis, Ω⊂X pseudoconvex open, G a complex Banach Lie group. We show that a Runge–type approximation hypothesis on X, G (which we also prove for G a solvable Lie group) implies that any holomorphic cocycle on Ω with values in G can be resolved holomorphically if it can be resolved continuously. Received: 1 March 2002 / Published online: 28 March 2003 Mathematics Subject Classification (2000): 32L05, 32E30, 46G20 RID="*" ID="*" Kedves Szímuskának. RID="*" ID="*" To my dear Wife.     

Solving monotone inclusions with linear multi-step methods

 In this paper a new class of proximal-like algorithms for solving monotone inclusions of the form T(x)∋0 is derived. It is obtained by applying linear multi-step methods (LMM) of numerical integration in order to solve the differential inclusion , which can be viewed as a generalization of the steepest decent method for a convex function. It is proved that under suitable conditions on the parameters of the LMM, the generated sequence converges weakly to a point in the solution set T ⁻¹ (0). The LMM is very similar to the classical proximal point algorithm in that both are based on approximately evaluating the resolvants of T. Consequently, LMM can be used to derive multi-step versions of many of the optimization methods based on the classical proximal point algorithm. The convergence analysis allows errors in the computation of the iterates, and two different error criteria are analyzed, namely, the classical scheme with summable errors, and a recently proposed more constructive criterion. Received: April 2001 / Accepted: November 2002 Published online: February 14, 2003 Key Words. proximal point algorithm – monotone operator – numerical integration – strong stability – relative error criterion Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

The contact boundary of a complex polynomial

 We define the contact boundary of a complex polynomial f : ℂ ⁿ → ℂ as the intersection of some generic fiber with a large sphere. We show that, up to contact isotopy, this does not depend on the choice of the fiber (provided it is generic) and is invariant under polynomial automorphism of ℂ ⁿ . We next prove that the formal homotopy class of this contact boundary is invariant in a large family of deformations of polynomials, which are not necessarily topologically trivial. Received: 15 November 2002 Published online: 20 March 2003 Mathematics Subject Classification (2000): 32S55, 53D15, 32S50     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

Matrix algebras in Quasi-Newton methods for unconstrained minimization

Summary.  In this paper a new class of quasi-Newton methods, named ℒQN, is introduced in order to solve unconstrained minimization problems. The novel approach, which generalizes classical BFGS methods, is based on a Hessian updating formula involving an algebra ℒ of matrices simultaneously diagonalized by a fast unitary transform. The complexity per step of ℒQN methods is O(n log n), thereby improving considerably BFGS computational efficiency. Moreover, since ℒQN's iterative scheme utilizes single-indexed arrays, only O(n) memory allocations are required. Global convergence properties are investigated. In particular a global convergence result is obtained under suitable assumptions on f. Numerical experiences [7] confirm that ℒQN methods are particularly recommended for large scale problems. Received December 30, 2001 / Revised version received December 20, 2001 / Published online November 27, 2002 Mathematics Subject Classification (1991): 65K10 Correspondence to: P. Zellini     

Variational conditions with smooth constraints: structure and analysis

 This is an expository paper about the analysis of variational conditions over sets defined in finite-dimensional spaces by fairly smooth functions satisfying a constraint qualification. The primary focus is on results that can provide quantitative and computable sensitivity information for particular instances of the problems under study, and our objective is to give a personal view of the state of current knowledge in this area and of gaps in that knowledge that require future work. The writing style is informal, in keeping with the objective of focusing the reader's attention on the basic concepts and the relationships between them, rather than on details of the particular results themselves. Received: December 1, 2002 / Accepted: April 25, 2003 Published online: May 28, 2003 Key words. variational condition – variational inequality – complementarity – sensitivity – stability – nondegeneracy Mathematics Subject Classification (2000): Primary: 90C31. Secondary: 47J20, 49J40, 49J53, 90C33