Search

For two given measure-preserving functions defined on the unit interval f , g : I → I , the function given by C f , g (u , v) : = λ (f − 1 ([ 0 , u ]) ∩ g − 1 ([ 0 , v ])) is a copula. Although the theoretical problem for constructing this copula is completely solved, in practice it is a rather difficult task. The principal problem is the reverse implication (that is, to prove that f and g are measure-preserving when C f , g is a copula). We provide new proof of this fact with a technique that is far from the previous ones already known in the literature. Indeed, finding two measure-preserving functions f and g , such that C f , g = C , for a given C , is equivalent to a suitable decomposition of such copula in the form C = C f , id ⁎ C id , g (the ⁎ -product), where id denotes the identity function. We also provide explicit algorithms which solve this problem in various contexts such as the measure preserving functions f and g are monotonic, as well as the copula C is a diagonal copula, an extreme copula, an extremal biconic copula, an Archimedean copula, a conic copula, a copula invariant under truncations, or an α -migrative copula. [ABSTRACT FROM AUTHOR]

We give the first correct O(n log n) algorithm for finding a maximum st-flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual s-to-t path. [ABSTRACT FROM AUTHOR]

Relationships between steepest descent lines and gradient extremals on potential surfaces are elucidated. It is shown that gradient extremals are the curves which connect those points where the steepest descent lines have zero curvature. This condition gives rise to a direct method for the global determination of gradient extremals which is illustrated on the Müller–Brown surface. Furthermore, explicit expressions are obtained for the derivatives of the steepest-descent-line curvatures and, from them, for the gradient extremal tangents. With the help of these formulas, a new gradient extremal following algorithm is formulated. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of tracking a solution of a reference parabolic equation by a solution of another equation. A stable algorithm based on the extremal shift method is proposed for this problem. The algorithm is designed to work on a sufficiently large time interval where both equations operate. [ABSTRACT FROM AUTHOR]

Proportional-Integral-Derivative (PID) controller is one of the most widely used controllers for its property of simplicity and practicability. In order to design high-quality performances PID controllers, an Advanced Fireworks (AFW) algorithm based on self-adaption principle and bimodal Gaussian function is proposed, which is built to optimize the PID controller by parameters tuning. Firstly, a compound index of optimization performance is formulated, and then the extremal optimization method of PID control system is proposed. Secondly, a PID parameters tuning model combined with AFW is built. At last, 5 typical transfer functions are simulated to obtain optimal parameters by AFW and contrast tuning method, such as Ziegler-Nichols method, Enhanced Fireworks (EFW) algorithm, and Particle Swarm Optimization (PSO). Simulation results show that AFW are effective and are easily implemented methods to solve PID control problems of different transfer functions. [ABSTRACT FROM AUTHOR]

Abstract: Binary optimal codes often contain optimal or near-optimal subcodes. In this paper we show that this is true for the family of self-dual codes. One approach is to compute the optimum distance profiles (ODPs) of linear codes, which was introduced by Luo et al. (2010). One of our main results is the development of general algorithms, called the Chain Algorithms, for finding ODPs of linear codes. Then we determine the ODPs for the Type II codes of lengths up to 24 and the extremal Type II codes of length 32, give a partial result of the ODP of the extended quadratic residue code of length 48. We also show that there does not exist a subcode of for , and we find a first example of a doubly-even self-complementary code. [Copyright &y& Elsevier]

In this article we propose an exact efficient simulation algorithm for the generalized von Mises circular distribution of order two. It is an acceptance-rejection algorithm with a piecewise linear envelope based on the local extrema and the inflexion points of the generalized von Mises density of order two. We show that these points can be obtained from the roots of polynomials and degrees four and eight, which can be easily obtained by the methods of Ferrari and Weierstrass. A comparative study with the von Neumann acceptance-rejection, with the ratio-of-uniforms and with a Markov chain Monte Carlo algorithms shows that this new method is generally the most efficient. [ABSTRACT FROM AUTHOR]

