Resolving degeneracy in combinatorial linear programs: Steepest edge,steepest ascent,and parametric ascent

While variants of the steepest edge pivot rule are commonly used in linear programming codes they are not known to have the theoretically attractive property of avoiding an infinite sequence of pivots at points of degeneracy. An example is presented demonstrating that the steepest edge pivot rule can fail to terminate finitely. It is then shown that a natural extension of the steepest edge pivot rule based on steepest ascent is guaranteed to determine a direction of ascent or a proof that no such direction exists after a finite number of pivots, although without modification the extension may not terminate with an ascent direction corresponding to an edge. Finally, it is demonstrated that a computationally more efficient pivot rule proposed by Magnanti and Orlin has similar theoretical properties to steepest ascent with probability 1independent of the linear program being solved. Unlike alternative methods such as primal lexicographic rules and Bland's rule, the algorithms described here have the advantage that they choose the pivot element without explicit knowledge of the set of all active constraints at a point of degeneracy, thus making them attractive in combinatorial settings where the linear program is represented implicitly.This work was sponsored in part by the National Science Foundation and the Office of Naval Research under NSF grant number DDM-9101578. The author gratefully acknowledges the support of IMSL, Inc.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

Steepest ascent algorithms for nonconical multiple objective programming

A steepest ascent family of algorithms suitable for the direct solution of continuous variable unconstrained nonconical multiple objective programming problems is introduced. Nonconical multiple objective problems, unlike standard (conical) vector optimization problems, cannot be easily solved by examining related single objective problems. The concept of a direction of steepest ascent is generalized to the multiple objective context and the question of algorithmic convergence is treated. A computational example involving a nonconical unanimity order is given.     

求解log—最优组合投资问题的一个自适应算法及其理论分析

本文给出了一个求解log－最优组合投资问题的自适应算法,它是一个变型的随机逼近方法。该问题是一个约束优化问题,因此,采用基于约束流形的梯度上升方向替代常规梯度上升方向,在一些合理的假设下证明了算法的收敛性并进行了渐近稳定性分析。最后,本文将该算法应用于上海证券交易所提供的实际数据的log-最优组合投资问题求解,获得了理想的数值模拟结果。     

An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem

This contribution is focused on an acceleration of branch and bound algorithms for the uncapacitated facility location problem. Our approach is based on the well-known Erlenkotters’ procedures and Körkels’ multi-ascent and multi-adjustment algorithms, which have proved to be the efficient tools for solving the large-sized instances of the uncapacitated facility location problem. These two original approaches were examined and a thorough analysis of their performance revealed how each particular procedure contributes to the computational time of the whole algorithms. These analyses helped us to focus our effort on the most frequent procedures. The unique contribution of this paper is a new dual ascent procedure. This procedure leads to considerable acceleration of the lower bound computation process and reduces the resulting computational time. To demonstrate more efficient performance of amended algorithms we present the results of extensive numerical experiments.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

Efficient group cuts for integer programs

Gomory's group relaxation for integer programs has been refined by column generation methods and dual ascent algorithms to identify a set of candidate solutions which are feasible in the relaxation but not necessarily so in the original integer program. Attempts at avoiding branch and bound procedures at this point have focussed on providing extra group constraints which eliminate all or most of the candidate solutions so that further ascent can take place. It will be shown that a single constraint usually of order 2 or 3, can eliminate all of the candidate solutions.     

Auction algorithms for network flow problems: A tutorial introduction

This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.     

Global Optimization Using Diffusion Perturbations with Large Noise Intensity

This work develops an algorithm for global optimization.The algorithm is of gradient ascent typeand uses random perturbations.In contrast to the annealing type procedurcs,the perturbation noise intensityis large.We demonstrate that by properly varying the noise intensity,approximations to the global maximumcan be achieved.We also show that the expected time to reach the domain of attraction of the global maximum,which can be approximated by the solution of a boundary value problem,is finite.Discrete-time algorithmsare proposed;recursive algorithms with occasional perturbations involving large noise intensity are developed.Numerical examples are provided for illustration.     

A distributed dual ascent algorithm for the Hop-constrained Steiner Tree Problem

The Hop-constrained Steiner Tree Problem is often used to model applications of multicast routing with QoS requirements. This paper introduces a distributed heuristic for the problem based on the application of dual ascent over a graph transformation introduced by Gouveia et al. The proposed algorithm is shown to yield significantly better solutions than the previously known algorithms.     

An exact solution framework for a broad class of vehicle routing problems

This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.     

A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints

In this paper we propose a dual ascent heuristic for solving the linear relaxation of the generalized set partitioning problem with convexity constraints, which often models the master problem of a column generation approach. The generalized set partitioning problem contains at the same time set covering, set packing and set partitioning constraints. The proposed dual ascent heuristic is based on a reformulation and it uses Lagrangian relaxation and subgradient method. It is inspired by the dual ascent procedure already proposed in literature, but it is able to deal with right hand side greater than one, together with under and over coverage. To prove its validity, it has been applied to the minimum sum coloring problem, the multi-activity tour scheduling problem, and some newly generated instances. The reported computational results show the effectiveness of the proposed method.     

