Random sampling and greedy sparsification for matroid optimization problems

Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Some of this work done at Stanford University, supported by National Science Foundation and Hertz Foundation Graduate Fellowships, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation and Xerox Corporation. Also supported by NSF award 962-4239.     

The node capacitated graph partitioning problem: A computational study

In this paper we consider the problem ofk-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

Deadlock properties of queueing networks with finite capacities and multiple routing chains

Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multiple routing chains. The necessary and sufficient conditions for deadlockfree queueing networks with blocking are provided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing network into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimization computationally expensive. For a special class of topologies, so-calledtandem networks, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks.This work was supported by the National Science Foundation under Grant No. CCR-90-11981.     

Parallel difference schemes with interface extrapolation terms for quasi-linear parabolic systems

In this paper some new parallel difference schemes with interface extrapolation terms for a quasi-linear parabolic system of equations are constructed. Two types of time extrapolations are proposed to give the interface values on the interface of sub-domains or the values adjacent to the interface points, so that the unconditional stable parallel schemes with the second accuracy are formed. Without assuming heuristically that the original boundary value problem has the unique smooth vector solution, the existence and uniqueness of the discrete vector solutions of the parallel difference schemes constructed are proved. Moreover the unconditional stability of the parallel difference schemes is justified in the sense of the continuous dependence of the discrete vector solution of the schemes on the discrete known data of the original problems in the discrete W2(2,1) (Q△) norms. Finally the convergence of the discrete vector solutions of the parallel difference schemes with interface extrapolation terms to the unique generalized solution of the original quasi-linear parabolic problem is proved. Numerical results are presented to show the good performance of the parallel schemes, including the unconditional stability, the second accuracy and the high parallelism.     

Two approaches to optimal routing and admission control in systems with real-time traffic

This paper addresses the problem of routing and admission control of real-time traffic in a queueing system where customers must begin service within given deadlines (or complete service within given deadlines), otherwise they are considered lost. Performance in such systems is measured by the probability a customer is lost. For a system ofK parallel servers with a probabilistic routing and admission control scheme, the problem of the optimal routing and admission control is considered and two approaches are presented. Assuming the availability of a closed-form expression for the probability of loss at each server, the problem is solved under general conditions and properties of the optimal flow allocation are given. However, such closed-form expressions are often unavailable. This motivates a second approach, which involves a gradient-based stochastic optimization algorithm with on-line gradient estimation. The gradient estimation problem for loss probabilities is solved through a recently-developed smoothed perturbation analysis (SPA) technique. The effectiveness of on-line stochastic optimization using this type of gradient estimator is demonstrated by combining the SPA algorithm with a sampling-controlled stochastic optimization algorithm for the aforementioned routing and admission control problem.This work was supported in part by the Office of Naval Research under Contract N00014-87-K-0304, by the Rome Air Development Center under Contract F30602-88-D-0027, by NASA under Contract NAG 2-595, and by the National Science Foundation under Grant EID-92-12122.The authors are grateful to Don Towsley for several contributions to Section 2 and to an anonymous reviewer for pointing out a redundant assumption in the proof of Lemma 2.1.     

Parallel pivotal algorithm for solving the linear complementarity problem

We propose a parallel implementation of the classical Lemke's algorithm for solving the linear complementarity problem. The algorithm is designed for a loosely coupled network of computers which is characterized by relatively high communication costs. We provide an accurate prediction of speedup based on a simple operation count. The algorithm produces speedup nearp, wherep is the number of processors, when tested on large problems as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-84-20963 and DCR-850-21228 and by Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the University of Wisconsin, Madison, Wisconsin.     

Optimal equi-partition of rectangular domains for parallel computation