We consider the real ε-pseudospectrum of a real square matrix, which is the set of eigenvalues of all real matrices that are ε-close to the given matrix, where closeness is measured in either the 2-norm or the Frobenius norm. We characterize extremal points and compare the situation with that for the complex ε-pseudospectrum. We present differential equations for rank-1 and rank-2 matrices for the computation of the real pseudospectral abscissa and radius. Discretizations of the differential equations yield algorithms that are fast and well suited for sparse large matrices. Based on these low-rank differential equations, we further obtain an algorithm for drawing boundary sections of the real pseudospectrum with respect to both the 2-norm and the Frobenius norm. [ABSTRACT FROM AUTHOR]

We find concrete necessary and sufficient conditions for the existence of contractive completions of Hankel partial contractions of size 4 × 4 in the extremal case. Along the way we introduce a new approach that allows us to solve, algorithmically, the contractive completion problem for 4 × 4 Hankel matrices. As an application, we obtain a concrete example of a partially contractive 4 × 4 Hankel matrix, which does not admit a contractive completion. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, an innovative algorithm of improved EMD (IEMD) has been presented for the analysis of frequency modulation (FM) signals. First, extract the first level extrema and the second level extrema to construct one two-level extrema structure (TLES). Using the locations'' relations between the first level extrema and the second level extrema, what the traditional EMD does for FM signals is determined. The propositions that can help us to judge whether the multi-component can be separated well or not by EMD in practice and then tell us what the EMD will do in practice are deduced. Four cases are presented for decomposition of FM components using EMD. According to these cases, different improved methods are presented to separate the FM components that EMD fails to separate. The least-squares method is used to estimate the phase polynomials of FM components. The orthogonal relations between different components are used to estimate the optimal amplitudes of FM components. Moreover, the performance of EMD is analyzed via the multi-level extrema distribution as well, which can be used in practice for the aforehand judgement. Finally, experiments are given to show our new improved EMD. [Copyright &y& Elsevier]

The currently adopted notion of a tolerance in combinatorial optimization is defined referring to an arbitrarily chosen optimal solution, i.e., locally. In this paper we introduce global tolerances with respect to the set of all optimal solutions, and show that the assumption of nonembededdness of the set of feasible solutions in the provided relations between the extremal values of upper and lower global tolerances can be relaxed. The equality between globally and locally defined tolerances provides a new criterion for the multiplicity (uniqueness) of the set of optimal solutions to the problem under consideration. [ABSTRACT FROM AUTHOR]

We address the multi-period portfolio optimization problem with the constant rebalancing strategy. This problem is formulated as a polynomial optimization problem (POP) by using a mean-variance criterion. In order to solve the POPs of high degree, we develop a cutting-plane algorithm based on semidefinite programming. Our algorithm can solve problems that can not be handled by any of known polynomial optimization solvers. [ABSTRACT FROM AUTHOR]

In this paper we classify all extremal and s-extremal binary self-dual codes of length 38. There are exactly 2744 extremal [38,19,8] self-dual codes, two s-extremal [38,19,6] codes, and 1730 s-extremal [38,19,8] codes. We obtain our results from the use of a recursive algorithm used in the recent classification of all extremal self-dual codes of length 36, and from a generalization of this recursive algorithm for the shadow. The classification of s-extremal [38,19,6] codes permits to achieve the classification of all s-extremal codes with d=6. [ABSTRACT FROM AUTHOR]

Abstract: Trigonometric non-Fourier moment problems arise as a result of various control problem study. In current paper, the extremal solution, i.e. the one with the least -norm is searched for. Proposed is an algorithm that allows to change an infinite system of equations into the linear one with only a finite number of equations. The mentioned algorithm is based on the fact, that in the case of a Fourier moment problem, the extremal solution is periodic and easy to construct. The extremal solution of a non-Fourier moment problem close to a Fourier one is approximated by a sequence of solutions with periodicity disturbed in a finite number of equations. It is proved that this sequence of approximations converges to the desired extremal solution. The paper is concluded with the particular example whose consideration leads to a moment problem elaborated in the first part of the article. [Copyright &y& Elsevier]