A Stochastic Approximation Frame Algorithm with Adaptive Directions

Stochastic approximation problem is to find some root or extremum of a non- linear function for which only noisy measurements of the function are available.The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm,which uses the noisy evaluation of the negative gradient direction as the iterative direction.In order to accelerate the RM algorithm,this paper gives a flame algorithm using adaptive iterative directions.At each iteration,the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions.Two feasible choices of the criterions are pro- posed and two corresponding flame algorithms are formed.Different choices of the directions under the same given switch criterion in the flame can also form different algorithms.We also proposed the simultanous perturbation difference forms for the two flame algorithms.The almost surely convergence of the new algorithms are all established.The numerical experiments show that the new algorithms are promising.     

-adic power series which commute under composition

When two noninvertible series commute to each other, they have same set of roots of iterates. Most of the results of this paper will be concerned with the problem of which series commute with a given noninvertible series. Our main theorem is a generalization of Lubin's result about isogenies of formal groups.

     

A comparison of feasible direction methods for the stochastic transportation problem

The feasible direction method of Frank and Wolfe has been claimed to be efficient for solving the stochastic transportation problem. While this is true for very moderate accuracy requirements, substantially more efficient algorithms are otherwise diagonalized Newton and conjugate Frank–Wolfe algorithms, which we describe and evaluate. Like the Frank–Wolfe algorithm, these two algorithms take advantage of the structure of the stochastic transportation problem. We also introduce a Frank–Wolfe type algorithm with multi-dimensional search; this search procedure exploits the Cartesian product structure of the problem. Numerical results for two classic test problem sets are given. The three new methods that are considered are shown to be superior to the Frank–Wolfe method, and also to an earlier suggested heuristic acceleration of the Frank–Wolfe method.     

A unified framework for primal-dual methods in minimum cost network flow problems

We introduce a broad class of algorithms for finding a minimum cost flow in a capacitated network. The algorithms are of the primal-dual type. They maintain primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional. The manner in which these procedures are combined is flexible thereby allowing the construction of algorithms that can be tailored to the problem at hand for maximum effectiveness. Particular attention is given to methods that incorporate features from classical relaxation procedures. Experimental codes based on these methods outperform by a substantial margin the fastest available primal-dual and primal simplex codes on standard benchmark problems.This work was supported by the National Science Foundation under Contract NSF/ECS 8217668.     

Blind source separation with nonlinear autocorrelation and non-Gaussianity

Blind source separation (BSS) is a problem that is often encountered in many applications, such as biomedical signal processing and analysis, speech and image processing, wireless telecommunication systems, data mining, sonar, radar enhancement, etc. One often solves the BSS problem by using the statistical properties of original sources, e.g., non-Gaussianity or time-structure information. Nevertheless, real-life mixtures are likely to contain both non-Gaussianity and time-structure information sources, rendering the algorithms using only one statistical property fail. In this paper, we address the BSS problem when source signals have non-Gaussianity and temporal structure with nonlinear autocorrelation. Based on the two statistical characteristics of sources, we develop an objective function. Maximizing the objective function, we propose a gradient ascent source separation algorithm. Furthermore, We give some mathematical properties for the algorithm. Computer simulations for sources with square temporal autocorrelation and non-Gaussianity illustrate the efficiency of the proposed approach.     

A dual ascent approach for steiner tree problems on a directed graph

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs. The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.     

Semiparametric mixtures of nonparametric regressions

In this article, we propose and study a new class of semiparametric mixture of regression models, where the mixing proportions and variances are constants, but the component regression functions are smooth functions of a covariate. A one-step backfitting estimate and two EM-type algorithms have been proposed to achieve the optimal convergence rate for both the global parameters and the nonparametric regression functions. We derive the asymptotic property of the proposed estimates and show that both the proposed EM-type algorithms preserve the asymptotic ascent property. A generalized likelihood ratio test is proposed for semiparametric inferences. We prove that the test follows an asymptotic \(\chi ^2\)-distribution under the null hypothesis, which is independent of the nuisance parameters. A simulation study and two real data examples have been conducted to demonstrate the finite sample performance of the proposed model.     

An algorithm for finding the shortest element of a polyhedral set with application to lagrangian duality

An algorithm is developed which finds the point in a compact polyhedral set with smallest Euclidean norm. At each iteration the algorithm requires knowledge of only those vertices of the set which are adjacent to a current reference vertex. This feature is shown to permit the adoption of the technique to find iteratively the shortest subgradient (i.e. the direction of steepest ascent) of the lagrangian dual function for large scale linear programs. Procedures are presented for finding the direction of steepest ascent in both the equality constraint and the inequality constraint cases of lagrangian duality.