A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

Optimal 3-terminal cuts and linear programming

Given an undirected graph G=(V,E) and three specified terminal nodes t ₁,t ₂,t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c _e is specified for each e∈E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is -hard, and in fact, is max- -hard. An approximation algorithm having performance guarantee has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most times the optimal LP value. It is proved here that can be improved to , and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee . In addition, we show that is best possible for this algorithm. Research of this author was supported by NSERC PGSB. Research supported by a grant from NSERC of Canada.     

A critical radius for unit Hopf vector fields on spheres

The volume of a unit vector field V of the sphere (n odd) is the volume of its image V() in the unit tangent bundle. Unit Hopf vector fields, that is, unit vector fields that are tangent to the fibre of a Hopf fibration are well known to be critical for the volume functional. Moreover, Gluck and Ziller proved that these fields achieve the minimum of the volume if n = 3 and they opened the question of whether this result would be true for all odd dimensional spheres. It was shown to be inaccurate on spheres of radius one. Indeed, Pedersen exhibited smooth vector fields on the unit sphere with less volume than Hopf vector fields for a dimension greater than five. In this article, we consider the situation for any odd dimensional spheres, but not necessarily of radius one. We show that the stability of the Hopf field actually depends on radius, instability occurs precisely if and only if In particular, the Hopf field cannot be minimum in this range. On the contrary, for r small, a computation shows that the volume of vector fields built by Pedersen is greater than the volume of the Hopf one thus, in this case, the Hopf vector field remains a candidate to be a minimizer. We then study the asymptotic behaviour of the volume; for small r it is ruled by the first term of the Taylor expansion of the volume. We call this term the twisting of the vector field. The lower this term is, the lower the volume of the vector field is for small r. It turns out that unit Hopf vector fields are absolute minima of the twisting. This fact, together with the stability result, gives two positive arguments in favour of the Gluck and Ziller conjecture for small r.     

Critical extreme points of the 2-edge connected spanning subgraph polytope

In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if is a non-integer minimal extreme point of P(G), then G and can be reduced, by means of some reduction operations, to a graph G' and an extreme point of P(G') where G' and satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral. Received: May, 2004 Part of this work has been done while the first author was visiting the Research Institute for Discrete Mathematics, University of Bonn, Germany.     

Ambiguous chance constrained problems and robust optimization

In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set of the distributions is of the form where ρ_p denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prohorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice. Research partially supported by NSF grant CCR-00-09972. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282, and ONR grant N000140310514.     

Partial regularity for stationary harmonic maps at a free boundary

Let and be smooth Riemannian manifolds, of the dimension n≥2 with nonempty boundary, and compact without boundary. We consider stationary harmonic maps u ∈ H¹(, ) with a free boundary condition of the type u(∂) ⊂ Γ, given a submanifold Γ⊂. We prove partial boundary regularity, namely (sing(u))=0, a result that was until now only known in the interior of the domain (see [B]). The key of the proof is a new lemma that allows an extension of u by a reflection construction. Once the partial regularity theorem is known, it is possible to reduce the dimension of the singular set further under additional assumptions on the target manifold and the submanifold Γ.     

The feasibility pump

