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     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

A nonlinear programming algorithm based on non-coercive penalty functions

 We consider first the differentiable nonlinear programming problem and study the asymptotic behavior of methods based on a family of penalty functions that approximate asymptotically the usual exact penalty function. We associate two parameters to these functions: one is used to control the slope and the other controls the deviation from the exact penalty. We propose a method that does not change the slope for feasible iterates and show that for problems satisfying the Mangasarian-Fromovitz constraint qualification all iterates will remain feasible after a finite number of iterations. The same results are obtained for non-smooth convex problems under a Slater qualification condition. Received: September 2000 / Accepted: June 2002 Published online: March 21, 2003 Research partially supported by CAPES, Brazil Research partially supported by CNPq, Brazil, and CONICIT, Venezuela. Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

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     

Corner Polyhedra and their connection with cutting planes

 We review the necessary background on Corner Polyhedra and use this to show how knowledge about Corner Polyhedra and subadditive functions translates into a great variety of cutting planes for general integer programming problems. Experiments are described that indicate the dominance of a relatively small number of the facets of Corner Polyhedra. This has implications for their value as cutting planes. Received: May 24, 2001 / Accepted: August 2002 Published online: March 21, 2003 Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

Adjoining cofinitary permutations (II)

 We construct several forcing models in each of which there exists a maximal cofinitary group, i.e., a maximal almost disjoint group, G≤Sym(ℕ), such that G is also a maximal almost disjoint family in Sym(ℕ). We also ask several open questions in this area in the fourth section of this paper. Received: 25 December 2000 / Revised version: 10 December 2001 Published online: 5 November 2002 Current address:Department of Mathematics, University of Michigan, Ann Arbor, MI, 48109-1109. USA.e-mail: yizhang@umich.edu The author's research on this subject was partially supported by a visiting grant from the Institute Mittag–Leffler, Royal Academy of Science, Sweden and the grant no. 40734 of Academy of Finland. Mathematics Subject Classification (2000): 03E35, 20A15, 20B07, 20B35     

The Douglas problem for parametric double integrals

 Let be a parametric variational double integral and γ ⊂ ℝ ⁿ be a system of several distinct Jordan curves. We prove the existence of multiply connected, conformally parametrized minimizers of spanned in γ by solving the Douglas problem for parametric functionals on multiply connected schlicht domains. As a by-product we obtain a simple isoperimetric inequality for multiply connected -minimizers, and we discuss regularity results up to the boundary which follow from corresponding results for the Plateau problem. Received: 19 April 2002 Mathematics Subject Classification (2000): 49J45, 49Q10, 53A07, 53A10     

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     

Combining search directions using gradient flows

 The efficient combination of directions is a significant problem in line search methods that either use negative curvature, or wish to include additional information such as the gradient or different approximations to the Newton direction. In this paper we describe a new procedure to combine several of these directions within an interior-point primal-dual algorithm. Basically, we combine in an efficient manner a modified Newton direction with the gradient of a merit function and a direction of negative curvature, if it exists. We also show that the procedure is well-defined, and it has reasonable theoretical properties regarding the rate of convergence of the method. We also present numerical results from an implementation of the proposed algorithm on a set of small test problems from the CUTE collection. Received: November 2000 / Accepted: October 2002 Published online: February 14, 2003 Key Words. negative curvature – primal-dual methods – interior-point methods – nonconvex optimization – line searches Mathematics Subject Classification (1991): 49M37, 65K05, 90C30     

Local behavior of an iterative framework for generalized equations with nonisolated solutions

 An iterative framework for solving generalized equations with nonisolated solutions is presented. For generalized equations with the structure , where is a multifunction and F is single-valued, the framework covers methods that, at each step, solve subproblems of the type . The multifunction approximates F around s. Besides a condition on the quality of this approximation, two other basic assumptions are employed to show Q-superlinear or Q-quadratic convergence of the iterates to a solution. A key assumption is the upper Lipschitz-continuity of the solution set map of the perturbed generalized equation . Moreover, the solvability of the subproblems is required. Conditions that ensure these assumptions are discussed in general and by means of several applications. They include monotone mixed complementarity problems, Karush-Kuhn-Tucker systems arising from nonlinear programs, and nonlinear equations. Particular results deal with error bounds and upper Lipschitz-continuity properties for these problems. Received: November 2001 / Accepted: November 2002 Published online: December 9, 2002 Key Words. generalized equation – nonisolated solutions – Newton's method – superlinear convergence – upper Lipschitz-continuity – mixed complementarity problem – error bounds Mathematics Subject Classification (1991): 90C30, 65K05, 90C31, 90C33     

On the capacitated vehicle routing problem

 We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY. Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002 Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

The volume algorithm revisited: relation with bundle methods

 We revise the Volume Algorithm (VA) for linear programming and relate it to bundle methods. When first introduced, VA was presented as a subgradient-like method for solving the original problem in its dual form. In a way similar to the serious/null steps philosophy of bundle methods, VA produces green, yellow or red steps. In order to give convergence results, we introduce in VA a precise measure for the improvement needed to declare a green or serious step. This addition yields a revised formulation (RVA) that is halfway between VA and a specific bundle method, that we call BVA. We analyze the convergence properties of both RVA and BVA. Finally, we compare the performance of the modified algorithms versus VA on a set of Rectilinear Steiner problems of various sizes and increasing complexity, derived from real world VLSI design instances. Received: December 1999 / Accepted: September 2002 Published online: December 19, 2002 Key Words. volume algorithm – bundle methods – Steiner problems Correspondence to: Claudia A. Sagastizábal, e-mail: sagastiz@impa.br     

Generalized Goal Programming: polynomial methods and applications

 In this paper we address a general Goal Programming problem with linear objectives, convex constraints, and an arbitrary componentwise nondecreasing norm to aggregate deviations with respect to targets. In particular, classical Linear Goal Programming problems, as well as several models in Location and Regression Analysis are modeled within this framework. In spite of its generality, this problem can be analyzed from a geometrical and a computational viewpoint, and a unified solution methodology can be given. Indeed, a dual is derived, enabling us to describe the set of optimal solutions geometrically. Moreover, Interior-Point methods are described which yield an $\varepsilon$-optimal solution in polynomial time. Received: February 1999 / Accepted: March 2002 Published online: September 5, 2002 Key words. Goal programming – closest points – interior point methods – location – regression     

Pruning by isomorphism in branch-and-cut

 The paper presents a branch-and-cut for solving (0, 1) integer linear programs having a large symmetry group. The group is used for pruning the enumeration tree and for generating cuts. The cuts are non-standard, cutting integer feasible solutions but leaving the optimal value of the problem unchanged. Pruning and cut generation are performed by backtracking procedures using a Schreier-Sims table for representing the group. Applications to hard set covering problems and to the generation of covering designs and error correcting codes are presented. Received: August 2001 / Accepted: October 2002 Publication online: December 9, 2002 Key Words. branch-and-cut – isomorphism pruning – symmetry     

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     

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     

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.     

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     

The two phase stochastic Stefan problem

 This work is concerned with existence for a stochastic free boundary problem arising in phase transition (the Stefan two phase problem). The existence of an invariant ergodic measure associated with the corresponding transition semigroup P(t) is also proved, together with an integration by parts formula for the generator of P(t). Received: 20 June 2001 / Revised version: 17 June 2002 / Published online: 24 October 2002 Mathematics Subject Classification (2000): 35K35, 35R15, 60H15 Key words or phrases: Stochastic Stefan problem – Invariant measures – Wiener process – Transition semigroup – Kolmogorov operator     

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