Abstract: We give an overview of some properties of Lie algebras generated by at most 5 extremal elements. In particular, for any finite graph Γ and any field K of characteristic not 2, we consider an algebraic variety X over K whose K-points parametrize Lie algebras generated by extremal elements. Here the generators correspond to the vertices of the graph, and we prescribe commutation relations corresponding to the nonedges of Γ. We show that, for all connected undirected finite graphs on at most 5 vertices, X is a finite-dimensional affine space. Furthermore, we show that for maximal-dimensional Lie algebras generated by 5 extremal elements, X is a single point. The latter result implies that the bilinear map describing extremality must be identically zero, so that all extremal elements are sandwich elements and the only Lie algebra of this dimension that occurs is nilpotent. These results were obtained by extensive computations with the Magma computational algebra system. The algorithms developed can be applied to arbitrary Γ (i.e., without restriction on the number of vertices), and may be of independent interest. [Copyright &y& Elsevier]

Abstract: We show that the constructions of extremal Ktsub2,2-free and K 3,3-free graphs cannot be generalized to a similar construction of K s,s -free graphs for . We also give new constructions of extremal K s,t -free graphs for large t. [Copyright &y& Elsevier]

Generalized quantum instruments correspond to measurements where the input and output are either states or more generally quantum circuits. These measurements describe any quantum protocol including games, communications, and algorithms. The set of generalized quantum instruments with a given input and output structure is a convex set. Here, we investigate the extremal points of this set for the case of finite dimensional quantum systems and generalized instruments with finitely many outcomes. We derive algebraic necessary and sufficient conditions for extremality. [ABSTRACT FROM AUTHOR]