In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{c^Tx:Ax≥b,x_j integer ∀j ∈ }. Trivially, a feasible solution can be defined as a point x* ∈ P:={x:Ax≥b} that is equal to its rounding , where the rounded point is defined by := x*_j if j ∈ and := x*_j otherwise, and [·] represents scalar rounding to the nearest integer. Replacing “equal” with “as close as possible” relative to a suitable distance function Δ(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.     

An approximation algorithm for the general max-min resource sharing problem

We propose an approximation algorithm for, the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. The algorithm is based on a Lagrangian decomposition method and it uses a c-approximation algorithm (called approximate block solver) for a simpler maximization problem over the convex set B. We show that our algorithm achieves within iterations or calls to the approximate block solver a solution for the general max-min resource sharing problem with approximation ratio The algorithm is faster and simpler than the previous known approximation algorithms for the problem [12, 13] Research of the author was supported in part by EU Thematic Network APPOL, Approximation and Online Algorithms, IST-2001-30012, by EU Project CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems, IST-2001-33135 and by DFG Project, Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs- und überdeckungsprobleme, JA 612/10-1. Part of this work was done while visiting the Department of Computer Science at ETH Zürich. An extended abstract of this paper appeared in SWAT 2004, Scandinavian Workshop on Algorithm Theory, LNCS 3111, 311–322.     

Some remarks on the Hardy-Littlewood maximal function on variable <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> spaces

We show that any pointwise multiplier for BMO(ℝⁿ) generates a function p from the class (ℝⁿ) of those functions for which the Hardy-Littlewood maximal operator is bounded on the variable L^p space. In particular, this gives a positive answer to Diening's conjecture saying that there are discontinuous functions which nevertheless belong to (ℝⁿ).     

A -algorithm for convex minimization

For convex minimization we introduce an algorithm based on -space decomposition. The method uses a bundle subroutine to generate a sequence of approximate proximal points. When a primal-dual track leading to a solution and zero subgradient pair exists, these points approximate the primal track points and give the algorithm's , or corrector, steps. The subroutine also approximates dual track points that are -gradients needed for the method's -Newton predictor steps. With the inclusion of a simple line search the resulting algorithm is proved to be globally convergent. The convergence is superlinear if the primal-dual track points and the objective's -Hessian are approximated well enough. Dedicated to Terry Rockafellar who has had a great influence on our work via strong support for proximal points and for structural definitions that involve tangential convergence. On leave from INRIA Rocquencourt Research of the first author supported by the National Science Foundation under Grant No. DMS-0071459 and by CNPq (Brazil) under Grant No. 452966/2003-5. Research of the second author supported by FAPERJ (Brazil) under Grant No.E26/150.581/00 and by CNPq (Brazil) under Grant No. 383066/2004-2.     

The volumetric barrier for convex quadratic constraints

Let where and _i is an n×n positive semidefinite matrix. We prove that the volumetric and combined volumetric-logarithmic barriers for are and self-concordant, respectively. Our analysis uses the semidefinite programming (SDP) representation for the convex quadratic constraints defining , and our earlier results on the volumetric barrier for SDP. The self-concordance results actually hold for a class of SDP problems more general than those corresponding to the SDP representation of .Mathematics Subject Classification (1991):90C25, 90C30     

Continuity of eigenvalues of subordinate processes in domains

Let X={X_t,t≥0} be a symmetric Markov process in a state space E and D an open set of E. Let S⁽ⁿ⁾={S⁽ⁿ⁾_t, t ≥ 0} be a subordinator with Laplace exponent ϕ_n and S={S_t,t≥0} a subordinator with Laplace exponent ϕ. Suppose that X is independent of S and S⁽ⁿ⁾. In this paper we consider the subordinate processes and and their subprocesses and X^ϕ,D killed upon leaving D. Suppose that the spectra of the semigroups of and X^ϕ,D are all discrete, with being the eigenvalues of the generator of and being the eigenvalues of the generator of X^ϕ,D. We show that, if lim_n→∞ϕ_n(λ)=ϕ(λ) for every λ>0, then The research of this author is supported in part by NSF Grant DMS-0303310. The research of this author is supported in part by a joint US-Croatia grant INT 0302167.     

Newton methods for nonsmooth convex minimization: connections among -Lagrangian, Riemannian Newton and SQP methods

This paper studies Newton-type methods for minimization of partly smooth convex functions. Sequential Newton methods are provided using local parameterizations obtained from -Lagrangian theory and from Riemannian geometry. The Hessian based on the -Lagrangian depends on the selection of a dual parameter g; by revealing the connection to Riemannian geometry, a natural choice of g emerges for which the two Newton directions coincide. This choice of g is also shown to be related to the least-squares multiplier estimate from a sequential quadratic programming (SQP) approach, and with this multiplier, SQP gives the same search direction as the Newton methods. This paper is dedicated to R.T. Rockafellar, on the occasion of his 70th birthday.     

Commutativity of Almost <Emphasis Type="Italic">F</Emphasis>-algebras

Let A be an Archimedean vector lattice, let be its Dedekind completion and let B be a Dedekind complete vector lattice. If Ψ ₀:A × A→ B is a positive orthosymmetric bimorphism, then there exists a positive bimorphism extension Ψ of Ψ ₀ to × in B which is orthosymmetric. This leads to a new and short proof of the commutativity of the almost f-algebras multiplications.     

Conjugacy classes of affine automorphisms of and linear automorphisms of ℙ n in the Cremona groups

We describe the conjugacy classes of affine automorphisms in the group Aut(n,) (respectively Bir()) of automorphisms (respectively of birational maps) of . From this we deduce also the classification of conjugacy classes of automorphisms of ℙⁿ in the Cremona group Bir().     

An estimate on the supremum of a nice class of stochastic integrals and U-statistics

Let a sequence of iid. random variables ξ ₁, . . . ,ξ _n be given on a space with distribution μ together with a nice class of functions f(x ₁, . . . ,x _k ) of k variables on the product space For all f ∈ we consider the random integral J _n,k (f) of the function f with respect to the k-fold product of the normalized signed measure where μ _n denotes the empirical measure defined by the random variables ξ ₁, . . . ,ξ _n and investigate the probabilities for all x>0. We show that for nice classes of functions, for instance if is a Vapnik–Červonenkis class, an almost as good bound can be given for these probabilities as in the case when only the random integral of one function is considered. A similar result holds for degenerate U-statistics, too. Supported by the OTKA foundation Nr. 037886     

Improved complexity results on solving real-number linear feasibility problems

We present complexity results on solving real-number standard linear programs LP(A,b,c), where the constraint matrix the right-hand-side vector and the objective coefficient vector are real. In particular, we present a two-layered interior-point method and show that LP(A,b,0), i.e., the linear feasibility problem A x = b and x ≥ 0, can be solved in in O(n ^2.5 c(A)) interior-point method iterations. Here 0 is the vector of all zeros and c(A) is the condition measure of matrix A defined in [25]. This complexity iteration bound is reduced by a factor n from that for general LP(A, b, c) in [25]. We also prove that the iteration bound will be further reduced to O(n ^1.5 c(A)) for LP(A, 0, 0), i.e., for the homogeneous linear feasibility problem. These results are surprising since the classical view has been that linear feasibility would be as hard as linear programming. This author was supported in part by NSF Grants DMS-9703490 and DMS-0306611     

Analysis of nonsmooth vector-valued functions associated with second-order cones

Let be the Lorentz/second-order cone in . For any function f from to , one can define a corresponding function f^soc(x) on by applying f to the spectral values of the spectral decomposition of x with respect to . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Fréchet differentiability, continuous differentiability, as well as (-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.Mathematics Subject Classification (1991): 26A27, 26B05, 26B35, 49J52, 90C33, 65K05     

On the disconnection of a discrete cylinder by a random walk

We investigate the large N behavior of the time the simple random walk on the discrete cylinder needs to disconnect the discrete cylinder. We show that when d≥2, this time is roughly of order N ^{2 d} and comparable to the cover time of the slice , but substantially larger than the cover timer of the base by the projection of the walk. Further we show that by the time disconnection occurs, a massive ``clogging' typically takes place in the truncated cylinders of height . These mechanisms are in contrast with what happens when d=1.     

Global Solutions to the Two Dimensional Quasi-Geostrophic Equation with Critical or Super-Critical Dissipation

The two dimensional quasi-geostrophic (2D QG) equation with critical and super-critical dissipation is studied in Sobolev space H^s(ℝ²). For critical case (α=), existence of global (large) solutions in H^s is proved for s≥ when is small. This generalizes and improves the results of Constantin, D. Cordoba and Wu [4] for s = 1, 2 and the result of A. Cordoba and D. Cordoba [8] for s=. For s≥1, these solutions are also unique. The improvement for pushing s down from 1 to is somewhat surprising and unexpected. For super-critical case (α ∈ (0,)), existence and uniqueness of global (large) solution in H^s is proved when the product is small for suitable s≥2−2α, p ∈ [1,∞] and β ∈ (0,1].