Primal and dual convergence of a proximal point exponential penalty method for linear programming

We consider the diagonal inexact proximal point iteration where f(x,r)=c ^T x+r∑exp[(A _i x-b _i )/r] is the exponential penalty approximation of the linear program min{c ^T x:Ax≤b}. We prove that under an appropriate choice of the sequences λ _k , ε _k and with some control on the residual ν ^k , for every r _k →0⁺ the sequence u ^k converges towards an optimal point u ^∞ of the linear program. We also study the convergence of the associated dual sequence μ _i ^k =exp[(A _i u ^k -b _i )/r _k ] towards a dual optimal solution. Received: May 2000 / Accepted: November 2001?Published online June 25, 2002     

Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems

We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ ²ⁿ satisfying y=f(x) and x _i y _i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ ⁿ to ℝ ⁿ . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ ³ⁿ which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ ²ⁿ in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it. Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999     

On the separation of maximally violated mod-k cuts

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min{c ^T x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ ^T Ax≤⌊λ ^T b⌋ for any λ∈{0,1/k,...,(k−1)/k} ^m such that λ ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|²|E ^*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G ^*=(V,E ^*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied. Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999     

Competitive genetic algorithms for the open-shop scheduling problem

For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger solution space, to smaller gaps between the optimal makespan and the lower bounds, and to disappointing results for the algorithms based on the disjunctive graph model. For instance, the best existing branch and bound method cannot solve some 7 ×7 hard instances to optimality, and all published metaheuristics (working by reversing some disjunctions already fixed) do not better than some greedy or steepest-descent heuristics which need a much smaller computational effort. In this context, the intrinsic parallelism of genetic algorithms (GAs) seems well adapted, for detecting global optima disseminated among many quasi-optimal schedules. This paper presents several GAs for the open-shop problem. It is shown that even simple and fast versions can compete with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each individual has a distinct makespan, and a special procedure which reorders every new chromosome. Using problem-specific heuristics, it is possible to design more powerful GAs which give excellent results, even on the hardest benchmarks of the literature: for instance, all hard open instances from Taillard are broken, except one for which the best known solution is improved.     

A priori and universal estimates for global solutions of superlinear degenerate parabolic equations

We prove an a priori estimate and a universal bound for any global solution of the nonlinear degenerate reaction-diffusion equation u _t =Δu ^m +u ^p in a bounded domain with zero Dirichlet boundary conditions. Received: October 1, 2001?Published online: July 9, 2002     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

Solving a class of semidefinite programs via nonlinear programming

In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions. Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002     

A branch and cut approach to the cardinality constrained circuit problem

The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most k edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits, and a branch-and-cut solution approach using these inequalities. Received: April 1998 / Accepted: October 2000?Published online October 26, 2001     

A Note on Graph Pebbling

 We say that a graph G is Class 0 if its pebbling number is exactly equal to its number of vertices. For a positive integer d, let k(d) denote the least positive integer so that every graph G with diameter at most d and connectivity at least k(d) is Class 0. The existence of the function k was conjectured by Clarke, Hochberg and Hurlbert, who showed that if the function k exists, then it must satisfy k(d)=Ω(2 ^d /d). In this note, we show that k exists and satisfies k(d)=O(2 ^2d ). We also apply this result to improve the upper bound on the random graph threshold of the Class 0 property. Received: April 19, 1999 Final version received: February 15, 2000     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

Extension of locally pseudocompact group actions

It is shown that: (1) any action of a Moscow group G on a first countable, Dieudonné complete (in particular, on a metrizable) space X can uniquely be extended to an action of the Dieudonné completion γG on X, (2) any action of a locally pseudocompact topological group G on a b _f -space (in particular, on a first countable space) X can uniquely be extended to an action of the Weil completion on the Dieudonné completion γX of X. As a consequence, we obtain that, for each locally pseudocompact topological group G, every G-space with the b _f -property admits an equivariant embedding into a compact Hausdorff G-space. Furthermore, for each pseudocompact group G, every metrizable G-space has a G-invariant metric compatible with its topology. We also give a direct construction of such an invariant metric. Received: June 22, 2000; in final form: May 22, 2001?Published online: June 11, 2002     

Solving the p-Median Problem with a Semi-Lagrangian Relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem. This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish government, MCYT subsidy dpi2002-03330.     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

Green functions and eigenfunction expansions for the square of the Laplace–Beltrami operator on plane domains

For a certain class of domains Ω⊂ℂ with smooth boundary and Δtilde;_Ω=w ²Δ the Laplace–Beltrami operator with respect to the Poincaré metric ds ²=w(z)^-2 dz dz on Ω, we (1) show that the Green function for the biharmonic operator Δtilde;_Ω ², with Dirichlet boundary data, is positive on Ω×Ω; and (2) obtain an eigenfunction expansion for the operator Δtilde;_Ω, which reduces to the ordinary non-Euclidean Fourier transform of Helgason for Ω=𝔻 (the unit disc). In both cases the proofs go via uniformization, and in (1) we obtain a Myrberg-like formula for the corresponding Green function. Finally, the latter formula as well as the eigenfunction expansion are worked out more explicitly in the simplest case of Ω an annulus, and a result is established concerning the convergence of the series ∑ _ω∈G (1-|ω0|²) ^s for G the covering group of the uniformization map of Ω and 0<s<1. Received: August 21, 2000?Published online: October 30, 2002 RID="*" ID="*"The first author was supported by GA AV CR grants no. A1019701 and A1019005.     

Persistency of linear programming relaxations for the stable set problem

The Nemhauser–Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of other LP formulations have been studied and one may wonder whether any of them has this property as well. We show that any other formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable set polytope.