We consider a generalization of the well-known domination problem on graphs. The ( soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs. [ABSTRACT FROM AUTHOR]

The article examines the maximum principle and convergence of second order central schemes for scalar hyperbolic conservation laws. It explores the development of a numerical algorithm through nonlinear slope reconstructions with minmod limiters. It further provides a mathematical proof for maximum principle and convergence without reducing the first order at local extrema.

The article examines the asymptotic properties of special types of extremal point configurations called greedy energy points. It states that the extremal point configurations are generated by a greedy algorithm which is an energy minimizing construction. It notes that the behavior of greedy points significantly differs from that of minimal energy points in some situations.

Abstract: Particle swarm optimization (PSO) has received increasing interest from the optimization community due to its simplicity in implementation and its inexpensive computational overhead. However, PSO has premature convergence, especially in complex multimodal functions. Extremal optimization (EO) is a recently developed local-search heuristic method and has been successfully applied to a wide variety of hard optimization problems. To overcome the limitation of PSO, this paper proposes a novel hybrid algorithm, called hybrid PSO–EO algorithm, through introducing EO to PSO. The hybrid approach elegantly combines the exploration ability of PSO with the exploitation ability of EO. We testify the performance of the proposed approach on a suite of unimodal/multimodal benchmark functions and provide comparisons with other meta-heuristics. The proposed approach is shown to have superior performance and great capability of preventing premature convergence across it comparing favorably with the other algorithms. [Copyright &y& Elsevier]

Abstract  We provide an optimal algorithm for the problem of augmenting an outerplanar graph G by adding a minimum number of edges in such a way that the augmented graph G′ is outerplanar and 2-connected. We also solve optimally the same problem when instead we require G′ to be 2-edge-connected. [ABSTRACT FROM AUTHOR]

Abstract: The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the renowned Szemerédi Regularity Lemma [Szemerédi, E., Regular partitions of graphs, Colloques Internationaux C.N.R.S. No: 260 – Problèmes Combinatoires et Théorie des Graphes, Orsay (1976), 399–401] in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partitioning given by Cooper [Cooper, J., A permutation regularity lemma, The Electronic Journal of Combinatorics 13 (2006), 20pp.], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence. [Copyright &y& Elsevier]

We consider auctions in which the winning bid is the smallest bid that is unique. Only the upper-price limit is given. Neither the number of participants nor the distribution of the offers are known, so that the problem of placing a bid to win with maximum probability looks, a priori, ill-posed. Indeed, the essence of the problem is to inject a (final) minimum into a random subset (of unique offers) of a larger random set. We will see, however, that here no more than two external (and almost compelling) arguments make the problem meaningful. By appropriately modeling the relationship between the number of participants and the distribution of the bids, we can then maximize our chances of winning the auction and propose a computable algorithm for placing our bid. [ABSTRACT FROM AUTHOR]

A geometric method is described to characterize the different kinds of extremals in optimal control theory. This comes from the use of a presymplectic constraint algorithm starting from the necessary conditions given by Pontryagin's Maximum Principle. The algorithm must be run twice so as to obtain suitable sets that once projected must be compared. Apart from the design of this general algorithm useful for any optimal control problem, it is shown how to classify the set of extremals and, in particular, how to characterize the strict abnormality. An example of strict abnormal extremal for a particular control-affine system is also given. [ABSTRACT FROM AUTHOR]

Lattice reduction is a geometric generalization of the problem of computing greatest common divisors. Most of the interesting algorithmic problems related to lattice reduction are NP-hard as the lattice dimension increases. This article deals with the low-dimensional case. We study a greedy lattice basis reduction algorithm for the Euclidean norm, which is arguably the most natural lattice basis reduction algorithm because it is a straightforward generalization of an old two-dimensional algorithm of Lagrange, usually known as Gauss' algorithm, and which is very similar to Euclid's gcd algorithm. Our results are twofold. From a mathematical point of view, we show that up to dimension four, the output of the greedy algorithm is optimal: The output basis reaches all the successive minima of the lattice. However, as soon as the lattice dimension is strictly higher than four, the output basis may be arbitrarily bad as it may not even reach the first minimum. More importantly, from a computational point of view, we show that up to dimension four, the bit-complexity of the greedy algorithm is quadratic without fast integer arithmetic, just like Euclid's gcd algorithm. This was already proved by Semaev up to dimension three using rather technical means, but it was previously unknown whether or not the algorithm was still polynomial in dimension four. We propose two different analyzes: a global approach based on the geometry of the current basis when the length decrease stalls, and a local approach showing directly that a significant length decrease must occur every O(1) consecutive steps. Our analyzes simplify Semaev's analysis in dimensions two and three, and unify the cases of dimensions two to four. Although the global approach is much simpler, we also present the local approach because it gives further information on the behavior of the algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm’s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables. [Copyright &y& Elsevier]

In this paper we consider finite families F of real n×n matrices. In particular, we focus on the computation of the joint spectral radius ρ(F) via the detection of an extremal norm in the class of complex polytope norms, whose unit balls are balanced complex polytopes with a finite essential system of vertices. Such a finiteness property is very useful in view of the construction of efficient computational algorithms. More precisely, we improve the results obtained in our previous paper [N. Guglielmi, F. Wirth, and M. Zennaro, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 721- 743], where we gave some conditions on the family F which are sufficient to guarantee the existence of an extremal complex polytope norm. Unfortunately, they exclude unnecessarily many interesting cases of real families. Therefore, here we relax the conditions given in our previous paper in order to provide a more satisfactory treatment of the real case. [ABSTRACT FROM AUTHOR]

Abstract: In this note, it is shown that every graph with no -minor is -list-colorable. We also give an extremal function for the existence for a -minor. Our proof implies that there is a linear time algorithm for showing that either has a -minor or is -choosable. In fact, if the latter holds, then the algorithm gives rise to a -list-coloring. [Copyright &y& Elsevier]

The notion of fractional parameter was introduced. Its relation with the notion of fuzzy classification was demonstrated. A procedure was proposed for constructing the dependence measure of such parameters. An algorithm for extremal grouping (classification) of the fractional parameters was developed. [ABSTRACT FROM AUTHOR]

Present and future supercomputers offer many opportunities and advantages to attack complex and demanding industrial and applied mathematical problems, but provide also new challenges. In the Peta-Flops regime, these concern both, the way to exploit the increasingly available power and the need of designing algorithms which are scalable and fault-tolerant at the same time. An example of a probabilistic domain decomposition method, which is indeed scalable and naturally fault-tolerant, is presented. Grid computing should also be mentioned as an increasingly popular way to perform massively distributed computing: it represents a way to exploit computing power, aside the existing supercomputers. Beyond classical supercomputers there is the prospective quantum computer, in view of which it is advisable to start now a search for suitable algorithms for certain classes of problems. [ABSTRACT FROM AUTHOR]

The aim of this article is to present algorithms to compute the firstconjugate time along a smooth extremal curve, where the trajectoryceases to be optimal. It is based on recent theoretical developmentsof geometric optimal control, and the article contains a reviewof second order optimality conditions.The computations are related to a testof positivity of the intrinsic second order derivative or a test ofsingularity of the extremal flow. We derive an algorithm called COTCOT(Conditions of Order Two and COnjugate Times), available on the web,and apply it to the minimal time problem of orbit transfer, and to theattitude control problem of a rigid spacecraft.This algorithm involves both normal and abnormal cases. [ABSTRACT FROM AUTHOR]

In this paper, we present a useful bicriteria model for analyzing the time–cost tradeoffs that can be achieved when undertaking a project consisting of a single task. Some related mathematical results are also presented. The model assumes that several different processes may be used to undertake the task, defining different operating modes, and also assuming that managers may change the process in use after the task is started, depending on the way the task is developing. The model is easy to use, and it can be applied to a large number of real-life situations when the objectives are to minimize cost and time. We present some ideas for an algorithm aimed at identifying sets of relevant strategies from which the decision-maker may choose a suitable strategy. We also present several mathematical properties that may be useful for such an algorithm. [ABSTRACT FROM AUTHOR]

A thin perforated plate with square symmetry is considered in the optimization context of finding the hole shapes which maximize the effective elastic moduli of the structure. In the literature, this is usually considered as a single-criterion problem when either of the moduli is optimized independently of the others. Here, we focus on the more realistic bi-criteria problem of optimizing the bulk modulus and the first shear modulus together. By combining the genetic algorithm (GA) with the weighted sums (WS) scheme, the set of Pareto optimal moduli is found numerically in the general case of interacting holes, even near the percolation limit. The GA part of the proposed approach was previously used by the author to separately optimize the shear and Young effective moduli in perforated plates. [ABSTRACT FROM AUTHOR]

Parametric control for market economy mechanisms is studied under the assumption that effective algorithms are chosen from separate extremal problems. [ABSTRACT FROM AUTHOR]

In this paper we study the classical problem of finding disjoint paths in graphs. This problem has been studied by a number of authors both for specific graphs and general classes of graphs. Whereas for specific graphs many (almost) matching upper and lower bounds are known for the competitiveness of on-line algorithms, not much is known about how well on-line algorithms can perform in the general setting. The best results obtained so far use the expansion of a network to measure the algorithm?s performance. We use a different parameter called the routing number that, as we will show, allows more precise results than the expansion. It enables us to prove tight upper and lower bounds for deterministic on-line algorithms. The upper bound is obtained by surprisingly simple greedy-like algorithms. Interestingly, our upper bound on the competitive ratio is even better than the best previous approximation ratio for off-line algorithms. Furthermore, we introduce a refined variant of the routing number and show that this variant allows us, for some classes of graphs, to construct on-line algorithms with a competitive ratio significantly below the best possible upper bound that could be obtained using the routing number or the expansion of a network only. We also show that our on-line algorithms can be transformed into efficient algorithms for the more general unsplittable flow problem. [ABSTRACT FROM AUTHOR]

A new variant of pure random search (PRS) for function optimization is introduced. The basic finite-descent accelerated random search (ARS) algorithm is simple: the search is confined to shrinking neighborhoods of a previous record-generating value, with the search neighborhood reinitialized to the entire space when a new record is found. Local maxima are avoided by including an automatic restart feature which reinitializes the search neighborhood after some number of shrink steps have been performed. One goal of this article is to provide rigorous mathematical comparisons of ARS to PRS. It is shown that the sequence produced by the ARS process converges, with probability one, to the maximum of a continuous objective function faster than that of the PRS process by adjustably large multiples of the time step (Theorem 1). Regarding an infinite-descent (no automatic restart) version of ARS, it is shown that if the objective function satisfies a local nonflatness condition, then the right tails of the distributions of inter-record times are exponentially smaller than those of PRS (Theorem 3). Performance comparisons between ARS, PRS, and three quasi-Newton-type optimization routines are reported in attempting to find extrema of (i) each of a small collection of standard test functions of two variables, and (ii) d -dimensional polynomials with random roots. Also reported is a three-way performance comparison between ARS, PRS, and a simulated annealing algorithm in attempting to solve traveling salesman problems. [ABSTRACT FROM AUTHOR]

Examines the linear and nonlinear inverse problems of active control of acoustic fields in regular three-dimensional waveguides. Discussion on the setting of the direct problem of sound radiation; Formula for potential energy in a given domain of the waveguide; Description of algorithms used in settings of inverse extremal problems.

We present a class of generalized Cheney--Loeb--Dinkelbach-type (i.e. DC-type) algorithms, together with the problems they solve, and discuss convergence properties. Our algorithms. which are as simple as the DC one, are applicable to classes of programs larger than fractional. In two particular cases, the first being an essentially max-min problem and the second a Pareto extremum, we prove 1.61 and second order convergence respectively. Applications are given to extended fractional max-min and fractional Pareto extremum problems. [ABSTRACT FROM AUTHOR]

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP-hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items. [ABSTRACT FROM AUTHOR]

This work considers some methods for searching for the absolute (global) minimum of functions having concave minorants on bounded convex sets. Special methods for minimizing Lipschitz and concave functions are proposed. The methods are based on deeper cuts that use second-order information. The possibility of applying some cutting schemes that solve convex programming problems for the global minimization of concave functions on bounded convex sets is analyzed. A new original class of cuts, and a new method for minimizing concave functions, are presented. The work also considers a new approach for the solution of multi-extremal problems that is different from cutting methods. It is based on the approximation of convex sets by the convex envelopes over the convex hull of a finite number of points. This work comes close to the studies by Tuy [1,8]. [ABSTRACT FROM AUTHOR]

This paper presents the use of surrogate constraints and Lagrange multipliers to generate advanced starting solutions to constrained network problems. The surrogate constraint approach is used to generate a singly constrained network problem which is solved using the algorithm of Glover, Karney, Klingman and Russell [13]. In addition, we test the use of the Lagrangian function to generate advanced starting solutions. In the Lagrangian approach, the subproblems are capacitated network problems which can be solved using very efficient algorithms. The surrogate constraint approach is implemented using the multiplier update procedure of Held, Wolfe and Crowder [16]. The procedure is modified to include a search in a single direction to prevent periodic regression of the solution. We also introduce a reoptimization procedure which allows the solution from the κth subproblem to be used as the starting point for the next surrogate problem for which it is infeasible once the new surrogate constraint is adjoined. The algorithms are tested under a variety of conditions including: large-scale problems, number and structure of the non-network constraints, and the density of the non-network constraint coefficients. The testing clearly demonstrates that both the surrogate constraint and Langrange multipliers generate advanced starting solutions which greatly improve the computational effort required to generate an optimal solution to the constrained network problem. The testing demonstrates that the extra effort required to solve the singly constrained network subproblems of the surrogate constraints approach yields an improved advanced starting point as compared to the Lagrangian approach. It is further demonstrated that both of the relaxation approaches are much more computationally efficient than solving the problem from the beginning with a linear programming algorithm. [ABSTRACT FROM AUTHOR]

This paper is concerned with a linear fractional problem of the form: max[sub x] min[sub y] F(X, Y) = (cX + dY + α)/(fX + gY + β), subject to AX + BY less than or equal to b; X, Y greater than or equal to O. This problem represents a generalization of a problem considered in the literature in which F(X, Y) is assumed to be linear. A number of results for the linear case are extended; and, in particular, it is shown that this fractional max-min problem is equivalent to a quasi-convex programming problem whose optimal solution lies at a vertex of the feasible region. Using these results, we develop an algorithm for solving this problem. The paper concludes with a numerical example. [ABSTRACT FROM AUTHOR]

The objective of this paper is the construction of a branch-and-bound algorithm for computing minimum cost flows in capacitated networks when the cost of passing a flow over an arc is concave. The method is based on the equivalence of the general network flow problem to a network flow problem in a bipartite network of a special form. An optimal flow is found by implicit enumeration of the set of extremal flows in that network. [ABSTRACT FROM AUTHOR]

A table of contents for the issue "Networks" is presented.