We present an efficient method for the partitioning of rectangular domains into equi-area sub-domains of minimum total perimeter. For a variety of applications in parallel computation, this corresponds to a load-balanced distribution of tasks that minimize interprocessor communication. Our method is based on utilizing, to the maximum extent possible, a set of optimal shapes for sub-domains. We prove that for a large class of these problems, we can construct solutions whose relative distance from a computable lower bound converges to zero as the problem size tends to infinity. PERIX-GA, a genetic algorithm employing this approach, has successfully solved to optimality million-variable instances of the perimeter-minimization problem and for a one-billion-variable problem has generated a solution within 0.32% of the lower bound. We report on the results of an implementation on a CM-5 supercomputer and make comparisons with other existing codes.This research was partially funded by Air Force Office of Scientific Research grant F496-20-94-1-0036 and National Science Foundation grants CDA-9024618 and CCR-9306807.     

Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem

We introduce a heuristic for the Multi-Resource Generalized Assignment Problem (MRGAP) based on the concepts of Very Large-Scale Neighborhood Search and Variable Neighborhood Search. The heuristic is a simplified version of the Very Large-Scale Variable Neighborhood Search for the Generalized Assignment Problem. Our algorithm can be viewed as a k-exchange heuristic; but unlike traditional k-exchange algorithms, we choose larger values of k resulting in neighborhoods of very large size with high probability. Searching this large neighborhood (approximately) amounts to solving a sequence of smaller MRGAPs either by exact algorithms or by heuristics. Computational results on benchmark test problems are presented. We obtained improved solutions for many instances compared to some of the best known heuristics for the MRGAP within reasonable running time. The central idea of our heuristic can be used to develop efficient heuristics for other hard combinatorial optimization problems as well.     

A three-time-level explicit difference scheme of the second order of accuracy for parabolic equations

The difference schemes of Richardson [1] and of Crank-Nicolson [2] are schemes providing second-order approximation. Richardson's three-time-level difference scheme is explicit but unstable and the Crank-Nicolson two-time-level difference scheme is stable but implicit. Explicit numerical methods are preferable for parallel computations. In this paper, an explicit three-time-level difference scheme of the second order of accuracy is constructed for parabolic equations by combining Richardson's scheme with that of Crank-Nicolson. Restrictions on the time step required for the stability of the proposed difference scheme are similar to those that are necessary for the stability of the two-time-level explicit difference scheme, but the former are slightly less onerous.Translated fromMatematicheskie Zametki, Vol. 60, No. 5, pp. 751–759, November, 1996.This research was supported by the Russian Foundation for Basic Research under grant No. 95-01-00489 and by the International Science Foundation under grants No. N8Q300 and No. JBR100.     

On the number of views of polyhedral terrains

We show that the number of topologically different orthographic views of a polyhedral terrain withn edges isO(n ^5+ɛ ), and that the number of topologically different perspective views of such a terrain isO(n ^8+ɛ ), for any ɛ>0. Both bounds are almost tight in the worst case. The proofs are simple consequences of the recent almost-tight bounds of [11] on the complexity of lower envelopes in higher dimensions. Pankaj Agarwal has been supported by National Science Foundation Grant CCR-91-06514. Micha Sharir has been supported by National Science Foundation Grant CCR-91-22103, and by grants from the U.S.—Israeli Binational Science Foundation, the G.I.F.—the German Israeli Foundation for Scientific Research and Development- and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Weighted median algorithms for L1 approximation

The weighted median problem arises as a subproblem in certain multivariate optimization problems, includingL ₁ approximation. Three algorithms for the weighted median problem are presented and the relationships between them are discussed. We report on computational experience with these algorithms and on their use in the context of multivariateL ₁ approximation.This work was supported in part by National Science Foundation Grant CCR-8713893 and in part by a grant from The City University of New York PSC-CUNY Research Award program.     

On Ekeland＇s Variational Principle for Set-Valued Mappings

In this paper, we derive a general vector Ekeland variational principle for set-valued mappings, which has a dosed relation to εk^0 -efficient points of set-valued optimization problems. The main result presented in this paper is a generalization of the corresponding result in [3].     

Moderate deviations for the quenched mean of the super-Brownian motion with random immigration

Moderate deviations for the quenched mean of the super-Brownian motion with random immigration are proved for 3≤d≤6, which fills in the gap between central limit theorem(CLT)and large deviation principle(LDP).     

Consolidation rates for two interacting systems in the plane

Summary This paper is a sequel of a paper of Cox and Griffeath “diffusive clustering in the two dimensional voter model”. We continue our study of the voter model and coalescing random walks on the two dimensional integer lattice. Some exact asymptotics concerning the rate of clustering in the former process and the coalescence rate of the latter are derived. We use these results to prove a limit law, announced in that earlier paper, concerning the size of the largest square centered at the origin which is of solid color at a large time t. Partially supported by the National Science Foundation under Grant DMS-831080 Partially supported by the National Science Foundation under Grant DMS-841317 Partially supported by the National Science Foundation under Grant DMS-830549     

On the convergence of Newton iterations to non-stationary points

We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, the interaction between the Newton direction and the merit function can prevent the iterates from escaping such non-stationary points. The unconstrained minimization problem is also studied, and conditions under which false convergence cannot occur are presented. Several examples illustrating failure of Newton iterations for constrained optimization are also presented. The paper also shows that a class of line search feasible interior methods cannot exhibit convergence to non-stationary points. This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported by Department of Energy grant DE-FG02-87ER25047-A004.This author was supported by National Science Foundation grant CCR-9987818 and Department of Energy grant DE-FG02-87ER25047-A004.     

A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

FRACTOP: A Geometric Partitioning Metaheuristic for Global Optimization

We propose a new metaheuristic, FRACTOP, for global optimization. FRACTOP is based on the geometric partitioning of the feasible region so that search metaheuristics such as Simulated Annealing (SA), or Genetic Algorithms (GA) which are activated in smaller subregions, have increased reliability in locating the global optimum. FRACTOP is able to incorporate any search heuristic devised for global optimization. The main contribution of FRACTOP is that it provides an intelligent guidance (through fuzzy measures) in locating the subregion containing the global optimum solution for the search heuristics imbedded in it. By executing the search in nonoverlapping subregions, FRACTOP eliminates the repetitive visits of the search heuristics to the same local area and furthermore, it becomes amenable for parallel processing. As FRACTOP conducts the search deeper into smaller subregions, many unpromising subregions are discarded from the feasible region. Thus, the initial feasible region gains a fractal structure with many space gaps which economizes on computation time. Computational experiments with FRACTOP indicate that the metaheuristic improves significantly the results obtained by random search (RS), SA and GA.     

Additive Schwarz Methods for Elliptic Mortar Finite Element Problems

Summary. Two variants of the additive Schwarz method for solving linear systems arising from the mortar finite element discretization on nonmatching meshes of second order elliptic problems with discontinuous coefficients are designed and analyzed. The methods are defined on subdomains without overlap, and they use special coarse spaces, resulting in algorithms that are well suited for parallel computation. The condition number estimate for the preconditioned system in each method is proportional to the ratio H/h, where H and h are the mesh sizes, and it is independent of discontinuous jumps of the coefficients. For one of the methods presented the choice of the mortar (nonmortar) side is independent of the coefficients.This work has been supported in part by the Norwegian Research Council, grant 113492/420This work has been supported in part by the National Science Foundation, grant NSF-CCR-9732208 and in part by the Polish Science Foundation, grant 2P03A02116 Mathematics Subject Classification (2000):65N55     

Feasible directions algorithms for optimization problems with equality and inequality constraints

In this paper two algorithms, of the feasible-directions and dual feasible-directions type, are presented for optimization problems with equality and inequality constraints. An associated problem, having only inequality constraints, is defined, and shown to be equivalent to the original problem if a certain parameter is sufficiently large. The algorithms solve the associated problem, but incorporate a method for automatically increasing this parameter in order to ensure global convergence to a solution to the original problem. Any feasible directions algorithm can be similarly modified to enable it to handle equality constraints.Research sponsored by the US Army Research Office — Durham, Contract DAHCO4-73-C-0025 and the National Science Foundation Grant GK-37572.