A survey on the continuous nonlinear resource allocation problem

Michael Patriksson^{∗}

June 30, 2006

Abstract

Our problem of interest consists of minimizing a separable, convex and differentiable function over a convex set, defined by bounds on the variables and an explicit constraint described by a separable convex function. Applications are abundant, and vary from equilibrium problems in the engineering and economic sciences, through resource allocation and balancing problems in manufacturing, statistics, military operations research and production and financial economics, to subproblems in algorithms for a variety of more complex optimization models. This paper surveys the history and applications of the problem, as well as algorithmic approaches to its solution. The most common techniques are based on finding the optimal value of the Lagrange multiplier for the explicit constraint, most often through the use of a type of line search procedure. We analyze the most relevant references, especially regarding their originality and numerical findings, summarizing with remarks on possible extensions and future research.

1 Introduction and motivation

1.1 The problem at hand

Suppose that for j = 1, …, n the functions ϕ_{j} : ℝ → ℝ and g_{j} : ℝ → ℝ are convex and differentiable and that −∞ ≤ l_{j} < u_{j} ≤ +∞ holds. Let b ∈ ℝ. Our problem has the following general statement:

minimize_{x} ϕ(x) := ∑_{j=1}^{n} ϕ_{j}(x_{j}),  (1a)

subject to g(x) := ∑_{j=1}^{n} g_{j}(x_{j}) ≤ b,  (1b)
x_{j} ∈ X_{j} := [l_{j}, u_{j}], j = 1, …, n.  (1c)

Let X ⊂ ℝ^{n} denote the (convex) feasible set of the problem (1). The problem has a finite optimal solution if, for example, X is bounded or if each function ϕ_{j} is such that ϕ_{j}(x_{j}) → +∞ whenever x_{j} → ±∞; it is moreover unique if the functions ϕ_{j} are strictly convex.

Applications where this mathematical model can be found are wide-spread. Before providing a short list for a quick flavour, we must make an important comment, however: We consider as (almost) equivalent the problem where the “≤”-constraint (1b) has been replaced by a “=”-constraint; the motivation is that in practice we expect the only explicit constraint to be active at an optimal solution. (If we solve the problem (1) while disregarding the constraint (1b), we either find an optimal solution to the original problem (if feasible) or we learn that every optimal solution must fulfil (1b) with equality.) By the same token, we will sometimes assume that the optimal value of the Lagrange multiplier μ for the explicit constraint (1b) is positive.

1.2 Example applications

1.2.1 Euclidean projection

Let ϕ_{j}(x_{j}) := \frac{1}{2}(x_{j} − y_{j})^{2}, j = 1, …, n, where y ∈ ℝ^{n} is a given vector. The resulting instance of the problem (1) is that of finding the vector of X nearest to y, that is, the problem of finding the projection of the vector y onto X. This problem arises in plenty of applications, especially as a subproblem. Various projection problems arise in decomposition methods for stochastic programming problems ([RoW88, MuV91, NiZ93]). The case of an explicit linear equality is frequently occurring in applications. A particular feasible set is the simplex, { x ∈ ℝ_{+}^{n} | (1^{n})^{T}x = b }, b > 0. (With b = 1, it is known as the unit, or canonical, simplex.) Solving a projection problem over such a set described by a linear equality constraint and bounded variables has been considered, for example, in matrix updates in quasi-Newton methods ([CaM87]), in gradient projection methods for a class of mathematical programs with equilibrium constraints (MPECs) arising in material and shape optimization problems in structural mechanics ([FJR05]), in subgradient algorithms within right-hand side allocation methods for linear multicommodity network flow problems ([HWC74, KeS77, AHKL80, HKL80, LPS96]), in equilibration procedures for traffic flows ([DaS69, BeG82, DaN89, LaP92, Lot06]), primal feasibility procedures within Lagrangian dual algorithms for classes of integer programs ([KLN00]) and in Lagrangian dual methods for quadratic transportation problems, also known as constrained matrix problems ([BaK78, BaK80, OhK80, OhK81, OhK84, CDZ86, Ven89, ShM90, Ven91, NiZ92]); see further below.

∗Professor in Applied Mathematics, Department of Mathematics, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden. E-mail: mipat@math.chalmers.se

The problem of projecting a vector onto a halfspace (that is, the case { x ∈ ℝ^{n} | a^{T}x ≤ b } for some vector a ∈ ℝ^{n}), and the more general case of projecting a vector onto a level set { x ∈ ℝ^{n} | g(x) ≤ b } of some convex function g : ℝ → ℝ, also arises in classic procedures for the feasibility problem. The most famous one is the successive projection method for polyhedral sets known as the Agmon–Motzkin– Schoenberg algorithm [Agm54, MoS54]. Further examples can be found in the excellent surveys in [BeT89, BaB96, CeZ97]. Such methods can also in some cases be interpreted as subgradient methods for the minimization of a non-differentiable convex function over a closed convex set (e.g., [Gof78]), several methods for which also use projections onto level sets of convex functions or surrogate linearized subgradient inequalities (as in “poor man’s bundle methods”); see, for example, the level methods in [LNN95, Kiw96a, Kiw96b], references found therein, and [Bra93, pp. 61–78].

1.2.2 Portfolio selection

Let b = 1, θ ≥ 0, and for all j let ϕ_{j}(x_{j}) := \frac{q_{j}}{2} x_{j}^{2} − θr_{j}x_{j}, q_{j} > 0; g_{j}(x_{j}) := x_{j}; and l_{j} := 0. The resulting problem with the “≤”-constraint replaced by a “=”-constraint is to

minimize_{x} ∑_{j=1}^{n} \frac{q_{j}}{2} x_{j}^{2} − θr_{j}x_{j},  (2a)

subject to ∑_{j=1}^{n} x_{j} = 1,  (2b)
x_{j} ∈ [0, u_{j}],  j = 1, …, n,  (2c)

where x ∈ ℝ^{n} is a vector of asset holdings (in portions of the total budget which are further upper bounded by u_{j} for each asset), the matrix of diagonal elements q_{j} represents a diagonal approximation of the positive definite matrix Q ∈ ℝ^{n×n} of covariances, while r ∈ ℝ^{n} is the vector of expected asset returns. This then is a separable approximation of the classic Markowitz [Mar52, Mar59] portfolio optimization model; references to the model (2) include [Sha63, Sto73, Jud75, EGP76, Pan80, DFL86].

1.2.3 Resource allocation models in production economics

Let b > 0. For all j let c_{j} > 0, b_{j} ∈ ℝ, ϕ_{j}(x_{j}) := c_{j}/x_{j} + b_{j}x_{j}, and g_{j}(x_{j}) := a_{j}x_{j}, a_{j} > 0, and hence consider the problem to

minimize_{x} ∑_{j=1}^{n} c_{j}/x_{j} + b_{j}x_{j},  (3a)

subject to ∑_{j=1}^{n} a_{j}x_{j} ≤ b,  (3b)
x_{j} ∈ [l_{j}, u_{j}],  j = 1, …, n.  (3c)

We mention two typical instances of this model. In the lot sizing problem we let, for each j, x_{j} denote the order quantity of item j, c_{j} be its holding cost, b_{j} the ordering (or, replenishment) cost, a_{j} the storage requirement per item, and b the storage capacity. With this interpretation the problem is a lot sizing problem with a capacity constraint for a multi-item system; cf. [Bec52, CAA71, Zie82, VeK88]. (Without the capacity constraint, a classic solution, often called Wilson’s formula, or the economic order quantity (EOQ) formula, was given already by Harris [Har13, Har15]; see also [Wil34, WaW58, HaW63].) Letting a_{j} = 1 and b_{j} = 0 for all j and replacing “≤” with “=” in the constraint (3b) we obtain the subproblem of a hierarchical production planning problem considered by Bitran and Hax [BiH77]. In this case, the problem is that of finding an optimal EOQ at the lower level of a hierarchical problem that defines the right-hand side b of the items in a given class, and the bounds defining X_{j} are obtained from forecasts of future demand, the current inventory, the safety stock, and the overstock limit. In [BiH79, BiH81] they consider objective functions of the form (3a) where labour costs are included also.

Additional references on resource allocation problems are found in [Zip80b, IbK88, PaK90, MaK93, BSSW94].

1.2.4 Optimum allocation in stratified sampling

The concept of optimum allocation in stratified sampling was introduced in [Ney34]. In this fundamental problem in statistics we are interested in estimating the average of a certain quantity among large populations. Since it is infeasible to examine the entire population M, we have to make an estimation on the basis of a small number of samples. For this purpose the population is stratified into n strata, each of which having a population M_{j}, and from which x_{j} samples are chosen.

The problem of minimizing the variance of the estimate is that to

minimize_{x} ∑_{j=1}^{n} ω_{j}^{2} \frac{(M_{j} − x_{j})σ_{j}^{2}}{(M_{j} − 1)x_{j}} ,  (4a)

subject to ∑_{j=1}^{n} x_{j} = b,  (4b)
x_{j} ≥ 1,  j = 1, …, n,  (4c)

where ω_{j} = M_{j}/M, σ_{j}^{2} is an appropriate estimate of the variance in each strata, and we choose a total sample size specified to a positive integer b and such that at least one sample is taken from each strata.

In this problem, the total sample is to be allocated to the strata so as to secure a minimum variance of the global estimate. Alternatively, we may determine the smallest sample necessary to control the variance of the global estimate at a specified level.

This problem is taken up and extended in [Sri63, San71, BRS99].

1.3 Motivation and outline

As will be evidenced by the example algorithms to be presented, an optimal solution to the problem (1) can in many cases most simply be generated by finding the optimal value of a single variable, namely the Lagrange multiplier associated with the constraint (1b). Two facts have attributed to the existence of many such algorithmic developments and analyses: the problem is, as seen above and in the next section, quite diverse in its applications, and the algorithms are often quite simple and elegant. In the preface to their book on resource allocation Ibaraki and Katoh [IbK88, p. xiii] claim that the first paper on the subject appeared in 1953 ([Koo53]), and then also state:

It is also observed that similar algorithms have been recurrently proposed in the literature, perhaps because of their simplicity of structure and the diversity of their applications. In view of this, it appears timely to summarize the past thirty years of achievement. This motivated us to write this book.

Since the publication of the above-mentioned book the development of algorithms for the continuous allocation problem have not stalled but instead increased in intensity, and it is still true that algorithms are recurrently proposed. It is therefore again timely to summarize this development, especially that since the mid 1980s. Further, while it might in general be said that annotated bibliographies are going out of fashion because of the development of electronically available and searcheable citation indexes, many relevant publications both prior to and after the publication of the book [IbK88] cannot be found in such indexes at all and several others at least not in mathematical ones. Related of course to all of the above, the reference lists of the recent papers do not correctly reflect the methodological and applicational development of the past decades.

In the next section we trace some of the history of the problem’s appearance and its many applications. Upon the characterizations and properties of the primal problem (1), its Karush–Kuhn–Tucker conditions and its Lagrangian dual formulation, in Section 3 we build the two most important algorithmic constructs and discuss their merits. We then collect the references in the area in annotated bibliographies, one for each of the two main algorithm frameworks, and in the process not only adding to the most important ones from the monograph [IbK88] with the last 20 years of research output but also tracing earlier developments not found therein. We summarize the lists of articles by giving remarks on their originality, numerical findings and visible patterns of research, followed by remarks on possible future developments.

2 History and additional applications

2.1 The theory of search and equilibria in special games

Our first examples have a diverse set of independent roots, but all of them are associated with various equilibrium concepts.

2.1.1 Gibbs’ Lemma and equilibrium in thermodynamics

The first example problem is the earliest one that is general enough and sufficiently well studied to be a candidate for providing an original reference to our problem (1).

Consider the following instance of (1):

minimize_{x}  ∑_{j=1}^{n} ϕ_{j}(x_{j}),  (5a)

subject to ∑_{j=1}^{n} x_{j} = b,  (5b)
x_{j} ≥ 0,  j = 1, …, n.  (5c)

Lemma 1 (Gibbs’ Lemma) Suppose that x^{∗} solves the problem (5). Then, there exists (at least one) μ^{∗} ∈ ℝ such that

ϕ′_{j}(x_{j}^{∗}) \begin{cases}= −μ^{∗}, & if x_{j}^{∗} > 0, \\ ≥ −μ^{∗}, & if x_{j}^{∗} = 0, \end{cases}  j = 1, …, n,  (6)

holds.

Proof. Thanks to the linearity of the constraints, the problem satisfies the Abadie constraint qualification and the Karush–Kuhn–Tucker conditions are necessary for the local optimality of x^{∗}. Introducing the multiplier μ for the equality constraint and λ_{j} ≥ 0 for the sign condition on x_{j}, we obtain the Lagrange function L(x, μ, λ) := bμ + ∑_{j=1}^{n}(ϕ_{j}(x_{j}) + [μ − λ_{j}]x_{j}). Suppose then that the triple (x^{∗}, μ^{∗}, λ^{∗}) ∈ ℝ^{n} × ℝ × ℝ_{+}^{n} is a Karush–Kuhn–Tucker point. Setting the partial derivatives of L with respect to each x_{j} to zero yields

ϕ′_{j}(x_{j}^{∗}) = λ_{j}^{∗} − μ^{∗},  j = 1, …, n.  (7)

Further, the complementarity conditions state that

λ_{j}^{∗} · x_{j}^{∗} = 0, j = 1, …, n.

For a j with x_{j}^{∗} > 0 we must therefore have from (7) that ϕ′_{j}(x_{j}^{∗}) = −μ^{∗}. Suppose instead that x_{j}^{∗} = 0. Then, since λ_{j}^{∗} ≥ 0 must hold, we obtain from (7) that ϕ′_{j}(x_{j}^{∗}) = λ_{j}^{∗} − μ^{∗} ≥ −μ^{∗}, and we are done.

The name “Gibbs’ Lemma” was coined by John M. Danskin [Dan67, p. 10]; Gibbs’ Lemma is named after the 19^{th} century scientist J. Willard Gibbs, one of the great scholars of the century, and provider of outstanding work in thermodynamics including pioneering work on statistical mechanics. In his long paper “On the equilibrium of heterogeneous substances” [Gib1876, Gib1878a, Gib1878b]^{1} Gibbs formulated a principle for the equilibrium state of chemical substances, such as gas, in actual physical contact with each other. Gibbs’ Lemma stems from an equilibrium in a kind of game, wherein the system simultaneously strives for a maximum entropy and a minimum energy. His principle is formulated in words thus:^{2}

1At home, at dinner, Gibbs would often offer to prepare the salad by saying that he was the world’s recognized expert on the mixture of heterogeneous substances ([Meh98]).

2This passage is found on page 56 in the 1961 Dover reprinted version of [Gib1876].

I. For the equilibrium of any isolated system it is necessary and sufficient that in all possible variations of the state of the system which do not alter its energy, the variation of its entropy shall either vanish or be negative.

II. For the equilibrium of any isolated system it is necessary and sufficient that in all possible variations of the state of the system which do not alter its entropy, the variation of its energy shall either vanish or be positive.

Gibbs’ two principles correspond precisely to the two optimality conditions for the Lagrangian of a maximum entropy and minimum energy formulation of the above-mentioned game. Notice however that Gibbs never formulated the two optimization problems formally. The fact that the substances are allowed to be heterogeneous was most important and truly original.

2.1.2 Marginal utility theory

Marginal utility theory in production economics dictates that the only items produced are the ones that have the largest marginal profits; the marginal profits are also equal, and maximal, among all items. Gibbs’ Lemma, rewritten for a maximization version of the problem, provides exactly this conclusion, and the marginal profit moreover equals the (negative of the) value μ^{∗} of the Lagrange multiplier.

This result in utility theory is however older than Gibbs’ Lemma, and is nowadays attributed to the Prussian economist and civil servant Hermann Heinrich Gossen. His work on marginal utility is found in the book [Gos1854] published in German, and much later translated into English in [Gos83] with the title The Laws of Human Relations and the Rules of Human Action Derived Therefrom. The preface reveals that the author wrote in a quite pretentious tone, comparing his work with that of Copernicus in significance; according to the English translation’s introductory essay, written by N. Georgescu-Roegen, neither did his usage of German and mathematics (especially in light of the non-mathematical approaches adopted by contemporary German economists) help him gain an audience. In fact, it was only in the 1870s that his work was rediscovered and appreciated, following discussions among the economists Leon Walras, Carl Menger, and William Stanley Jevons, and then became reformulated in a more intelligible way for the public.

To appreciate the originality of the work of H. H. Gossen and show that Gibbs’ Lemma effectively was analyzed already by him, we cite his two main results (of which the first is of our primary interest); they are, respectively, found in [Gos83, Theorem 1.2, p. 14] (result (a)) and [Gos83, Theorem 7.11, p. 108–109] (result (b)), and [Gos83, Theorem 2.3, p. 53].^{3}

Theorem 2 (Gossen’s Fundamental Theorems) (the optimal allocation of money): (a) In order to maximize his total pleasure, an individual free to choose between several pleasures but whose time is not sufficient to enjoy all to satiety must proceed as follows: However different the absolute magnitudes of the various pleasures might be, before enjoying the greatest pleasure to satiety first all pleasures in part in such a manner that the magnitude [intensity] of each single pleasure at the moment when its enjoyment is broken off shall be the same for all pleasures.

(b) Man obtains the maximum of life pleasure if he allocates all his earned money E between the various pleasures and determines the e in such a manner that the last atom of money spent for each pleasure offers the same amount [intensity] of pleasure.

(the optimal allocation of time): In order to maximize his life pleasure, man must distribute his time and energy among various pleasures in such a way that for every pleasure, the intensity of pleasure of the last atom produced shall be equal to the magnitude [intensity] of the discomfort experienced by him at the very last moment of his expenditure of effort.

Interestingly, his proofs of several of the results in his book [Gos1854] were based on ingenious diagrams, which he was the first to devise; the result in (a) is nowadays normally illustrated with the use of the indifference map but, as pointed out by N. Georgescu-Roegen in [Gos83, p. xci], Gossen’s diagram is better in revealing the relationship between allocation and utility.

2.1.3 Traffic equilibrium

The notion of an equilibrium in a traffic system of individual trip makers seeking a best route from origin to destination was first described and analyzed in mathematical terms by the statistician J. G. Wardrop of the British Road Research Laboratory. Since his seminal paper [War52], the equilibrium conditions are also known as Wardrop’s first principle. As cited from [War52], this is the definition:

3The “[intensity]” brackets constitute the translator’s clarification that we are dealing with derivative values.

The journey times on all the routes actually used are equal, and less than those which would be experienced by a single vehicle on any unused route.

Wardrop’s first principle is usually referred to as the user equilibrium conditions, since they can be related to the individual traveller’s (user’s) cost minimizing behaviour, and to the steady-state which the principle describes and which evolves following trial-and-error route-choice adjustments. Wardrop’s second principle deals with a situation in which the travellers are somehow influenced to choose their routes such that the average travel cost is minimal, that is, the total travel cost is minimal. We refer to such a situation as being a system optimum.

In the mid-1950s, following the publication of the famous Kuhn–Tucker Theorem ([KuT51]) in nonlinear programming, the user equilibrium principle was shown to be the statement of the optimality conditions of a special convex program. This program has variables corresponding to the non-negative volumes x_{j} in the links j of the traffic network as well as disaggregated variables for the flows between different origins and destinations; the objective function is the sum of integrals (with limits zero and x_{j}) of functions for each link, each of which measuring how the cost of travel along a link increases by its volume. The primary classic references for the construction of these convex programs, and the interpretation of their optimality conditions, are Beckmann et al. [BMW55, BMW56]; for more recent expositions, see [She85, Pat94].

In the simplest traffic models, where there is only one origin and one destination, and the links are all parallel (that is, the routes never intersect), the model (5) perfectly represents the above-mentioned convex program. Indeed, let n be the number of links in the network, each function ϕ_{j} be the primitive function corresponding to the travel cost function, and the value of b be the demand of travel between the origin and the destination. Gibbs’ Lemma then corresponds exactly to Wardrop’s first principle, with the value of μ being the cost of travel along each route actually used.

Normally traffic models are much more complex, dealing with several pairs of origin and destination and having non-separable travel cost functions due to the interaction between traffic along neighbouring links in the network, particularly at intersections. (For more details on traffic models, see [She85, Pat94].) However, the simple model discussed above is interesting in that the connection between a user equilibrium in a traffic network and Gibbs’ Lemma was discussed by economists long before the work of Wardrop and Beckmann et al. We summarize this discussion next.

The notion of pricing economic activities in order to obtain a system optimum was introduced into the economics literature by Jules Dupuit [Dup1844, Dup1849]. The argument is that a congested traffic network will perform inefficiently, if users do not pay for their external costs. The concept of marginal cost pricing is therefore sometimes referred to as the process of internalizing the external costs of the users of the traffic network.^{4} This market-based, laissez-faire, pricing policy, in which selfish pursuit of individual objectives result in maximum social benefit, is also the guiding light behind Adam Smith’s Invisible Hand: having removed market imperfections (here, through the pricing of congestion), private pursuit becomes optimal; see Book IV, Chapter II, of The Wealth of Nations [Smi1776].

The total travel cost is generally not minimized by the user optimal travel pattern, as already observed by the economist A. C. Pigou [Pig20]. Pigou provides the following discussion on the difference between the two principles:

Suppose there are two roads ABD and ACD both leading from A to D. If left to itself, traffic would be so distributed that the trouble involved in driving a “representative” cart along each of the two roads would be equal. But, in some circumstances, it would be possible, by shifting a few carts from route B to route C, greatly to lessen the trouble of driving those still left on B, while only slightly increasing the trouble of driving along C. In these circumstances a rightly chosen measure of differential taxation against road B would create an “artificial” situation superior to the “natural” one. But the measure must be rightly chosen.

Notice that Pigou indeed describes a version of Gibbs’ Lemma.

The purpose of Pigou’s statement is to give an example of the consequences of total freedom of companies’ factory investments. Pigou concludes that they would choose to invest in factories with higher marginal investment costs, and that society, by a correctly chosen taxation, can direct the companies to invest more wisely, from the society’s point of view. In this, he has in fact both stated the two route-choice principles and also introduced the principle of congestion pricing.^{5}

The economist F. H. Knight [Kni24] examined Pigou’s example, and explained in more detail the reason for the difference between the two situations. Discussions on pricing issues later became more precise, especially after the optimization models of the two Wardrop conditions appeared in the work by Beckmann et al.; see, for example, [Wal54, Wal61]. Congestion pricing, the related Braess’ Paradox, and the “cost of anarchy”—the difference in total travel cost between the user equilibrium and system optimal flows—is today a hot topic in transportation science (see, e.g., [Rou02, RoT02, CSS04]).

4Traces of such ideas can be found also in von Thünen’s [vTh1826] analysis of agricultural land use.

5However famous Pigou’s discussion has become in transportation science, it is interesting to note that in subsequent editions of the book ([Pig24, Chapters 8 and 10], [Pig29, Chapter 9], [Pig46, Chapters 9 and 11]), Pigou had replaced it with examples from production economics.

2.1.4 The theory of search

Consider the problem to

maximize_{x ∈X} ∑_{j=1}^{n} a_{j} (1 − e^{−b_{j}x_{j}}) ,  (8)

where X := { x ∈ ℝ_{+}^{n} | 1^{T}x = b }, b > 0, a_{j}, b_{j} > 0, j = 1, …, n, which is of the form (5) with a special objective function. This problem was formulated and studied in the context of the US Navy search for enemy vessels in the Atlantic ocean, by Bernard O. Koopman; see [Koo52, Koo53, Koo54, Koo56a, Koo56b, Koo56c, Koo57, Koo79a, Koo79b], and the books [Koo80, Koo99] which contain some of the earliest work done immediately after WWII (e.g., [Koo46]).

The problem has the following interpretation: an object is with probability a_{j} inside box j, and −b_{j} is proportional to the difficulty of searching inside the box. If the searcher spends x_{j} time units looking inside box j then he/she will find the object with probability 1−exp(−b_{j}x_{j}). The problem (8) represents the optimum search strategy if the available time is limited to b time units.

Koopman called his research problem the theory of search, which he invented through his work. In his paper [Koo53] he gave four examples of problems of the form (5):

• Search for a lost object: The above example.

• Distribution of destructive effort: This example is discussed below.

• Response to a sales campaign: in a maximization version of (5) the value of b is the total value spent on the campaign, while ϕ_{j}(x_{j}) denotes the return on an investment x_{j} in a given sector j.

• Drilling for oil: Among n possible drilling sites we wish to select only those that provide the best return, measured in terms of the functions ϕ_{j}; this function is zero at zero, but also at all arguments x_{j} (representing the investment into the operation) that are too small for the operation to yield a sizable drilling.

The book [ORC59] summarizes some then recent developments in operations research made in particular by staff at MIT associated with NATO research activities. (Among the authors we find P. M. Morse and G. E. Kimball.) Koopman (the only non-MIT author, affiliated with Columbia University) wrote two chapters. In his concluding remarks to his chapter “Search” in this collection ([Koo59]) he states the following, showing that he did indeed know of Gibbs’ work and understood the generality of the problem:

The class of problems considered herin is more general than the problems of linear programming, since the expression to be optimized is non-linear and involves integration; it is more special, since only two linear side-conditions are given. If the number of such conditions were increased, much of what has been done here could be extended, although not without going drastically beyond the present chapter. The same is true, with even greater difficulties, if the detection law (or pay-off function) is not of the simple exponential type assumed. For all these extensions, only the general approach of the unilateral variational schemata remains. This approach, while familiar through its use in many similar situations in the present period, actually goes back to the work of Willard Gibbs, who applied it (in the case of finite sums, rather than integrals) in his theory of the equilibrium of heterogeneous substances, an epochal work of the last century. But a much more fundamental question is in order: When can the present methods, or anything like them using the same general approach, have any hope of being applicable? The answer is that the pre-conditions of the present type of approach are that the pay-off P should be \underline{additive} in the separable portions of effort (so that it can be expressed as an integral, in some sufficiently general sense); and, furthermore, that the separate returns of the portions of effort be functions of these portions, together with the local conditions.

He then goes on the present a simple extension of the search problem where separability fails.

In the book “Resource Allocation Problems” by T. Ibaraki and N. Katoh [IbK88], Koopman’s papers [Koo53, Koo56b, Koo56c, Koo57] and the problem (8) represent the first example mentioned in the book, which however has no reference to Gossen or Gibbs.

Charnes and Cooper [ChC58b] and Karush [Kar62] furnished additional theory and a first example algorithm for the problem, respectively; the algorithm of [ChC58b] is based on the Lagrangian dual formulation of (8) while that of [Kar62] is based on dynamic programming. de Guenin [deG61] extends the search algorithm to a general detection probability distribution; further developments in that area for the problem of moving targets are found in, for example, [Zah63, Luk77, Man82]. A book containing many references to optimal search problems and methods is [Sto75], and [PIS02] includes several references to the Russian activities in the theory of search since the 1940s.

2.1.5 A weapons allocation problem

We next consider a similar game but of a different origin than Koopman’s. John M. Danskin [Dan66, Dan67] utilized Gibbs’ Lemma in the investigation of a weapons allocation game of this form:

maximize_{x ∈X} minimum_{y∈Y} ∑_{j=1}^{n} v_{j} (1 − α_{j}e^{−κ_{j}x_{j}/y_{j}})^{y_{j}} ,

where X := { x ∈ ℝ_{+}^{n} | 1^{T}x = b } and Y := { y ∈ ℝ_{++}^{n} | 1^{T}y = c }, all constants b, c, v_{j}, κ_{j} are greater than zero and α_{j} ∈ (0, 1). This game was invented around 1951 at the RAND Corporation to study the following cold war problem: Suppose one side allocates anti-missile defenses to various cities. The other side observes this allocation and then allocates missiles to those cities. The function

ϕ_{j}(x_{j}, y_{j}) := \begin{cases}v_{j} (1 − α_{j}e^{−κ_{j}x_{j}/y_{j}})^{y_{j}} , & if y_{j} > 0, \\ 0, & if y_{j} = 0, \end{cases}

is intended to represent the residual value of a target if it is defended by x_{j} defense units and attacked by y_{j} attack units. The quantity exp(−κ_{j}x_{j}/y_{j}) is the probability that an individual attack unit gets through when x_{j}/y_{j} is the amount of defense against each attack unit, and κ_{j} is the effectiveness of the defense. The value α_{j} is the probability that a missile attack unit destroys the target, the quantity 1 − α_{j} exp(−κ_{j}x_{j}/y_{j}) is the probability that the target survives an individual attack, and, finally, [1 − α_{j} exp(−κ_{j}x_{j}/y_{j})]^{y_{j}} is the probability that the target survives an attack with y_{j} units. In this game, then, the x-player acts first by constructing defenses, and the y-player moves in full knowledge of what the x-player has done.

Danskin especially analyzes the problem for one of the players, namely the problem (8), characterizing its unique optimal solution by means of Gibbs’ Lemma. Here, 1−exp(−b_{j}x_{j}) is the proportionate damage done to target j with a level x_{j} of attack, the value of which is a_{j}, while b_{j} is the vulnerability of target j. The problem (8) then is to maximize damage subject to the availability of weapons. The criterion for attacking target j according to Gibbs’ Lemma is therefore that the product a_{j}b_{j} is larger than some threshold quantity. Through the Lagrangian relaxation of the constraint we can also reach a purely dual problem in the (only) variable μ; Danskin [Dan67, Section II.3] also provides a simple scheme for finding its optimal value through a line search. As we shall see, this technique has a much earlier origin within production economics. More on the Lagrangian relaxation technique and dual line searches will be said in Section 3.1.

Danskin also extends Gibbs’ Lemma to situations where ϕ is neither separable nor differentiable, reaching a Lagrange multiplier rule for the characterization of an optimal solution based on the possible values of the directional derivatives of ϕ in admissible directions.

In related work Danskin also studies the convoy routing and reconneaisance problems (see [Dan62a] and [Dan62b, Dan62c], respectively). According to his recollections in the abstract of [Dan62a] the work of that paper was performed in 1953 for the Operations Evaluations Group of the Navy Department. Interestingly, therein he states Gibbs’ Lemma (albeit without naming it as such), referring the reader to a proof that will be found in his forthcoming “Calculus of Variations and Operations Research”, which however has not materialized; his only other citation in that paper is to the game theory classic [vNe28], so in the open literature it is therefore first in his 1967 book on max–min problems that the lemma is credited to Gibbs.

2.2 An example application arising as a subproblem

The following example, together with the special case following it, illustrates that the problem (1) can arise naturally as a subproblem for important problems when attacked by various decomposition–coordination methods. The technique applied here is Lagrangian relaxation (or, price-directive decomposition) together with dual line search procedures; other general methods that can lead to problems of this form are righthand side allocation (or, resource directive decomposition) (e.g., [HWC74]), Benders decomposition (e.g., [CoL84, AaL90]) and surrogate relaxation. (See the classic references [Eve63, Geo70a, Geo70b, Geo70c, GrP70, Las70] on these techniques.)

2.2.1 Dual ascent methods for convex problems with linear constraints

Consider the convex program to

minimize_{x} ϕ(x),  (9a)
subject to ϵ_{i}^{T}x = d_{i},  i = 1, …, m,  (9b)
x_{j} ∈ X_{j},  j = 1, …, n,  (9c)

where ϕ : ℝ^{n} → ℝ is a convex function of the form (1a), each set X_{j} is of the form in (1c), and for i = 1, …, m ϵ_{i} ∈ ℝ^{n} and d_{i} ∈ ℝ are given data.

To introduce the Lagrangian dual function q we suppose we have at hand a dual vector λ̄ ∈ ℝ^{m}, whence the minimum of the Lagrange function over ∏_{j=1}^{n} X_{j} yields

q(λ̄) := minimum ; x ∈∏_{j=1}^{n} X_{j} {ϕ(x) + ∑_{i=1}^{m} λ̄_{i}(ϵ_{i}^{T}x − d_{i})} .

Note that the minimization problem actually separates into n independent one-variable problems. We suppose that the function q is finite on ℝ^{m}. In order to solve the problem of maximizing this function over ℝ^{m}, we consider a dual ascent procedure, which means that we generate directions of change, p ∈ ℝ^{m}, and that we are interested in solving the line search problem to

maximize_{α≥0} q(λ̄ + αp).  (10)

We will also be looking more specifically at the problem of optimizing q over a specific coordinate direction given the current value λ̄, since such algorithms are quite popular. In that case, p = e_{i}, where e_{i} is the i^{th} unit vector; then, we will also allow α in (10) to become negative.

Suppose that α^{∗} ≥ 0 solves (10). Then, α^{∗} is a Lagrange multiplier in the primal problem to

minimize_{x} {ϕ(x) + λ̄^{T}(Ex − d)} ,  (11a)
subject to p^{T}(Ex − d) ≤ 0,  (11b)
x_{j} ∈ X_{j},  j = 1, …, n,  (11c)

where E is the m × n matrix with rows ϵ_{i}^{T}.

To see this, notice that if α^{∗} solves (10), then, in particular, the minimum value of the Lagrangian function equals q(λ̄ + α^{∗}p). But the Lagrangian function (11) is precisely ϕ(x) + (λ̄ + α^{∗}p)^{T}(Ex − d), whence this equality implies that α^{∗} indeed is the Lagrange multiplier sought.

Notice that the problem (11) is of the form (1).

Let, in particular, now p = e_{i}, the i^{th} unit vector, and so consider the coordinate search problem of maximizing q over λ_{i}, keeping all the other indices fixed at their values at λ̄. Then, the optimal value is λ_{i}^{∗} = λ̄_{i} + α^{∗}, where α^{∗} is a Lagrange multiplier in the problem to

minimize_{x} {ϕ(x) + λ̄^{T}(Ex − d)} ,  (12a)
subject to ϵ_{i}^{T}x = d_{i},  (12b)
x_{j} ∈ X_{j},  j = 1, …, n.  (12c)

In other words, performing a coordinate search in the dual space in the variable λ_{i} amounts to Lagrangian optimally satisfying constraint i in the primal problem. If λ̄ = 0^{m}, then the dual coordinate search is equivalent to solving a relaxation of the original problem (9), where only constraint i in (9b) is present.

The last result is not surprising at all; it simply says that to optimize over a dual variable is equivalent to not Lagrangian relaxing the corresponding primal constraint; as we are not Lagrangian relaxing that constraint, we equivalently eliminate that dual variable! For the more general first result, we can observe that a dual line search corresponds to solving a primal problem where the linear constraints have been surrogate relaxed with a particular vector of relaxation parameters, namely p; see [Glo68, Geo69, GrP70, KaR79] for more on surrogate relaxation.

We next specialize this development to the important problem of minimum convex cost network flows, which is an application where dual ascent methods have been applied for several decades.

2.2.2 Dual ascent methods for separable strictly convex network flows:

Consider now the particular problem of the minimization of a separable strictly convex cost function over the feasible flows in a single-commodity network. This special case of the above problem corresponds to letting E be the node–link incidence matrix for the corresponding network representation, where each element e_{ij} equals −1 (1) if node i is the origin (destination) node of link j, and 0 otherwise; the value d_{i} is the demand value for node i, with d_{i} < 0 (d_{i} > 0) if node i is a source (sink) node, and the elements of d sum to zero.

In this case, the gradient of q at λ̄ has a particularly simple form. Suppose we rename the variable vector x such that each element is denoted x_{ik}, indicating the flow on link j = (i, k) from node i to node k; also, we denote the set of links by L and the set of nodes by N. From the special form of the problem the Lagrangian function has terms for each variable x_{ik} of the form ϕ_{ik}(x_{ik}) + (λ_{i} − λ_{k})x_{ik}.

By the sign conventions we then have that the partial derivative of the Lagrangian dual function q at λ with respect to each coordinate λ_{i} is as follows:

\frac{∂q(λ)}{∂λ_{i}} = ∑_{k:(i,k)∈L}x_{ik}(λ_{i} − λ_{k}) − ∑_{k:(k,i)∈L}x_{ki}(λ_{k} − λ_{i}) − d_{i}, i ∈ N ,

where x(λ) is the Lagrangian minimizer.

This result comes as no surprise, knowing that the optimality conditions of the dual problem is that ∇q(λ^{∗}) = 0^{m}, or, that Ex^{∗} = Ex(λ^{∗}) = d holds: the partial derivative of q with respect to λ_{i} equals the violation (or, slack) in the i^{th} flow conservation constraint; in the context of network flows, the violation of flow conservation is also called the divergence (or, surplus or imbalance) of node i.

In order to reach a dual optimal solution, it seems natural to utilize the primal–dual relations established above, and therefore to try to balance node i’s flow through the manipulation of the dual price λ_{i}; this is the main ingredient in a coordinate-wise dual ascent algorithm for the problem. From our previous example, we know that performing a restricted dual search in which q is maximized over the single dual price λ_{i}, that is, performing a line search in the i^{th} dual coordinate, is equivalent to satisfying the i^{th} equality constraint (in a Lagrangian optimal manner). If \frac{∂q(λ)}{∂λ_{i}} > 0, this means that too much net flow leaves (or, too little net flow reaches) the node. In order to balance the flow, a line search would then increase the value of λ_{i}.

From the above we can see that this line search problem is equivalent to a special form of separable problem (1), and is therefore amenable to be solved using the algorithms surveyed in this paper.

Some of the articles presented later on in this survey are devoted to the solution of the above network flow problem by means of Lagrangian relaxation and dual ascent. This technique is very old, and applications are abundant, including problems in migration theory, tomography, and many others, as well as several types of traditional network flow problems. To mention but a few references, see [Hil57, Bre67, Cry71, BaK78, BaK80, Her80, CeL81, OhK81, CoP82, OhK84, ZeM85, CDZ86, OOK86, CeH87, ZeM88, NEK90, ZeC91, Cur93], which all describe coordinate-wise dual search algorithms, dual ascent methods that operate over several coordinates simultaneously in [Pan84, Tse90, Ven91, HaH93, WuV95], the surveys in [LaS81, ErS90, ScZ90, CeZ97], the classic by Kruithof [Kru37] (sometimes called the RAS algorithm) and [DEs59, Osb60, Fur62, Sin64, Gra71, EvK74, Mur77, JeS79, Mac79, BHT87, BeT89, Tse91]. Further theoretical results on dual line searches, in particular for quadratic problems, are found in [Pan84, LiP87, TsB87, VeH88, BeT89, Tse90, TsB90, Ven91].

3 A survey of techniques for our problem

The two subsections to follow describe the two main approaches to the problem (1). The first class of algorithms utilizes the simple form of the KKT conditions and/or the Lagrangian dual problem which has only one variable. Since the optimal value of the multiplier μ is found through a line search and the values of the primal variables are only generated implicitly, we refer to this class of algorithms as a dual one. In the second class of algorithms, denoted pegging algorithms, an optimal solution x^{∗} is built up from solutions to relaxations of (1) wherein the bound constraints (1c) are relaxed. It is a recursive algorithm wherein at each iteration some variables will receive their optimal values. In the process the Lagrange multiplier is also optimized, but only implicitly, whence we refer to this as a primal algorithm.

In the annotated bibliographies that follow each algorithm class description we group together, in a (roughly) chronological order, work where algorithms are explicitly described. Under the term “Problem” we provide any special properties of the problem introduced beside those already stated when presenting the general problem (1); so, for example, we do not state that each function ϕ_{j} is convex and in C^{1}, and the default form of X_{j} is the finite interval [l_{j}, u_{j}]. Under the term “Origin” we explain to which concrete problem the algorithm is applied; if there is no specialization compared to be statements under “Problem” then this item is deleted. Actual methodological particulars are provided under the term “Methodology”, while under the term “Citations” we collect the most relevant citations in the work, if any. Under “Notes” we provide any additional remarks that are worth mentioning, such as whether the work contains comparative numerical experiments with conclusions.

3.1 Lagrange multiplier algorithms

3.1.1 Introduction

Algorithms based on the Lagrangian relaxation of the explicit constraint (1b) have an older history than the primal “pegging” algorithms. This is clearly due to the fact that pegging algorithms quite strongly rest on the Karush–Kuhn–Tucker (KKT) conditions (and the algorithmic developments in most of the relevant references are based on KKT arguments) which did not become widely available until the end of the 1940s and early 1950s with the work of F. John [Joh48], W. Karush [Kar39], and H. W. Kuhn and A. W. Tucker [KuT51]. Lagrangian based algorithms have been present much longer and the famous “Lagrange multiplier method” for equality constrained optimization is classic in the calculus curriculum. While in theory such algorithms extend neither to inequality constraints nor to the presence of a ground set X_{j} ≠ ℝ, the former poses no problem as we have discussed in Section 1, since we have only one inequality constraint; the latter imposes additional conditions that in a one-variable problem are easy to accommodate. Indeed, Lagrange multiplier techniques for our problem (1) are older, dating back at least to the early 1950s, if not earlier: the earliest reference found so far is to Beckmann [Bec52], which we include in our bibliography although the Lagrange multiplier algorithm therein is a simple grid search method. (We note that in every reference to [Bec52] cited in this paper, starting with the influential referencing in the text book [CAA57], the year 1952 has been erroneously replaced by 1942.)

Introducing the Lagrange multiplier μ ≥ 0 for the constraint (1b) we obtain the following conditions for the optimality of x^{∗} in (1):

μ^{∗} ≥ 0, g(x^{∗}) ≤ 0, μ^{∗}g(x^{∗}) = 0,  (13a)
x_{j}^{∗} ∈ X_{j},  j = 1, …, n,  (13b)

and

x_{j}^{∗} = l_{j}, if ϕ′_{j}(x_{j}^{∗}) ≥ −μ^{∗}g′_{j}(x_{j}^{∗}),  j = 1, …, n,  (13c)
x_{j}^{∗} = u_{j}, if ϕ′_{j}(x_{j}^{∗}) ≤ −μ^{∗}g′_{j}(x_{j}^{∗}),  j = 1, …, n,  (13d)
l_{j} < x_{j}^{∗} < u_{j}, if ϕ′_{j}(x_{j}^{∗}) = −μ^{∗}g′_{j}(x_{j}^{∗}),  j = 1, …, n.  (13e)

For the fixed optimal value μ^{∗} of the Lagrange multiplier the conditions (13c)–(13e) are the optimality conditions for the minimization over x ∈ ∏_{j=1}^{n} X_{j} of the Lagrangian function defined on ∏_{j=1}^{n} X_{j} × ℝ_{+},

L(x, μ) := −bμ + ∑_{j=1}^{n}{ϕ_{j}(x_{j}) + μg_{j}(x_{j})}.

Its minimization over x ∈ ∏_{j=1}^{n} X_{j} for a given μ ≥ 0 separates into n problems, yielding the Lagrangian dual function

q(μ) := −bμ + ∑_{j=1}^{n} minimum_{x_{j}∈X_{j}} {ϕ_{j}(x_{j}) + μg_{j}(x_{j})},  μ ≥ 0.  (14)

By introducing additional properties of the problem, we can ensure that the Lagrangian dual function q is not only concave but finite on ℝ_{+} and moreover differentiable there. Suppose, for example, that for each j, ϕ_{j}(·) + μg_{j}(·) is weakly coercive on X_{j} for every μ ≥ 0 [that is, that either X_{j} is bounded or that for every μ ≥ 0, ϕ_{j}(x_{j}) + μg_{j}(x_{j}) tends to infinity whenever x_{j} tends to ±∞], and that ϕ_{j} is strictly convex on X_{j}. In this case, then, the derivative q′ exists on ℝ_{+} and equals

q′(μ) = ∑_{j=1}^{n} g_{j}(x_{j}(μ)) − b,

where x(μ) is the unique minimum of the Lagrange function over ∏_{j=1}^{n} X_{j}. Thanks to this simple form of the dual derivative, the maximum μ^{∗} of q over ℝ_{+} can be characterized by the complementarity conditions (13a), and the conditions (13) are the primal–dual optimality conditions for the pair of primal–dual convex programs.

If we, as before, assume that μ^{∗} ≠ 0, we search for μ^{∗} > 0 such that q′(μ^{∗}) = 0 (or, in other words, g(x(μ^{∗})) = 0), that is, we need to solve a special equation in the unknown μ, where the function q′ is implicitly defined, but is known to be decreasing since q is concave. This equation can of course be solved through the use of any general such procedure [for example, bisection search takes two initial values \overline{μ} and \underline{μ} with q′(\overline{μ}) > 0 and q′(\underline{μ}) > 0, then iteratively cancels part of the initial interval given the sign of q′ at its midpoint (\overline{μ} + \underline{μ})/2], but the structure of q′ makes specialized algorithms possible to utilize.

From the above optimality conditions for the Lagrangian minimization problem over ∏_{j=1}^{n} X_{j} we obtain that

x_{j}(μ) = \begin{cases}l_{j}, & if μ ≥ μ^{+} := −ϕ′_{j}(l_{j})/g′_{j}(l_{j}), \\ u_{j}, & if μ ≤ μ^{−} := −ϕ′_{j}(u_{j})/g′_{j}(u_{j}), \\ x_{j}, & if ϕ′_{j}(x_{j}) + μg′_{j}(x_{j}) = 0. \end{cases}

As a special case, consider the set X := { x ∈ ℝ^{n} | 1^{T}x = b; l ≤ x ≤ u } with b > 0. The above formula then simplifies to

x_{j}(μ) = \begin{cases}l_{j}, & if μ ≥ μ^{+} := −ϕ′_{j}(l_{j}), \\ u_{j}, & if μ ≤ μ^{−} := −ϕ′_{j}(u_{j}), \\ x_{j}, & if ϕ′_{j}(x_{j}) = −μ, \end{cases}

and we learn again the strong connection to Gibbs’ Lemma 1 in the characterization of an optimal solution.

In a rudimentary algorithm we order these indices (or, breakpoints) μ^{+} and μ^{−} in an increasing (for example) order into {μ_{1}, …, μ_{N}}, where N ≤ 2n due to the possible presence of ties. Finding μ^{∗} then amounts to finding an index ȷ^{∗} such that either q′(μ_{ȷ∗}) = 0 (whence we are done), or that q′(μ_{ȷ∗}) > 0 and q′(μ_{ȷ∗+1}) < 0 and then performing an interpolation between these two values such that μ^{∗} ∈ (μ_{ȷ∗}, μ_{ȷ∗+1}) and q′(μ^{∗}) = 0.

Two decisions thus need to be made: how to find the index ȷ^{∗}, and how to perform the interpolation. Starting with the former, the easiest means is to run through the indices in ascending or descending order to find the index where q′ changes sign. (We will refer to this methodology by ranking.) If we have access to indices ȷ^{+} and ȷ^{−} for which q′(μ_{ȷ^{+}}) > 0 while q′(μ_{ȷ^{−}}) < 0, then we can choose the midpoint index, check the corresponding sign of q′, and reduce the index set thereafter. (We will refer to this methodology by bisection search.) Given the sorted list, we can also find this index in some random fashion. (We will refer to this methodology by random search.)

As remarked above, algorithms such as bisection search can be implemented without the use of the breakpoints, and therefore without the use of sorting, as long as an initial interval can somehow be found; also general methods for solving the equation q′(μ) = 0, such as the secant method or regula falsi, can be used even without an initial interval; notice however that q ∉ C^{2}, whence a pure Newton method is not guaranteed to be well-defined.

If the functions ϕ_{j} and g_{j} are quadratic and linear, respectively, the interpolation can be performed exactly, since the corresponding equation is linear; otherwise, it is in general an infinitely convergent procedure.

While the sorting operation used in the ranking and bisection search methods takes O(n log n) time it is possible to lower the complexity by choosing the trial index based on the median index, which is found without the use of sorting; the complexity of the algorithm is then reduced to O(n). It is not clear, however, that the latter must always be more efficient, since the “O” definition calls for n to be “large enough”. We also remark that in the case when the problem (1) arises as a subproblem in an iterative method, as the method converges the data describing the problem will tend to stabilize. This fact motivates the use of reoptimization of the problems, which most obviously can be done by using the previous value of the Lagrange multiplier as a starting point and/or utilizing the previous ordering of the breakpoints; in the latter case, the O(n log n) sorting complexity will eventually drop dramatically in practice, and even O(n^{2}) sorting methods may be competitive due to their better reoptimization capabilities.

To summarize the above class of methods, we may say that they are explicitly dual, since they work in the dual space. The methods are on the other hand also implicitly primal, since they in each step may identify optimal values of one or several primal variables x_{j} at their respective bounds.

Since we have opted to include only references to methods solving our problem and not any generalizations unless they do treat our problem as a subproblem, some perhaps natural references are omitted; we refer, for example, to papers that treat the case of ϕ non-separable (e.g., [HoI99]; the algorithms in this paper reduce to a general dual search method and bisection, respectively).

For the problem at hand, the principle of optimizing the value of μ is discussed in [Bec52, Ber60, Eve63, Tak63], [Dan67, pp. 11–12], [Roc70, pp. 285–287], and [Geo70a, Geo70b, Geo70c, GrP70, Tak70], among others, but without explicit details or referring to trial–and–error techniques only; the term grid search refers to one such technique.

3.1.2 Annotated bibliography

[Bec52] M. J. Beckmann, A Lagrangian multiplier rule in linear activity analysis and some of its applications

(Problem) ϕ_{j}(x_{j}) = c_{j}/x_{j} + b_{j}x_{j}, c_{j} > 0, b_{j} > 0; (non)linear inequality (g_{j}(x_{j}) = d_{j}/x_{j}, d_{j} > 0; or a_{j} > 0);

l_{j} = −∞, u_{j} = ∞ (Origin) Lot sizing problems with a linear (warehouse space) or nonlinear (machine time) restriction (Methodology) Grid search (Citations) Unknown (see below); the author has been informed by prof. David Boyce, Northwestern Uni-

versity, Evanston, IL, that the report by Slater [Sla50] was quite influencial in the work of Martin Beckmann; both reports were produced at the Cowles Commission, New Haven, CT.

(Notes) Numerical examples (n = 2). Extends the technique to two inequality constraints. Unpublished report unavailable to the author; a summary is however available in [CAA57, Chapter 10].

[ChC58b] A. Charnes and W. W. Cooper, The theory of search: Optimal distribution of search effort (Problem) ϕ_{j}(x_{j}) = q_{j}exp(−αx_{j}), q_{j} > 0, q_{j+1} ≤ q_{j}, α > 0; linear equality (a_{j} = 1, b = 1); l_{j} = 0 (Methodology) Ranking (Citations) Algorithms: [ChL54] (separable programming); theory of search: [Koo52, Koo53, Koo54, Koo56a,

Koo56b, Koo56c, Koo57]; theory: [KuT51]

[Eve63] H. Everett, III, Generalized Lagrange multiplier method for solving problems of optimum allocation of resources (Problem) ϕ_{j}(x_{j}) = − log[1 − (1 − q_{j})^{x_{j}}], q_{j} ∈ (0, 1); linear inequality (a_{j} > 0) (Origin) “Cell problem” in more complex models; application to a problem in reliability investment (Methodology) Grid search (Citations) Application: [Ket62] (Notes) Numerical experiments with a trial–and–error method (n = 4). The method of [Ket62] for an

integer programming version of the problem utilizes dynamic programming; see also [Loa71]

[Sri63] K. S. Srikantan, A problem in optimum allocation (Problem) ϕ_{j} ∈ C^{2}, ϕ′′_{j} > 0; linear equality (a_{j} ≠ 0, b = 10^{s} for some positive integer s); l_{j} ≥ 0 (Origin) Extension of an optimal allocation problem in stratified sampling (Methodology) Bisection search without the use of breakpoints (Citations) Application: [Ney34]; theory: [ChC61a] (Notes) Numerical experiments (n = 6)

[Bod69] L. Bodin, Optimization procedures for the analysis of coherent structures

(Problem) ϕ_{j} strictly convex, increasing; ϕ_{j}(l_{j}) > 0; linear inequality (a_{j} = 1); 0 < l_{j} < u_{j} < 1. Special

case: ϕ_{j}(x_{j}) = c_{j}(1 − expx_{j}), c_{j} > 0 (Origin) Reliability determination at minimum cost for parallel or series systems (Methodology) Ranking (Citations) [BaP65] (Notes) Discusses “modular decomposition” as a means to decompose more complex models with several

explicit constraints into the present one. Considers also solving a parametric model over the values of the right-hand side b.

[DaS69] S. Dafermos and F. T. Sparrow, The traffic assignment problem for a general network (Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2}, q_{j} > 0; linear equality (a_{j} = 1); l_{j} = 0, u_{j} = ∞ (Origin) Subproblem for each origin–destination pair in the traffic equilibrium problem within a cyclic

decomposition (Jacobi) algorithm (Methodology) Ranking; referred to as the “equilibration operator” (Citations) Model foundations: [Pig20, War52, Bec67, BMW56, FoF58, FoF62, ChC58a, ChC61b] (Notes) Numerical experiments (n = 60)

[San71] L. Sanathanan, On an allocation problem with multistage constraints

(Problem) General: ϕ_{j} ∈ C^{2}, ϕ′′ > 0; linear equality (a_{j} ≠ 0); l_{j} = −∞, u_{j} = ∞ possible. Application:

ϕ_{j}(x_{j}) = q_{j}/x_{j}, q_{j} > 0 (Origin) Same. Application to optimal allocation in stratified sampling subject to restrictions on strata

estimates, capital budgeting and multistage sampling (Methodology) Bisection search à la [Sri63] (Citations) [Sri63, Kis65] (Notes) Numerical experiments (n = 6); same problem as in [Sri63]. Presents a recursive pegging algorithm;

cf. Section 3.2.

[HWC74] M. Held, P. Wolfe, and H. P. Crowder, Validation of subgradient optimization (Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}, linear equality (a_{j} = 1); l_{j} = 0, u_{j} = ∞ (Origin) Linear minimum cost multicommodity flow problem solved via right-hand side (RHS) allocation,

Lagrangian relaxation and subgradient optimization; projection arises in the multiplier updating step, one for each commodity

(Methodology) Ranking (Citations) Cites [AbS70], where it is explained that G. W. Dantzig had already previously applied RHS

allocation to the given problem (Notes) Numerical experiments (n ∈ [3, 20])

[Jud75] J. V. Jucker and C. de Faro, A simple algorithm for Stone’s version of the portfolio selection problem (Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1, b = 1); l_{j} = 0 (Origin) Separable approximation of Markowitz’ portfolio selection problem, taken from [Sto73] (Methodology) Ranking (Citations) Models: [Mar52, Mar59, Sha63, Sto73] (Notes) Numerical experiments (n = 8)

[LuG75] H. Luss and S. K. Gupta, Allocation of effort resources among competing activities (Problem) ϕ_{j} strictly convex and increasing; linear inequality (a_{j} = 1) (Origin) Subproblem in a recursive pegging algorithm; cf. Section 3.2 (Methodology) Ranking (Citations) Algorithms: [ChC58b, WiG69, Geo70a, Geo70c] (Notes) Notes that having a closed form solutions to each Lagrangian problem is advantageous, and gives

them for some special forms of functions ϕ_{j}

[KeS77] J. L. Kennington and M. Shalaby, An effective subgradient procedure for minimal cost multicommodity flow problems (Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear equality (a_{j} = 1); l_{j} = 0, u_{j} = ∞ (Origin) Linear minimum cost multicommodity flow problem solved via RHS allocation, Lagrangian relax-

ation and subgradient optimization; projection arises in the multiplier updating step, one for each commodity

(Methodology) Refers to the ranking procedure from [HWC74] (Citations) Related models: [War52, ChC61b, HWC74]; price-directive decomposition: [FoF58, Tom67,

WeC72] (Notes) Numerical experiments (n ∈ [8, 12])

[AHKL80] A. I. Ali, R. V. Helgason, J. L. Kennington, and H. Lall, Computational comparisons among three multicommodity flow algorithms

(Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear equality (a_{j} = 1); l_{j} = 0, u_{j} = ∞ (Origin) Linear minimum cost multicommodity flow problem solved via RHS allocation, Lagrangian relax-

ation and subgradient optimization; projection arises in the multiplier updating step, one for each commodity

(Methodology) Ranking (Citations) Algorithms: [HWC74, KeS77] (Notes) Numerical experiments, comparing RHS allocation with Dantzig–Wolfe decomposition and primal

partitioning (n ∈ [8, 60]). RHS allocation wins while convergence of that algorithm is not guaranteed

[HKL80] R. V. Helgason, J. L. Kennington, and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1, b = 1); l_{j} = 0 (Methodology) Bisection search; extends the method from [HWC74] to a more general case of QP (Citations) [HWC74, KeS77, AHKL80] (for applications and special cases); [ChC58b, Sri63, San71, LuG75,

BiH79, McC7X] (for related work) (Notes) Derives a O(n log n) time bound

[Zip80b] P. H. Zipkin, Simple ranking methods for allocation of one resource

(Problem) ϕ_{j} strictly convex, linear equality (a_{j} = 1); l_{j} = 0 (Origin) Subproblem in a hierarchical pegging algorithm for the same problem with additional upper

bounds; cf. Section 3.2 (Methodology) The ranking method from [LuG75] is the source algorithm. Modifications: (a) allowing

for the inexact determination of the Lagrangian problem’s solution; (b) allows for starting at any breakpoint. Notes the possibility to replace ranking by bisection search (or Fibonacci search) and the possibility to restart from the optimum in the previous iteration

(Citations) Applications: optimal search effort ([ChC58b]), marketing ([LuG75]), capital budgeting ([Han68, p. 81]), production ([BiH77]), aggregation errors ([Zip80a]), portfolio selection ([Jud75, EGP76]), reliability ([Bod69]), health care ([Fet73]), and multicommodity flows ([HWC74]). Algorithms: cites the Lagrange multiplier method in [LuG75] as subsuming [ChC58b, WiG69]; discusses also the pegging algorithm from [BiH77] (wrongly supposing that only one variable can be pegged at any given iteration) and the Lagrange multiplier methods from [Bod69, HWC74, Jud75]. Further citations: [Koo57, deG61, Kar62, Eve63, Geo70a, Geo70b, GrP70]

(Notes) Perhaps the first survey, providing a unified presentation of some previous work.

[Ein81] J. M. Einbu, Extension of the Luss–Gupta resource allocation algorithm by means of first order approximation techniques

(Problem) ϕ_{j} ∈ C^{2} strictly convex and increasing; linear inequality (a_{j} = 1); l_{j} = 0 (Origin) Subproblem in a recursive pegging algorithm; cf. Section 3.2 (Methodology) Ranking; extension of the analytic method from [LuG75] with the numerical solution of the

Lagrangian problem determining the current Lagrange multiplier estimate (Citations) [LuG75]

[Hor81] R. Horst, On reducing a resource allocation problem to a single one-dimensional minimzation of a differentiable convex function

(Problem) ϕ_{j} strictly convex, decreasing, ϕ_{j}(0) = 0; linear equality; l_{j} = 0 (Origin) Same (Methodology) (Citations) Convex programming techniques: [ChC58b, LuG75]; dynamic programming techniques: [WiG69];

duality: [Geo71] (Notes) Derives the primal–dual optimality conditions of the problem; proposes no algorithms

[Was81] A. R. Washburn, Note on constrained maximization of a sum

(Problem) ϕ_{j} strictly convex; linear equality (a_{j} = 1); l_{j} = 0 (Methodology) Ranking, possibly with a random starting index (Citations) Algorithms: [ChC58b, Eve63, Sto75, Bro80] (Notes) Numerical experiments (n = 8)

[OhK80] A. Ohuchi and I. Kaji, Algorithms for optimal allocation problems having quadratic objective function (Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1); l_{j} > 0 (Origin) Subproblem in a coordinate dual ascent method for a strictly convex quadratic optimal allocation

problem (Methodology) The Lagrange multiplier methods “polynomial approximation” (PA; quadratics preferable),

“sequential search” (SS; bisection search), hybrid method (HB = PA + SS) (Citations) [Tak70] (consider the same problem, except for u_{j} = ∞, provides a coordinate-wise search

method for the Lagrange dual but without details or theory) [Tak63, Geo70a, Geo70b] (background theory); [KIM79] (extension to integer programming case)

(Notes) Numerical experiments (n ∈ [10, 100]; randomly generated instances); HB best

[OhK81] A. Ohuchi and I. Kaji, An algorithm for the Hithcock transportation problems with quadratic cost functions (Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} > 0); l_{j} > 0 (Origin) Parallel subproblems in a coordinate dual ascent method for a strictly convex quadratic trans-

portation problem (Methodology) The three Lagrange multiplier methods from [OhK80] (Citations) Algorithms: [Tak70, OhK80]; [AHU74] for bisection search complexity (Notes) Numerical experiments using HB (number of source nodes N_{1} ∈ [40, 100]; number of terminal nodes

N_{2} ∈ [80, 200]; randomly generated instances); reference to [HKL80] added in proof

[OhK84] A. Ohuchi and I. Kaji, Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs (Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} > 0); l_{j} ≥ 0 (Origin) Parallel subproblems in a coordinate dual ascent method for a strictly convex quadratic trans-

portation problem (Methodology) The three Lagrange multiplier methods from [OhK80] (Citations) [Tak70, OhK80]; [AHU74] for bisection search complexity (Notes) Numerical experiments using HB (n ∈ [30, 100]; complete graphs; randomly generated instances);

favourable comparison to Wolfe’s [Wol74] QP algorithm (tests on problems with n ∈ [5, 7]); no reference to [HKL80, OhK81] but algorithm better explained

[Zie82] H. Ziegler, Solving certain singly constrained convex optimization problems in production planning (Problem) ϕ_{j}(x_{j}) = c_{j}/x_{j} + b_{j}x_{j}, c_{j} ≥ 0, b_{j} ≥ 0; linear inequality (a_{j} > 0); l_{j} = 0, u_{j} = ∞ (Methodology) Bisection search without sorting or use of breakpoints; acceleration by Newton method or

regula falsi; initial interval given by a projection of the result of Harris’ [Har15] EOQ formula (Citations) Previous “trial-and-error” procedures: [Bec52, CAA71] (Notes) Notes that no bounds on μ^{∗} are provided in the previous work. Numerical experiments (n ∈

[10, 500]). Main purpose to propose a bound on μ^{∗} rather than actually finding its value

[FeZ83] A. Federgruen and P. Zipkin, Solution techniques for some allocation problems (Problem) ϕ_{j} strictly convex; linear equality (a_{j} = 1); l_{j} = 0 (Origin) Parallel subproblem in a RHS allocation algorithm for a problem with additional linear generalized

upper bound (GUB) constraints (Methodology) Derived from the ranking algorithm from [Bod69]; replaces sorting by work with two heaps;

no complexity analysis; also discusses the reoptimization of the sorted list, and discusses the invertibility of ϕ′_{j} and proposes a numerical approximation scheme (cites [Zip80b])

(Citations) Related work ([Bod69, LuG75, OhK80, Zip80b, BiH81, Roh79])—see [Roh82] for the published

version of the latter; data structures ([Knu68, AHU74]) (Notes) The paper [Roh82] contains a discussion on the productivity of the activities, measured in terms of

the quantity ϕ_{j}(x_{j}^{∗})/x_{j}^{∗}, and relates this number to the value of ϕ′_{j}(0) for some special return functions given in [ChC58b, LuG75] [Bru84] P. Brucker, An O(n) algorithm for quadratic knapsack problems

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (Methodology) Median search (Citations) [HKL80]; [AHU74] for median complexity O(n)

[CDZ86] R. W. Cottle, S. G. Duvall, and K. Zikan, A Lagrangean relaxation algorithm for the constrained matrix problem

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1); l_{j} = 0 (Origin) Parallel subproblems in block coordinate dual ascent method for the quadratic transportation

problem (Methodology) Bisection search; reoptimization of sorting using permutation vector from [Knu73, p. 80]; also

tests using the parametric principal pivoting (PPP) algorithm; also investigates the use of successive over-relaxation (SOR) in the coordinate ascent method

(Citations) Problem ([Bac70, BaK78]); other coordinate ascent algorithms ([Tak63, Tak70, OhK80, OhK81, OhK84]); subproblem algorithms ([Roc70, Jud75, FLR78, KIM79, HKL80, Roc81, Bru84]); cyclic coordinate ascent ([Zad69, Zan69]); SOR ([CoP82, Cot84]); parametric principal pivoting ([Cot72])

(Notes) Discusses the problem of unbounded level sets of the Lagrangian dual problem; imposes a Slater condition. Remarks that the test problems in [OhK84] are “easy”. Numerical experiments (number of source nodes N_{1} = 54; number of terminal nodes N_{2} = 55; taken from [BaK78, BaK80]); reoptimization of sorting reduces CPU time by half; SOR another half; best algorithm PPP (note: equivalent to using median search, or ordinal statistics, cf. [RJL92])

[DFL86] J.-P. Dussault, J. A. Ferland, and B. Lemaire, Convex quadratic programming with one constraint and bounded variables

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} ≥ 0); l_{j} = −∞, u_{j} = ∞ possible (Origin) Positive semidefinite quadratic program solved through a series of separable approximations; par-

allel subproblems in coordinate dual ascent method for the problem (Methodology) Bisection search (Citations) Refers to the complementary pivot algorithm from [Pan80] as reducing to bisection search for

quadratic programs with a diagonal Hessian; other Lagrange multiplier search methods ([FLR78, HKL80, Roc70]); the active set method from [McC79]

(Notes) Numerical experiments with two versions of the complete algorithm (exact line search; unit step length) and the parametric linear complementarity algorithm from [Pan80] (n = 50); the latter wins when the original problem matrix is less diagonally dominant

[Vid84] P. V. V. Vidal, A graphical method to solve a family of allocation problems

(Problem) ϕ_{j}(x_{j}) = −r_{j}(1 − exp(−k_{j}x_{j})), r_{j}, k_{j} > 0; linear equality; l_{j} = 0 (Methodology) Graphical method for finding a zero of q′ based on a nonlinear transformation that creates

a piece-wise linear q′ (Citations) General methodologies: [Sri63, Vid70, San71, BiH79]; dynamic programming: [WiG69]; Kuhn–

Tucker based: [LuG75]; derivation of the Lagrangian: [Hor81] (Notes) Numerical experiment (n = 4) taken from [WiG69]. Provides a table of references to applications

where other nonlinear transformations also lead to piece-wise linear q′

[Vid86] P. V. V. Vidal, Solving a family of simple allocation problems

(Notes) Same algorithm, same numerical example, same methodological references, and same table as in [Vid84], but without a reference. Discusses an extension to a non-differentiable problem

[Vid87] P. V. V. Vidal, A simple method to solve some simple allocation problems

(Notes) Same algorithm, same numerical example, same methodological references, and same table as in [Vid84], but without a reference

[CaM87] P. H. Calamai and J. J. Moré, Quasi-Newton updates with bounds

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (Origin) Broyden quasi-Newton update of Jacobian approximation (Methodology) Median search (Citations) [AHU74] for median search complexity O(n) (Notes) Notes that the result of the median search also provides important information when the original

problem is inconsistent

[IbK88] T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches

(Problem) Linear equality (a_{j} = 1) (Origin) Resource allocation problem from several areas (Methodology) Pegging (the algorithm BRELAX2 from [BiH81]) or recursive pegging (first converting the

set to X_{j} to [0, u_{j}], then utilizing the Lagrange multiplier algorithm BRELAX1 from [Zip80b]); pegging (the algorithm from [BiH81], then denoted RELAX) for the special case of X_{j} = [0, u_{j}]

(Citations) Applications: optimal search effort ([Koo53, Koo56a, Koo56b, Koo57, ChC58b, Kar58, Kar62]), optimal sample allocation in stratified sampling ([Ney34, Sri63]), optimal portfolio selection ([Mar52, Mar59, Sha63, Sto73, Jud75, EGP76, Zip80b]), production planning ([BiH77, BHH81, BiH81, Zie82]), resource distribution ([FeZ83, FeZ84]), mass advertising ([Kot71]; here, ϕ_{j} is “S-shaped”), marketing effort allocation ([Lus73]), reliability problems ([Bod69]), bidding for oil and gas ventures ([FeG86]), allocation of people to evacuation routes ([Fra78]), subproblems in subgradient algorithms ([HWC74]), the apportionment problem ([BaY82]). Algorithms for continuous problems: pegging algorithms ([Zip80b, BiH81]), Lagrange multiplier methods ([LuG75, HKL80, OhK80, Zip80b, Was81, Bru84]), and variations ([Ein81])

(Notes) Comprehensive overview of the linearly constrained allocation problem with extensions to minimax/maximin, lexicographic minimization, submodular and integrality constraints, and more. Notes that the RELAX algorithms can be extended to the case of non-differentiable functions ϕ_{j}

[RoW88] R. T. Rockafellar and R. J.-B. Wets, A note about projections in the implementation of stochastic quasigradient methods

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; g′_{j} > 0 and bounded away from zero; l_{j} = −∞, u_{j} = ∞ possible (Origin) Projection subproblem in a stochastic quasigradient method (Methodology) Ranking; interpolation by the secant method; proposes also the secant method for the

Lagrangian minimization problem when x_{j}(μ) is not explicitly available (Citations) Related work: [FLR78, McC79, HKL80, BiH81, CDZ86] (Notes) Acknowledges R. Cottle for supplying references

[VeK88] J. A. Ventura and C. M. Klein, A note on multi-item inventory systems with limited capacity

(Problem) ϕ_{j}(x_{j}) = c_{j}/x_{j} + b_{j}x_{j}, c_{j} ≥ 0, b_{j} ≥ 0; linear inequality (a_{j} > 0); l_{j} = 0, u_{j} = ∞ (Methodology) Refinement of algorithm from [Zie82]; initial interval given from the least/most costly items

relative storage requirements, followed by a Newton/regula falsi step; proposes an algorithm based on the continued use of such steps, but without a formal convergence analysis

(Citations) Background ([Har15]), marginal cost solution technique ([JoM74]), previous bounds on μ^{∗}

([Zie82]). (Notes) Main purpose to propose a bound on μ^{∗} rather than actually finding its value

[Ven89] J. A. Ventura, Algorithms for quadratic transportation networks

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (Origin) Line search subproblem in the Polak–Ribière [PoR69] dual ascent method for the quadratic trans-

portation problem (Methodology) Two algorithms: (a) the pegging algorithm from [BiH81], extended to possibly negative

constraint coefficients and developed in [VeH88]; (b) the bisection search algorithm from [CDZ86], utilizing reoptimization of breakpoints (and claiming that [CDZ86] does not utilize reoptimization) as well as pegging variables based on the sign of q′; the algorithm does not use sorting of the breakpoints

(Citations) Applications: communication networks ([Min78, Min84]), adjustment of input–output tables ([BaK78, BaK80, BiH81]), estimation of contingency tables in statistics ([DeS40, Fri61]), and projection of interzonal transfers ([DeM80, Oma67]); Lagrangian dual algorithms: cyclic coordinate ascent ([CDZ86]), gradient-based dual ascent ([KNS74, VeH88])

(Notes) Numerical experiments (number of source nodes N_{1} ∈ [25, 150]; number of terminal nodes N_{2} ∈ [25, 150]). Best strategy found was to initially use pegging, then transfer to bisection search (the latter utilizes a good starting solution better), but difficult to find a good transition strategy [Ven91] J. A. Ventura, Computational development of a Lagrangian dual approach for quadratic networks

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (Origin) Line search subproblem in the Polak–Ribière [PoR69] dual ascent method for the quadratic trans-

portation problem (Methodology) Three algorithms: (a) the bisection search algorithm from [HKL80], extended to cover non-

unit constraint coefficients; (b) random search without sorting; (c) the pegging algorithm from [BiH81], extended to cover non-unit constraint coefficients

(Citations) Applications: resistive electrical networks ([CoK77]), equilibrium import–export trade problems ([Gla78]), quadratic data fitting ([BaK80]), optimal economic operation of electric power systems ([ElC79]), projecting and forecasting traffic matrices in telecommunication networks ([DeM80]); Lagrangian dual algorithms ([BaK80, CoP82, OhK84, ZeM85, CDZ86, BeE87, BHT87]); [LiP87] for the interpretation of dual line searches

(Notes) Numerical experiments (n ∈ [50, 500]); the pegging algorithm wins, and random search is somewhat faster than bisection search; discusses a potential improvement from utilizing that the step lengths become smaller by eventually switching from pegging to bisection search, but without testing. Presents a primal feasibility heuristic for adjusting the infeasible Lagrangian problem solutions x(μ) into feasible flows; the heuristic is however not optimizing in the limit as μ → μ^{∗}

[DaN89] S. Dafermos and A. Nagurney, Supply and demand equilibration algorithms for a class of market equilibrium problems

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1) (Origin) Subproblem for each pair of supply and demand within a cyclic decomposition (Jacobi) algorithm

for a market equilibrium model with linear and separable supply and demand functions (Methodology) Ranking; referred to as the “equilibration operator”; adaptation of the algorithm from

[DaS69] to the given problem (Citations) Algorithms in the same spirit: [DaS69, LuG75, HKL80, Zip80b, BiH81]; iterative algorithm for

the same problem: [Nag87]

[PaK90] P. Pardalos and N. Kovoor, An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1); l_{j} = 0 (Methodology) Proposes a randomized version of the median search algorithm, having O(n^{2}) worst-case and

O(n) expected complexity; theoretically compares the algorithm with the median search algorithm from [Bru84] and the bisection search algorithm from [HKL80]

(Citations) Median complexity: [Blu+72, AHU74]; projection algorithms: [HWC74, HKL80, Bru84, CaM87];

application to multicommodity network flows ([HWC74, Mey84]) (Notes) Numerical experiments (n ∈ [500, 4000]); compares randomized median search with bisection

search; the former wins in CPU time by a factor of three. The reference [Bru84] was added thanks to a referee

[ShM90] B. Shetty and R. Muthukrishnan, A parallel projection for the multicommodity network model

(Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear equality (a_{j} = 1); l_{j} = 0 (Origin) Linear minimum cost multicommodity flow problem solved via RHS allocation, Lagrangian relax-

ation and subgradient optimization; projection arises in the multiplier updating step, one for each commodity

(Methodology) Bisection search (Citations) RHS allocation algorithm for the problem: [HWC74, KeS77, HKL80], the latter also for the

claim that RHS allocation is the best decomposition scheme for the problem (Notes) Numerical experiments (n ∈ [50, 450])

[NiZ92] S. S. Nielsen and S. A. Zenios, Massively parallel algorithms for singly constrained convex programs

(Problem) ϕ_{j} strictly convex; linear equality (a_{j} > 0) (Origin) Subproblem in several network flow type problems (Methodology) Four algorithms: (a) An iterative Bregman projection algorithm originating in [CeL81]; each

iteration consists of a sequence of projection-like operations with respect to a distance measure in terms of approximations of ϕ_{j} (a “Bregman function”), first onto the hyperplane, then onto the bounds for each variable depending on the result of the hyperplane “projection”; the operations resemble those of the pegging algorithm, but convergence is not finite. (b) The bisection algorithm, extending that from [HKL80] to non-quadratic ϕ_{j}. (c) A line search method originating in [Tse90] which provides an underestimate of the optimal step. (d) A Newton-type algorithm where the formula utilizes left or right derivatives of ϕ′ depending on its sign. Convergence is established for quadratic ϕ_{j}

(Citations) Applications to RHS allocation methods for multicommodity flows ([HKL80]), row-action methods in computerized tomography ([Her80]), nonlinear network flow problems solved by dual coordinate ascent methods ([BeT89]) and in matrix balancing ([ScZ90]), as well as in other applications ([DFL86, PaK90, CoH93]); dual line search methods ([HKL80, CeL81, Tse90])

(Notes) Numerical experiments (n ∈ [91, 1000]) on massively parallel implementations; the Newton method is found to be the most robust; does however not implement bisection search but instead ranking, and remarks that it fares badly for tightly constrained problems and that it would be a good idea to use bisection instead

[RJL92] A. G. Robinson, N. Jiang, and C. S. Lemke, On the continuous quadratic knapsack problem

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} > 0); transforms the problem before solution

to ϕ_{j}(x_{j}) = \frac{1}{2} x_{j}^{2} (Methodology) Three Lagrange multiplier algorithms: (a) the approximate median based algorithm from

[PaK90], implemented as in [AHU74, p. 102]; (b) the bisection search algorithm from [HKL80], implemented using Quicksort; (c) the median search algorithm from [Bru84]; and (d) a dual “Newton” method (as suggested by a referee) with safe-guards against non-differentiability and non-ascent. Includes the possibility to peg the variables x_{j} based on the sign of q′ (à la [Ven89, Ven91]). Also proposes a pegging algorithm; cf. Section 3.2

(Citations) Applications: multicommodity flows ([AHKL80]), traffic equilibrium ([DaS69]), quadratic transportation ([OhK84]), matrix balancing in regional and national economics ([CDZ86, NKR90, NaR92]), convex quadratic programming ([CDZ86]), portfolio selection ([Jud75, Pan80]); references to other pegging algorithms ([Mic86], pointed out by a referee), and Lagrange multiplier methods ([DaS69, HWC74, HKL80, Bru84, CDZ86])

(Notes) Notes that the principal pivoting algorithm ([CDZ86]) reduces to the O(n) ordinal statistics (median search) algorithm for the given problem. Numerical experiments (n ∈ [100, 4000]) against the pegging algorithm; the pegging algorithm wins against all the three Lagrange multiplier methods and is comparable to the Newton method. Notes that the complexity of bisection search grows more than linearly with n, whereas the others grow linearly

[GSAB93] S. J. Grotzinger, R. Srinivasan, R. Akella, and S. Bollapragada, Component procurement and allocation for products assembled to forecast: Risk-pooling effects

(Problem) ϕ_{j}(x_{j}) = d_{j} ∫_{0}^{x̂_{j} +x_{j}} [x̂_{j} +x_{j} −s]f_{j}(s) ds (convex; f_{j} is a marginal density function); linear equality

(a_{j} = 1) (Methodology) Ranking; advanced start, with first index chosen based on the sign of the constants x̂_{j};

extends the procedure from [Zip80b] to the case of upper bounds (Citations) Algorithms: [LuG75, Zip80b] (Notes) Numerical experiments (n ∈ [2, 44])

[MaK93] B. M. Maloney and C. M. Klein, Constrained multi-item inventory systems: An implicit approach

(Problem) ϕ_{j}(x_{j}) = c_{j}/x_{j} + b_{j}x_{j}, c_{j} > 0; linear inequality (a_{j} > 0); l_{j} = 0, u_{j} = ∞ (Methodology) Improves the initial bounds from [VeK88]; cites [HMMS60, Lew81] for the origins of such

bounds; also presents a Newton-type algorithm (denoted the “implicit algorithm”) for obtaining μ^{∗}, which utilizes the bounding formula iteratively; the algorithm utilizes an initial ranking of inventory cost/storage requirement ratios, just as in [Zie82, VeK88]; convergence is claimed (referring to it being a Newton method) but not established

(Citations) Problem definitions ([Har15]), the “classic solution technique” ([HaW63, BuK63, JoM74]); ear-

lier bounds on μ^{∗} ([Zie82, VeK88]) (Notes) Numerical experiments (n ∈ [2, 31]); compares the implicit algorithm with the iterative algorithms

from [Zie82, VeK88] and the “classic solution technique”; the proposed wins in a clear majority of the cases. Main purpose still to propose a bound on μ^{∗} rather than actually finding its value [CoH94] S. Cosares and D. S. Hochbaum, Strongly polynomial algorithms for the quadratic transportation

problem with a fixed number of sources

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1); l_{j} = 0, u_{j} = ∞ (Origin) Quadratic transportation problem with one source; extended to any fixed number of sources (Methodology) Median search (Citations) Linear median complexity: [Blu+72]; original algorithm: [Bru84]

[Hoc94] D. S. Hochbaum, Lower and upper bounds for the allocation problem and other nonlinear optimization problems

(Problem) ϕ_{j} convex; linear equality (a_{j} = 1); l_{j} = 0, u_{j} = ∞ (Methodology) Greedy algorithm with arbitrary increments (Citations) Continuous case: [Zip80b, Koo57, LuG75, Bru84]; discrete case: [Koo53, ChC58b, IbK88] (Notes) The algorithm does not require that ϕ_{j} ∈ C^{1}

[HoH95] D. S. Hochbaum and S.-P. Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} = 1); l_{j} = 0, u_{j} = ∞ (Origin) Special case of a problem with generalized upper bound (GUB) constraints (Methodology) Median search (Citations) Linear time algorithms: [Bru84, CoH94]; median complexity: [Blu+72] (Notes) Also presents an O(n) algorithm for the GUB case

[BrS95] K. M. Bretthauer and B. Shetty, The nonlinear resource allocation problem

(Origin) Same problem with integral requirements on x, solved by means of continuous relaxation and

branch–and–bound (Methodology) Lagrangian relaxation of the nonlinear constraint; unspecified method for solving the result-

ing equation q′(μ^{∗}) = 0 (Citations) “Generalizes previous work” in [HKL80, Bru84, CaM87, PaK90, ShM90] (QP) and [NiZ92]

(linear constraint), and similar approaches for allocation problems in [Zip80b, BiH81, IbK88] and for production planning in [Zie82, VeK88, MaK93]

(Notes) Discusses the cases when the Lagrangian problem has a closed form solution (such as for the stratified sampling, quadratic knapsack, and production planning problems) or not (such as in capacity planning in manufacturing networks)

[BSS95] K. M. Bretthauer, B. Shetty, and S. Syam, A branch and bound algorithm for integer quadratic knapsack problems

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} > 0) (Origin) Same problem with integral requirements on x, solved by means of continuous relaxation and

branch–and–bound (Methodology) Bisection search (Citations) Applications: promotion models ([McC7X]); capital budgeting ([Lau70, MSM83, DMS88]); hy-

drological studies, clique problems in graphs, and location problems ([GHS80]); for the continuous case: resource allocation ([BiH79, LuG75]); algorithms for multicommodity flows ([HWC74]) and stochastic programs with network recourse ([NiZ93]); additional references found in [IbK88]. Algorithms for the problem: [HWC74, HKL80, Bru84, CaM87, PaK90, ShM90, PYH91, NiZ92]

(Notes) Discusses the reoptimization of the relaxed problem from a previous B & B iteration when the lower bounds change. Describes the algorithm in the unavailable report by McCallum [McC7X] as solving the continuous relaxation and applying a rounding heuristic in order to obtain integer solutions. Numerical experiments (n ∈ [75, 200])

[Bre96] K. M. Bretthauer, Capacity planning in manufacturing and computer networks

(Problem) ϕ_{j}(x_{j}) = c_{j}x_{j}; nonlinear inequality (g_{j}(x_{j}) = a_{j}/(x_{j} − h_{j}), a_{j} > 0) (Origin) Same problem with integral requirements on x and a concave objective function, solved by means

of continuous relaxation and branch–and–bound, and where the concave objective function is replaced by a linear underestimator within each set X_{j} (Methodology) Lagrangian relaxation of the nonlinear constraint; unspecified method for solving the result-

ing equation q′(μ^{∗}) = 0 (Citations) [BiH81, PaK90] included in the reference list but not in the text (Notes) Numerical experiments (n ∈ [75, 300]) on the integer program that compares whether reoptimiza-

tion of the continuous subproblems and special heuristics applied at each B & B node are advantageous; the answer is ’yes’

[BiM96a] G. R. Bitran and S. V. Mondschein, Inventory management in catalog sales companies

(Problem) ϕ_{j}(x_{j}) = − ∫_{0}^{x̂_{j} +x_{j}} d_{j}[x_{j} − c_{j}(x̂_{j} + s − x_{j})]f_{j}(s) ds − ∫_{x̂_{j} +x_{j}}^{∞} d_{j}(x̂_{j} + x_{j} − ĉ_{j}(s − x̂_{j} − x_{j}))f_{j}(s) ds

(convex; f_{j} is a marginal density function); linear inequality (a_{j} > 0); l_{j} = 0, u_{j} = ∞ (Origin) Operational submodel in a hierarchical decision-making model including feedback strategies (Methodology) Bisection search without the use of breakpoints (Citations) Applications: [BHH82, BiM96b]; algorithms solving similar models, also by the use of the KKT

conditions: [LuG75, Zip80b]

[Gla96] P. Glasserman, Allocating production capacity among multiple products

(Problem) ϕ_{j}(x_{j}) = c_{j}/γ_{j}(x_{j}), γ_{j}^{−1} convex; linear equality (a_{j} = 1); l_{j} > 0, u_{j} = ∞ (Origin) Choice of base-stock levels and capacity allocations for a minimal total backorder or holding cost,

in an inventory system with several items (Methodology) Simple heuristic decision rules (Citations) Similar analyses for other sequencing problems: [Kle76, Ana89]; optimization algorithms: [LuG75,

Zip80b, IbK88] (Notes) Shows that simple rules exist (such as one that maximizes the time between stockouts) that behave

asymptotically optimally, in the sense that as the number of orders tend to infinity the allocation policy tend to be optimal.

[KoL98] M. S. Kodialam and H. Luss, Algorithms for separable nonlinear resource allocation problems

(Problem) ϕ_{j} strictly increasing; g_{j} strictly decreasing; ϕ′_{j}/g′_{j} strictly increasing and invertible; l_{j} = 0;

u_{j} = ∞; Slater CQ (Origin) Same; application mentioned: the service constrained problem (Methodology) Two Lagrange multiplier algorithms: (a) ranking (denoted RANK) à la [LuG75] (and

[Tan88] for a minimax version); and (b) bisection search (denoted EVALUATE) à la [Zip80b] (and [Lus91] for a minimax version); also presents a pegging algorithm (denoted RELAX) à la [BiH81], cf. Section 3.2, and a combination with RANK (denoted RELAX/RANK) in which sorting is first performed, then followed by the division of the problem into two roughly equal parts, each of which is solved with RELAX and RANK, respectively (cites [Ein81, Lus92] for this combination)

(Citations) Algorithms for the problem: [ChC58b, WiG69, LuG75, Zip80b, BiH81, Ein81, IbK88, GSAB93,

BrS95]; for the minimax problem: [LuS86, Lus87, Tan88, Lus91, Lus92] (Notes) Extends the three algorithms in a natural manner to the general bounded case, citing [LuG75,

BiH81, GSAB93], but without an analysis. Conclude through numerical experiments (n = 10^{4}) that pegging (RELAX) is best when the multiplier value μ̄ is available explicitly (followed by RANK and EVALUATE), otherwise EVALUATE is much better; RANK however suffers much when lacking explicit solutions, since inversions are needed at every iteration. Notes that if RANK is supplied with bisection search then RANK = EVALUATE follows. Investigates the effect on the algorithms on the relative number of positive variables at the optimum; RANK is the most sensitive to this number, and fares worse with an increased number of positive values, since RANK is initialized at zero; RELAX spends the most time in providing a first Lagrange multiplier estimate.

[MaD89] N. Maculan and G. G. de Paula, Jr, A linear-time median-finding algorithm for projecting a vector on the simplex of ℝ^{n}

(Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear equality (a_{j} = 1, b = 1); l_{j} = 0, u_{j} = ∞ (Methodology) Median search (Citations) [AHU74] for the O(n) complexity of median search; [HWC74] for uses of projections onto a

simplex [MMP97] N. Maculan, M. Minoux, and G. Plateau, An O(n) algorithm for projecting a vector on the

intersection of a hyperplane and ℝ_{+}^{n}

(Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear equality (a_{j} ≠ 0); l_{j} = 0, u_{j} = ∞ (Methodology) Two methods: bisection search and median search (Citations) [AHU74] for the O(n log n) and O(n) complexity of sorting and median search, respectively;

[Mic86] for an alternative method (but “without detailed complexity analysis”); [MaD89] for a special case

[MeR00] A. Melman and G. Rabinowitz, An efficient method for a class of continuous nonlinear knapsack problems

(Problem) ϕ_{j}(x_{j}) = ϕ(x) = x[exp(−1/x) − 1]; linear inequality (a_{j} > 0); l_{j} = 0, u_{j} = ∞ (Origin) Determining the optimal frequency of waste removal services in chemical production processes (Methodology) A modified Newton method based on Halley’s method (Citations) Lagrange multiplier methods: [Bec52, CAA57] (“trial–and–error”), [Zie82, Vid87] (“rigorous

methods”); Halley’s method: [Tra64] (Notes) Numerical experiments (n ∈ [500, 3000])

[MSMJ03] N. Maculan, C. P. Santiago, E. M. Macambira, and M. H. C. Jardim, An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in ℝ^{n}

(Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear equality (a_{j} ≠ 0) (Methodology) Median search (Citations) Previous algorithms: [MaD89, MMP97], [Bru84, Mic86, PaK90]; refers to the use of projections

in subgradient techniques in [HWC74, KeS77] (Notes) Computational results (n ∈ [10^{4}, 10^{6}]) confirm the linearity of the complexity. States that the

references [Bru84, PaK90] were, during the refereeing process, provided by K. C. Kiwiel; states that [Bru84] “does not use the KKT optimality conditions”, and refers to four contributions of the paper, out of which the one theoretical result (Lemma 2.1) was not new in 2003

[Spi02] H. Spiess, Biproportional matrix balancing with upper bounds

(Problem) ϕ_{j}(x_{j}) = x_{j}(log x_{j} − r_{j}), linear equality (a_{j} = 1); l_{j} = 0 (Origin) An extension of the matrix balancing problem in transportation planning with the addition of

upper bounds; parallel subproblems in coordinate dual ascent method for the problem (Methodology) Ranking (Citations) Matrix balancing problems: [Fur70, Mur77, LaS81] (Notes) Notes that the methodology probably can be extended also to multi-proportional problems and

three-dimensional matrix balancing

[HaP04] W. W. Hager and S. Park, The gradient projection method with exact line searches

(Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − [y_{j} + αp_{j}])^{2}, α ≥ 0; linear equality (a_{j} > 0); l_{j} = 0, u_{j} = 1 (Origin) Exact line search in the gradient projection algorithm, applied to a reformulation of the graph

partition problem as a continuous quadratic programming problem; a parametric projection problem to find the piecewise linear projections Proj_{X}[y + αp] over an interval in the step length α

(Methodology) Explicit enumeration of breakpoints (Citations) Subproblem algorithms: [Bru84, PaK90]

[DaF06] Y.-H. Dai and R. Fletcher, New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (Origin) Same; also a subproblem in a gradient projection method for a quadratic problem with a non-

diagonal Hessian (Methodology) Bracketing followed by a secant method (Citations) Previous algorithms: [HKL80, Bru84, CaM87, PaK90] (Notes) Includes a device for checking the consistency of the problem. Extended to the non-convex case.

Numerical experiments on randomly generated problems (n ∈ [10^{4}, 10^{6}]) against bisection search; the proposed method wins by a factor of 1.5–4 [Lot06] P. A. Lotito, Issues in the implementation of the DSD algorithm for the traffic assignment problem

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} ≥ 0; linear equality (a_{j} = 1, b = 1); l_{j} = 0, u_{j} = ∞

(Origin) Subproblem for each origin–destination pair in the traffic assignment problem within the scaled

reduced gradient method of [LaP92] (Methodology) A Newton method, wherein q′′, at breakpoints where it is not defined, is replaced by the

left (right) derivative of q′ when q′ is negative (positive) (Citations) Refers to [HKL80, Bru84, PaK90] for the case when q_{j} > 0 for all j, and to [NiZ92] for a similar

Newton method (Notes) Numerical experiments on median search, randomized median search and the proposed Newton

method (n ∈ [100, 400]); they show similar performance and complexity, but the Newton method is slightly faster. Has observed in actual iterative use for the traffic assignment problem that the latter is even faster. Vectorized implementations are also shown to be more easily constructed for the Newton method, due to the avoidance of any binary search

3.2 Primal “pegging” algorithms

3.2.1 Introduction

A pegging algorithm for the problem (1) works as follows: We first determine whether the constraint (1a) is satisfied with equality at an optimal solution, by solving (1) while ignoring the constraint (1a); see the discussion in Section 1. Unless we then have already found an optimal solution, we know that μ^{∗} > 0 and that the inequality constraint can be regarded as an equality.

Next, we solve the problem (1) while ignoring the constraints (1b), obtaining a solution x̄. Together with x̄ we also obtain an estimate μ̄ of the multiplier value μ^{∗} from the optimality condition. Let

L(x̄) := { j = 1, …, n | x̄_{j} < l_{j} }, U(x̄) := { j = 1, …, n | x̄_{j} > u_{j} }

denote the sets of variables that are out of bounds at x̄. Let also J(μ̄) := { j = 1, …, n | l_{j} < x̄_{j} < u_{j} }.

In order to simplify the remaining discussion, we consider the simplest form of explicit constraint, namely ∑_{j=1}^{n} x_{j} = b; the general case is treated analogously.

Calculate the total deficit and excess with respect to the set X at x̄ as

∇ := ∑_{j∈L(x̄)}(l_{j} − x̄_{j}), Δ := ∑_{j∈U(x̄)}(x̄_{j} − u_{j}).

Now, if Δ ≥ ∇ then we set x_{j}^{∗} = u_{j}, j ∈ U(x̄); otherwise, we set x_{j}^{∗} = l_{j}, j ∈ L(x̄). We then reduce the problem by removing the fixed variables, and adjust the right-hand side of the constraint (1b) to reflect the variables fixed. If any free variables are left, we resolve the problem (1) while ignoring the constraint (1b), otherwise we have obtained an optimal solution.

The rationale behind this procedure is quite simple and natural: Suppose that Δ ≥ ∇ holds. We have that μ̄ = −ϕ′_{j}(x̄_{j}) for j ∈ J(μ̄). Let s ∈ U(x̄) and i ∈ {1, …, n} \ U(x̄). Since the functions ϕ_{j} are convex, it follows that

−ϕ′_{s}(u_{s}) ≥ −ϕ′_{s}(x̄_{s}) = μ̄ = −ϕ′_{i}(x̄_{i}) ≥ −ϕ′_{i}(u_{i}).

Denote by b_{+} the right-hand side in the following iteration given that Δ ≥ ∇ holds: b_{+} := b−∑_{j∈U(x̄)} x̄_{j}. Also let (x̂, μ̂) denote a pair of relaxed optimal primal–dual solutions in the following iteration. We must have that μ̂ ≤ μ̄, since

∑_{j∈{1,...,n}\U(x̄)} x̄_{j} = b − ∑_{j∈U(x̄)} x̄_{j} ≤ b − ∑_{j∈U(x̄)} u_{j} = b_{+} = ∑_{j∈{1,...,n}\U(x̄)} x̂_{j};

hence, for at least one j ∈ {1, …, n} \ U(x̄) we have that x̂_{j} ≥ x̄_{j}, and therefore, by the convexity of ϕ_{j},

μ̂ = −ϕ_{j}(x̂_{j}) ≤ −ϕ_{j}(x̄_{j}) = μ̄

follows.

Since in each iteration at least one variable is fixed (or, pegged, as it is sometimes called) to an optimal value, the algorithm is clearly finite, and in fact its complexity is O(n^{2}). The most serious disadvantage of the algorithm may be the requirement that the problem without the variable bounds present must have an optimal solution. The computational efficiency of this method is also determined by whether or not it is possible to provide an explicit formula for each x̄_{j} in terms of the multiplier; this is of course always possible when for each j ϕ_{j} is strictly convex quadratic and g is linear with a_{j} ≠ 0. The methodology on the other hand has the clear advantage that at least for linear explicit constraints convergence of the method only requires the functions ϕ_{j} to be convex; this is in contrast with the Lagrange multiplier methods to be discussed in Section 3.1, and which require them to be strictly convex.

Variations of the above theme does exist. One such variation is such that one of the bounds is relaxed in the constraints (1c), and that the resulting subproblems are solved with a pegging algorithm with respect to the non-relaxed bounds; hence, a recursive pegging algorithm, which is how we will refer to them. A second variation is that the pegging is based on the feasibility with respect to the constraint (1a) at the projected vector

x̂ := Proj_{∏_{j=1}^{n} X_{j}} x̄,

that is, consider letting

x̂_{j} := l_{j}, j ∈ L(x̄);  x̂_{j} := u_{j}, j ∈ U(x̄);  x̂_{j} := x̄_{j}, j ∈ {1, …, n} \ (L(x̄) ∪ U(x̄)).

Then, if g(x̂) > 0 we set x_{j}^{∗} = l_{j}, j ∈ L(x̂); if g(x̂) < 0 we set x_{j}^{∗} = u_{j}, j ∈ U(x̄); if g(x̂) = 0 then x^{∗} = x̂. We will refer to this variation as a projected pegging method.

To summarize the above class of methods, we may say that the methods are explicitly primal, since they in each step decide on the optimal value of at least one of the variables x_{j}. They are on the other hand also implicitly dual, since they in each step update upon the dual variable μ towards its optimal value based on the current values of the primal variables.

Apart from the below references, motivations for the pegging activities can also be found in [Thv60, Boo63, Boo64, Geo70a, Geo70b, Geo70c, Geo72]. A simple modification of the pegging method is also found in [YaS87].

3.2.2 Annotated bibliography

[San71] L. Sanathanan, On an allocation problem with multistage constraints

(Problem) General: ϕ_{j} ∈ C^{2}, ϕ′′_{j} > 0; linear equality (a_{j} ≠ 0); l_{j} = −∞, u_{j} = ∞ possible. Application:

ϕ_{j}(x_{j}) = c_{j}/x_{j}, c_{j} > 0

(Origin) Same. Application to optimal allocation in stratified sampling subject to restrictions on strata

estimates, capital budgeting and multistage sampling (Methodology) Recursive pegging algorithm (Citations) [Sri63, Kis65] (Notes) Numerical experiments (n = 6); same problem as in [Sri63]. Presents a Lagrange multiplier method

à la [Sri63] for the problem; cf. Section 3.1. The purpose of the paper is to introduce pegging as an alternative approach, with the advantage that pegging can be extended to certain multi-stage problems.

[LuG75] H. Luss and S. K. Gupta, Allocation of effort resources among competing activities

(Problem) ϕ_{j} strictly convex and increasing, linear inequality (a_{j} = 1)

(Origin) Applications: allocating an advertising budget among n sales territories, portfolio selection, and

budgeting (Methodology) Recursive pegging algorithm (Notes) For the submodels, the algorithm is a Lagrange multiplier method which utilizes sorting of primal

derivatives (“ranking”), hence the strong requirements on ϕ_{j}; cf. Section 3.1

[BiH77] G. R. Bitran and A. C. Hax, On the design of hierarchical production planning systems

(Problem) Family disaggregation production planning model; ϕ_{j}(x_{j}) = c_{j}/x_{j}, c_{j} > 0; linear equality (a_{j} =

1) (Origin) Hierarchical production planning problem (Methodology) Pegging (Citations) [BiH79] (Notes) Small numerical tests. Extends the algorithm to the inequality case

[BiH79] G. R. Bitran and A. C. Hax, On the solution of convex knapsack problems with bounded variables (Problem) Linear equality (a_{j} = 1) (Origin) Same (Methodology) Pegging (Citations) [ChC58b, WiG69, LuG75, BiH77] (Notes) Numerical experiments (n ∈ [50, 200]). Proves that if ∇ > Δ in some iteration then the value of μ̄

will decrease in the next iteration

[BiH81] G. R. Bitran and A. C. Hax, Disaggregation and resource-allocation using convex knapsack-problems with bounded variables

(Problem) Linear equality (a_{j} = 1); l_{j} = −∞ and u_{j} = ∞ possible (Origin) Production planning and scheduling, allocation of financial resources, inventory control (Methodology) Pegging. Algorithm referred to as BRELAX2 in [IbK88, Section 2.3] (Citations) Applications: [ChC58b, WiG69, HWC74, LuG75, BiH77, BHH81]; algorithms: [ChC58b] (“con-

vex programming arguments”), [WiG69] (dynamic programming), [LuG75] (iterative algorithm), [Zip80b] (extension of the algorithm in [LuG75])

(Notes) Similar to [BiH79]

[Zip80b] P. H. Zipkin, Simple ranking methods for allocation of one resource

(Problem) ϕ_{j} strictly convex, linear equality (a_{j} = 1); l_{j} = 0 (Methodology) For the general problem: recursive pegging, citing [LuG75]. Algorithm referred to as BRE-

LAX1 in [IbK88, Section 2.3]. For the singly bounded problems (u_{j} = ∞), cites the Lagrange multiplier method from [LuG75], and also presents a modification, likewise based on the ranking of primal derivatives; cf. Section 3.1.

(Citations) Applications: optimal search effort ([ChC58b]), marketing ([LuG75]), capital budgeting ([Han68, p. 81]), production ([BiH77]), aggregation errors ([Zip80a]), portfolio selection ([Jud75, EGP76]), reliability ([Bod69]), health care ([Fet73]), and multicommodity flows ([HWC74]). Algorithms: cites the Lagrange multiplier method in [LuG75] as subsuming [ChC58b, WiG69]; discusses also the pegging algorithm from [BiH77] (wrongly supposing that only one variable can be pegged at any given iteration) and the Lagrange multiplier methods from [Bod69, HWC74, Jud75]. Further citations: [Koo57, deG61, Kar62, Eve63, Geo70a, Geo70b, GrP70]

(Notes) Perhaps the first survey on algorithms for the problem, providing a unified presentation of some previous work. For the singly bounded submodels, the algorithm is a Lagrange multiplier method, hence the strong requirements on ϕ_{j}; cf. Section 3.1

[Mic86] C. Michelot, A finite algorithm for finding the projection of a point onto the canonical simplex of ℝ^{n}

(Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear equality (a_{j} = 1, b = 1); l_{j} = 0, u_{j} = ∞ (Methodology) Pegging (Citations) Projections onto general polyhedra: [Wol74, Wol76, BGR78] (Notes) Extends the algorithm to a more general setting (a_{j} > 0)

[IbK88] T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches

(Problem) Linear equality (a_{j} = 1) (Origin) Resource allocation problem from several areas (Methodology) Pegging (the algorithm BRELAX2 from [BiH81]) or recursive pegging (first converting the

set to X_{j} to [0, u_{j}], then utilizing the Lagrange multiplier algorithm BRELAX1 from [Zip80b]); pegging (the algorithm from [BiH81], then denoted RELAX) for the special case of X_{j} = [0, u_{j}]

(Citations) Applications: optimal search effort ([Koo53, Koo56a, Koo56b, Koo57, ChC58b, Kar58, Kar62]), optimal sample allocation in stratified sampling ([Ney34, Sri63]), optimal portfolio selection ([Mar52, Mar59, Sha63, Sto73, Jud75, EGP76, Zip80b]), production planning ([BiH77, BHH81, BiH81, Zie82]), resource distribution ([FeZ83, FeZ84]), mass advertising ([Kot71]; here, ϕ_{j} is “S-shaped”), marketing effort allocation ([Lus73]), reliability problems ([Bod69]), bidding for oil and gas ventures ([FeG86]), allocation of people to evacuation routes ([Fra78]), subproblems in subgradient algorithms ([HWC74]), the apportionment problem ([BaY82]). Algorithms for continuous problems: pegging algorithms ([Zip80b, BiH81]), Lagrange multiplier methods ([LuG75, HKL80, OhK80, Zip80b, Was81, Bru84]), and variations ([Ein81])

(Notes) Comprehensive overview of the linearly constrained allocation problem with extensions to minimax/maximin, lexicographic minimization, submodular and integrality constraints, and more. Notes that the RELAX algorithms can be extended to the case of non-differentiable functions ϕ_{j}

[Ven91] J. A. Ventura, Computational development of a Lagrangian dual approach for quadratic networks

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (Origin) Line search subproblem in the Polak–Ribière [PoR69] dual ascent method for the quadratic trans-

portation problem (Methodology) Pegging (extends the algorithm from [BiH81] to allow for non-unit coefficients in the linear

equality constraint); also discusses two Lagrange multiplier methods based on bisection search (the method from [HKL80] and a random search method); cf. Section 3.1

(Citations) Pegging methods ([BiH81]), Lagrange multiplier methods for network flow problems ([BaK80,

CoP82, OhK84, CDZ86, BeE87, BHT87, LiP87]) (Notes) Numerical experiments (n ∈ [50, 500]) on NETGEN generated networks, using Merge sort [O(n log n)]

for the sorting; pegging wins, followed by random search and the method from [HKL80]

[RJL92] A. G. Robinson, N. Jiang, and C. S. Lemke, On the continuous quadratic knapsack problem

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} > 0); transforms the problem before solution

to ϕ_{j}(x_{j}) = \frac{1}{2} x_{j}^{2} (Methodology) Pegging (perhaps the first time the term is mentioned) (Citations) Applications: multicommodity flows ([AHKL80]), traffic equilibrium ([DaS69]), quadratic trans-

portation ([OhK84]), matrix balancing in regional and national economics ([CDZ86, NKR90, NaR92]), convex quadratic programming ([CDZ86]), portfolio selection ([Jud75, Pan80]); references to other pegging algorithms ([Mic86], pointed out by a referee), and Lagrange multiplier methods ([DaS69, HWC74, HKL80, Bru84, CDZ86])

(Notes) Numerical experiments (n ∈ [100, 4000]) against three Lagrange multiplier algorithms (the dual line search methods from [HKL80, Bru84, PaK90]) and a rough dual Newton method, cf. Section 3.1; the pegging algorithm wins against all the three Lagrange multiplier methods and is comparable to the Newton method

[KoL98] M. S. Kodialam and H. Luss, Algorithms for separable nonlinear resource allocation problems

(Problem) ϕ_{j} strictly increasing; g_{j} strictly decreasing; ϕ′_{j}/g′_{j} strictly increasing and invertible; l_{j} = 0;

u_{j} = ∞; Slater CQ (Origin) Same; application mentioned: the service constrained problem (Methodology) Pegging (denoted RELAX) à la [BiH81]; also presents two Lagrange multiplier algorithms

(denoted RANK and EVALUATE), cf. Section 3.1, and an algorithm combination (denoted RE-LAX/RANK) in which sorting is first performed, then followed by the division of the problem into two roughly equal parts, each of which is solved with RELAX and RANK, respectively (cites [Ein81, Lus92] for this combination)

(Citations) Algorithms for the problem: [ChC58b, WiG69, LuG75, Zip80b, BiH81, Ein81, IbK88, GSAB93,

BrS95]; for the minimax problem: [LuS86, Lus87, Tan88, Lus91, Lus92] (Notes) Also extends the three algorithms in a natural manner to the general bounded case, citing [LuG75,

BiH81, GSAB93], but without an analysis. Conclude through numerical experiments (n = 10, 000) that pegging (RELAX) is best when the multiplier value μ̄ is available explicitly (followed by RANK and EVALUATE), otherwise EVALUATE is much better; RANK however suffers much when lacking explicit solutions, since inversions are needed at every iteration. Notes that if RANK is supplied with bisection search then RANK = EVALUATE follows. Investigates the effect on the algorithms on the relative number of positive variables at the optimum; RANK is the most sensitive to this number, and fares worse with an increased number of positive values, since RANK is initialized at zero; RELAX spends the most time in providing a first Lagrange multiplier estimate.

[BSS96] K. M. Bretthauer, B. Shetty, and S. Syam, A projection method for the integer quadratic knapsack problem

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear equality (a_{j} > 0) (Origin) Same problem with integral requirements on x, solved by means of continuous relaxation and

branch–and–bound (Methodology) Pegging (Citations) Lagrangian multiplier method for the problem: [BSS95]; recent projection method: [RJL92]

which is modified in the present paper; other methods: [HKL80, PaK90, ShM90, NiZ92] (Notes) Provides a modified version of the method of [RJL92] through which an a priori problem conversion

becomes unnecessary. Numerical example (n = 5). Compares two implementations for the original problem, using the Lagrange multiplier method from [HKL80] and the modified pegging algorithm from [RJL92] (n ∈ [50, 100]); pegging wins in CPU time by a factor of 3–4

[BrS97] K. M. Bretthauer and B. Shetty, Quadratic resource allocation with generalized upper bounds

(Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear inequality (a_{j} > 0) (Origin) Quadratic resource allocation with generalized upper bounds solved through Lagrangian relaxation (Methodology) Pegging (Citations) Bisection search ([HKL80]); pegging ([RJL92]); other methods for the problem ([LuG75, BiH81,

FeZ83, MSM83, Bru84, DMS88, IbK88, PaK90, ShM90, NiZ92, BKP93]); an O(n) algorithm for a more general problem ([MeT93])

(Notes) Provides a modified version of the pegging algorithm from [RJL92] through which an a priori problem conversion becomes unnecessary. Numerical experiments (n ∈ [100, 1500]) on easy and hard problems (related to the number of variables that are not on any of the bounds at x^{∗}); compares bisection search, pegging, and the general-purpose GRG algorithm from [SmL92]; pegging wins marginally over bisection search, while both are reported to be more than 4000 times faster than GRG

[BRS99] K. M. Bretthauer, A. Ross, and B. Shetty, Nonlinear integer programming for optimal allocation in stratified sampling

(Problem) ϕ_{j}(x_{j}) = c_{j}/x_{j}, c_{j} > 0; linear inequality (a_{j} > 0) (Origin) Same problem with integral requirements on x, solved by means of continuous relaxation and

branch–and–bound (Methodology) Pegging (Citations) Stratified sampling ([Coc77]); pegging algorithms for the continuous relaxation ([BiH81, RJL92]);

Lagrange multiplier methods ([HKL80, PaK90, NiZ92, BrS95]); other studies of the problem ([Sri63, MSM86, IbK88])

(Notes) Notes that a dual line search is also possible to use, but refers to it as an infinite procedure. Numerical experiments [n ∈ [5, 200] (easy problems), n ∈ [5, 20] (hard problems), n ∈ [75, 200] (easy problems)]; compares pegging and a Lagrange multiplier method (given by an unidentified generic nonlinear solver taken from [PFTV90]) together with a general B & B code, as well as a problem conversion/linearization into a linear 0/1 problem from [MSM86, Hoc95]; on easy problems the latter wins over pegging by a great margin, and the Lagrange multiplier method is a factor of nearly 10 slower; on the hard problems the conversion method does not converge within time limits on the largest instances, while pegging wins over the Lagrange multiplier method with a factor of about 6.

[BrS02a] K. M. Bretthauer and B. Shetty, A pegging algorithm for the nonlinear resource allocation problem

(Problem) ϕ_{j} ∈ C^{2}; g_{j} ∈ C^{2}. Case I: ϕ_{j} increasing, g_{j} decreasing, x̄_{j} increasing in μ̄. Case II: ϕ_{j} decreasing,

g_{j} increasing, x̄_{j} decreasing in μ̄ (Origin) Discrete extension of same problem, solved through continuous relaxation and branch–and-bound (Methodology) Pegging. Case I: if ∑_{j∈L}[g_{j}(l_{j})−g_{j}(x̄_{j})] > ∑_{j∈U}[g_{j}(x̄_{j})−g_{j}(u_{j})] then peg wrt. U, otherwise

peg wrt. L. Case II: if ∑_{j∈L}[g_{j}(l_{j}) − g_{j}(x̄_{j})] < ∑_{j∈U}[g_{j}(x̄_{j}) − g_{j}(u_{j})] then peg wrt. U, otherwise peg wrt. L.

(Citations) Applications of the original problem: [Coc63, GeK77, MSM83, HaC84, IbK88, BSSW94]; algorithms: [HKL80, BiH81, Bru84, IbK88, PaK90, ShM90, NiZ92, RJL92, BKP93, BrS95, BSS95, BSS96, BrS97, KoL98]

(Notes) Show that in both cases I and II ∑_{j∈L}[g_{j}(l_{j}) − g_{j}(x̄_{j})] > ∑_{j∈U}[g_{j}(x̄_{j}) − g_{j}(u_{j})] implies that the value of μ̄ will increase in the next iteration. Discusses the differences between having access to x̄ explicitly (such as in the strictly convex quadratic minimization case with a linear constraint) or not

[BrS02b] K. M. Bretthauer and B. Shetty, The nonlinear knapsack problem—algorithms and applications

(Problem) Same as in [BrS02a] (Origin) Discrete extension of same problem, solved through continuous relaxation and branch–and-bound (Methodology) Same as in [BrS02a] (Citations) Applications: financial ([MSM83]), production and inventory management ([Zie82, VeK88,

MaK93, BSSW94]), stratified sampling ([Coc63]), optimal design of queueing network models in manufacturing ([BiT89]), and computer systems ([GeK77]); algorithms: [Zip80b, BiH81, FeZ83, Bru84, IbK88, PaK90, ShM90, NiZ92, RJL92, BrS95, KoL98, BrS02a]. Cites also algorithms for the integer problem and algorithms for the non-convex continuous problem.

(Notes) Survey paper on applications and algorithms

[BSS03] K. M. Bretthauer, B. Shetty, and S. Syam, A specially structured nonlinear integer resource allocation problem (Problem) ϕ_{j}(x_{j}) = c_{j}/x_{j} + b_{j}x_{j}, c_{j} > 0, b_{j} > 0, or ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear inequality (a_{j} > 0) (Origin) Capacity planning problems in health care and production planning and portfolio optimization

problems with additional GUB constraints (and with/without integer variable requirements), solved through Lagrangian relaxation of the coupling resource constraints and a dual line search (and branch– and–bound)

(Methodology) Pegging (Citations) Previous pegging algorithms: [BiH81, IbK88, RJL92, KoL98, BrS02a] (Notes) Numerical experiments on randomly generated problems (n ∈ [10, 5000])

[Ste00] S. M. Stefanov, On the implementation of stochastic quasigradient methods to some facility location problems (Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear (in)equality (a_{j} > 0) (Origin) Projection subproblem in a stochastic quasigradient method (Methodology) Projected pegging (Citations) [RoW88, Ste01a] (Notes) States that the algorithm has an O(n^{2}) complexity. Small numerical examples (n ∈ {5, 6})

[Ste01a] S. M. Stefanov, Convex separable minimization subject to bounded variables

(Problem) ϕ_{j} ∈ C^{2}, strictly convex; g_{j} ∈ C^{2}, g′_{j} > 0 and bounded away from zero; general constraint as

well as linear (in)equality (a_{j} > 0); l_{j} = −∞, u_{j} = ∞ possible (Methodology) Projected pegging (Citations) Applications: [ChC58b, HWC74, LuG75, Zip80b, BiH81, RoW88, Ste00]; algorithms: [LuG75,

HKL80, Zip80b, BiH81, Bru84, Mic86, PaK90, MoV91, Ste00] (Notes) Numerical experiments (n ∈ [1200, 1500]). Does not present any relationships between the pro-

jected pegging method proposed and the pegging methods cited

[Ste01b] S. M. Stefanov, Separable Programming: Theory and Methods

(Problem) ϕ_{j} ∈ C^{2}, strictly convex; g_{j} ∈ C^{2}, g′_{j} > 0 and bounded away from zero; general constraint as

well as linear (in)equality (a_{j} > 0); l_{j} = −∞, u_{j} = ∞ possible (Origin) Same; also applied to the problem from [Ste00] (Methodology) Projected pegging from [Ste01a] (Citations) Algorithms: [Dun77, McC79, CDZ86, LiP87], in addition to those in [Ste01a] (Notes) Text similar to that of [Ste01a]

[Ste04a] S. M. Stefanov, Convex quadratic minimization subject to a linear constraint and box constraints (Problem) ϕ_{j}(x_{j}) = \frac{q_{j}}{2} x_{j}^{2} − r_{j}x_{j}, q_{j} > 0; linear (in)equality (a_{j} > 0); l_{j} = −∞, u_{j} = ∞ possible (Methodology) Projected pegging (Citations) Algorithms: [ChC58b, HWC74, LuG75, McC79, HKL80, Bru84, DFL86, Mic86, RoW88, PaK90,

RJL92, Ste00, Ste01a, Ste01b, Ste04b] (Notes) Numerical experiments (n ∈ [1200, 1500])

[Ste04b] S. M. Stefanov, Polynomial algorithms for projecting a point onto a region defined by a linear constraint and box constraints (Problem) ϕ_{j}(x_{j}) = \frac{1}{2} (x_{j} − y_{j})^{2}; linear (in)equality (a_{j} > 0); l_{j} = −∞, u_{j} = ∞ possible (Methodology) Projected pegging (Citations) Algorithms: [ChC58b, HWC74, LuG75, KIM79, BiH81, Bru84, Mic86, RoW88, Ste00, Ste01a,

Ste01b, Ste02, Zip80b]

4 Analysis, comments and future research

We summarize the above bibliographies of the two main algorithm approaches for the problem (1), by listing the—in our opinion—main contributions, sorted in chronological order:

[Bec52] The first algorithm

[ChC58b] The first practical and convergent algorithm

[ChC58b] The first explicit use of breakpoints in a Lagrange multiplier algorithm

[Sri63] The first bisection algorithm

[Sri63] The first algorithm for a general form of ϕ_{j}

[Bod69] The first algorithm for the parametric problem (over the values of the RHS b)

[DaS69] The first numerical experiment with n > 10

[San71] The first (recursive) pegging algorithm

[San71] The first article to discuss both pegging and Lagrange multiplier algorithms

[LuG75] The first article to discuss the value of having an explicit formula for x(μ)

[BiH77] The first true pegging algorithm, together with convergence theory

[HKL80] The first complexity analysis of a Lagrange multiplier algorithm

[Zip80b] The first survey on algorithms

[Zip80b] The first discussion on the reoptimization of the problem for small changes in the data; utilizes the previous value of μ^{∗}

[Ein81] The first numerical solution of the Lagrangian minimization problem

[Zie82] The first Newton-type algorithm for the problem

[FeZ83] The first mention of reoptimization of the problem through the re-ordering of the list of breakpoints [CDZ86] The first serious computational study

[CaM87] The first discussion on the value of solving the Lagrangian dual problem even when the original problem is inconsistent

[IbK88] The first comprehensive survey

[IbK88] The first collected treatise on extensions of the problem (to integer variables, maximin problems, non-differentiable functions ϕ_{j}, etcetera)

[RoW88] The first algorithm for a general form of g_{j}

[Ven89] The first numerical comparison between pegging and Lagrange multiplier algorithms

[Ven89] The first hybrid pegging/Lagrange multiplier algorithm

[NiZ92] The first theoretical analysis of a Newton algorithm for the Lagrangian dual problem

[NiZ92] The first (massively) parallel implementation

[KoL98] The most complete computational study

[KoL98] The first pegging algorithm for the general problem

[BrS02a] The first pegging algorithm analyzed for the general problem

In Table 1 we summarize the appearance of articles on the two main algorithmic approaches, among the articles presented in the above bibliographies.

Decade  50s 60s 70s 80s 90s 00s Σ
Lagrange multiplier algorithms  2  4  5 21 19  6 57
Primal “pegging” algorithms  — —  4  4  6  8 22

Table 1: Number of articles on each algorithm class through the decades. Note that the three papers [Vid84, Vid86, Vid87] on Lagrange multiplier methods are only counted once.

It is apparent from the above list and Table 1 that most of the development of Lagrange multiplier algorithms occurred in the 1980s and the early 1990s while the development of pegging algorithms has continued to increase over the decades, albeit at a smaller scale. Notice that noone actually has yet proposed a Lagrange multiplier algorithm for the general problem (1), although it is of course straightforward.

The development of numerical experiments for the problem (1) is illustrated in Table 2, where we cite the size of the largest test problem reported during each decade.

Based on the above list of articles it appears that a short story on how to solve the problem (1) goes as follows: to utilize a pegging algorithm, unless one has access to a near-optimal value of the Lagrange multiplier μ or x(μ) is not available explicitly, whence one should instead use a Lagrange multiplier

Decade  50s 60s 70s 80s 90s 00s
Lagrange multiplier algorithms  2 60 12 200 10^{4} 10^{6}
Primal “pegging” algorithms  — — 200 200 10^{4} 5000

Table 2: Largest instances solved for each algorithm class through the decades.

algorithm. Also, on the latter approach, it is evident that a sorting of the breakpoints should be avoided, unless one needs to solve several similar problems. And: one should not use the ranking approach but instead use bisection or a Newton-like algorithm.

There are some interesting questions and comments that are provoked by reading these articles, and which conclude the paper:

1. Recall that two general convex quadratic programming algorithms reduce to instances of Lagrange multiplier algorithms when considering strictly convex quadratic programming instances of the general problem (1): parametric principal pivoting ([CDZ86]) reduces to ordinal statistics (or, median search), cf. [RJL92], and the complementary pivot algorithm from [Pan80] reduces to bisection search, cf. [DFL86]. Can more general statements be made regarding the connection between quadratic programming algorithms and Lagrange multiplier algorithms?

2. In the above references, no Newton-type algorithm has been analyzed theoretically for a nonquadratic problem; such an analysis is called for, given the success the algorithms have had in numerical experiments.

3. Is it possible to say in general which of the two main approaches is the best to use when solving a certain extension of the problem, such as, say, to integer variables (as in [Gre70, IbK88])?

4. As we have remarked before presenting the bibliographies for each of the two main algorithm classes, there is an issue regarding the solvability of the relaxed problems. It appears that noone has yet proposed a way around that problem, but there is a simple approach for dealing with it: Suppose we apply a proximal point algorithm (e.g., [Roc76a, Roc76b]) for the problem, and use either pegging or a Lagrange multiplier algorithm in each iteration. In the proximal point algorithm we introduce an additive term for each index j into the objective, of the form \frac{γ_{j}^{τ}}{2} (x_{j} − x_{j}^{τ})^{2}, where γ_{j}^{τ} > 0 and x_{j}^{τ} is the value of the variable x_{j} at iteration τ of the proximal point algorithm. This addition means that solvability of the relaxed problem is always guaranteed, and moreover if the problem has (non-strictly convex) quadratic objective terms and the constraint is linear then the relaxed problem has an explicit optimal solution. A few iterations of the proximal point algorithm might produce better solutions than a general tool for solving non-strictly convex programs.

5. In all the above references the only comparison with a “standard” NLP solver has been performed in [BrS97]; the conclusion is that pegging beats a GRG code with a huge factor. This does of course not conclude the debate of whether the best specialized algorithms discussed in this paper are superior to every generally applicable algorithm in nonlinear programming that can utilize the special sparsity of the problem. Numerical tests are planned in the near future to contribute to an answer to this question.

Acknowledgments

The author would like to thank Karin Ljungklint and Martina Ramstedt at the mathematics library, Chalmers University of Technology, for allocating so much effort during 2004 and 2005 in acquiring references. Additional references were obtained by Julia Larsson and Christina Pejlare during the winter of 2005–2006.

References

[AaL90] K. Aardal and T. Larsson, A Benders decomposition based heuristic for the hierarchical production planning problem, European Journal of Operational Research, 45 (1990), pp. 4–14.

[AbS70] J. Abadie and M. Sakarovitch, The methods of decomposition for linear programming, in Proceedings of the Princeton Symposium on Mathematical Programming, H. W. Kuhn, ed., Princeton, NJ, 1970, Princeton University Press, pp. 1–23.

[Agm54] S. Agmon, The relaxation method for linear inequalities, Canadian Journal of Mathematics, 6 (1954), pp. 382–392.

[AHU74] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.

[AHKL80] A. I. Ali, R. V. Helgason, J. L. Kennington, and H. Lall, Computational comparisons among three multicommodity flow algorithms, Operations Research, 28 (1980), pp. 995–1000.

[Ana89] V. Anantharam, The optimal buffer allocation problem, IEEE Transactions on Information Theory, 35 (1989), pp. 116–126.

[Bac70] M. Bacharach, Biproportional Matrices and Input-Output Change, Cambridge University Press, Cambridge, MA, 1970.

[BaK78] A. Bachem and B. Korte, An algorithm for quadratic optimization over transportation polytopes, Zeitschrift für Angewandte Mathematik und Mechanik, 58 (1978), pp. T459–T461.

[BaK80] , Minimum norm problems over transportation polytopes, Linear Algebra and Its Applications, 31 (1980), pp. 103–118.

[BaY82] M. L. Balinski and H. P. Young, Fair Representation—Meeting the Ideal of One Man, One Vote, Yale University Press, New Haven, CT, 1982.

[BaP65] R. E. Barlow and F. Proschan, Mathematical Theory of Reliability, John Wiley & Sons, New York, NY, 1965.

[BaB96] H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), pp. 367–426.

[BGR78] M. S. Bazaraa, J. J. Goode, and R. L. Rardin, An algorithm for finding the shortest element of a polyhedral set with application to Lagrangian duality, Journal of Mathematical Analysis and Applications, 65 (1978), pp. 278–288.

[Bec52] M. J. Beckmann, A Lagrangian multiplier rule in linear activity analysis and some of its applications, Tech. Rep. Economics No. 2054, Cowles Commission Discussion Paper, Chicago, IL, 1952. Summarized in [CAA71] but erroneously dated to 1942.

[Bec67] , On the theory of traffic flow in networks, Traffic Quarterly, 21 (1967), pp. 109–117.

[BMW55] M. J. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the economics of transportation, Research Memorandum RM-1488, The RAND Corporation, Santa Monica, CA, 1955. Available online at the RAND Corporation home page, as the first in a list of RAND Classics. See

http://www.rand.org/publications/electronic/class.html.

[BMW56] , Studies in the Economics of Transportation, Yale University Press, New Haven, CT, 1956.

[BKP93] P. Berman, N. Kovoor, and P. Pardalos, Algorithms for the least distance problem, in Complexity in Numerical Optimization, P. Pardalos, ed., Singapore, 1993, World Scientific, pp. 33–56.

[Ber60] B. Bernholtz, Optimum allocation of discharge to units in a hydro-electric generating station, SIAM Review, 2 (1960), pp. 247–258.

[BeE87] D. P. Bertsekas and D. El Baz, Distributed asynchronous relaxation methods for convex network flow problems, SIAM Journal on Control and Optimization, 25 (1987), pp. 74–85.

[BeG82] D. P. Bertsekas and E. M. Gafni, Projection methods for variational inequalities with application to the traffic assignment problem, Mathematical Programming Study, 17 (1982), pp. 139–159.

[BHT87] D. P. Bertsekas, P. A. Hosein, and P. Tseng, Relaxation methods for network flow problems with convex arc costs, SIAM Journal on Control and Optimization, 25 (1987), pp. 1219–1243.

[BeT89] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, London, U.K., 1989.

[BHH81] G. R. Bitran, E. A. Haas, and A. C. Hax, Hierarchical production planning: A single stage system, Operations Research, 29 (1981), pp. 717–743.

[BHH82] , Hierchical production planning: A two-stage system, Operations Research, 30 (1982), pp. 232– 251.

[BiH77] G. R. Bitran and A. C. Hax, On the design of hierarchical production planning systems, Decision Science, 8 (1977), pp. 28–55.

[BiH79] , On the solution of convex knapsack problems with bounded variables, in Survey of Mathematical Programming, A. Prékopa, ed., vol. 1, Amsterdam, 1979, North-Holland, pp. 357–367.

[BiH81] , Disaggregation and resource-allocation using convex knapsack-problems with bounded variables, Management Science, 27 (1981), pp. 431–441.

[BiM96a] G. R. Bitran and S. V. Mondschein, Inventory management in catalog sales companies, ORSA Journal on Computing, 8 (1996), pp. 274–288.

[BiM96b] , Mailing decisions in the catalog sales industry, Management Science, 42 (1996), pp. 1364–1381.

[BiT89] G. R. Bitran and D. Tirupati, Tradeoff curves, targeting and balancing in manufacturing queueing networks, Operations Research, 37 (1989), pp. 547–564.

[Blu+72] M. R. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, 7 (1972), pp. 448–461.

[Bod69] L. Bodin, Optimization procedures for the analysis of coherent structures, IEEE Transactions on Reliability, r-18 (1969), pp. 118–126.

[Boo63] J. C. Boot, Binding constraint procedures of quadratic programming, Econometrica, 31 (1963), pp. 464–498.

[Boo64] , Quadratic Programming: Algorithms, Anomalies, Applications, vol. 2 of Studies in Mathematical and Managerial Economics, North-Holland, Amsterdam, 1964.

[Bra93] U. Brännlund, On relaxation methods for nonsmooth convex optimization, PhD thesis, Department of mathematics, Royal Institute of Technology, Stockholm, Sweden, 1993.

[Bre67] L. M. Bregman, Proof of the convergence of Sheliekhovskii’s method for a problem with transportation constraints, USSR Computational Mathematics and Mathematical Physics, 7 (1967), pp. 191–204.

[Bre96] K. M. Bretthauer, Capacity planning in manufacturing and computer networks, European Journal of Operational Research, 91 (1996), pp. 386–394.

[BRS99] K. M. Bretthauer, A. Ross, and B. Shetty, Nonlinear integer programming for optimal allocation in stratified sampling, European Journal of Operational Research, 116 (1999), pp. 667–680.

[BrS95] K. M. Bretthauer and B. Shetty, The nonlinear resource allocation problem, Operations Research, 43 (1995), pp. 670–683.

[BrS97] , Quadratic resource allocation with generalized upper bounds, Operations Research Letters, 20 (1997), pp. 51–57.

[BrS02a] , A pegging algorithm for the nonlinear resource allocation problem, Computers & Operations Research, 29 (2002), pp. 505–527.

[BrS02b] , The nonlinear knapsack problem—algorithms and applications, European Journal of Operational Research, 138 (2002), pp. 459–472.

[BSS95] K. M. Bretthauer, B. Shetty, and S. Syam, A branch and bound algorithm for integer quadratic knapsack problems, ORSA Journal on Computing, 7 (1995), pp. 109–116.

[BSS96] , A projection method for the integer quadratic knapsack problem, Journal of the Operational Research Society, 47 (1996), pp. 457–462.

[BSS03] , A specially structured nonlinear integer resource allocation problem, Navel Research Logistics, 50 (2003), pp. 770–792.

[BSSW94] K. M. Bretthauer, B. Shetty, S. Syam, and S. White, A model for resource constrained production and inventory management, Decision Sciences, 25 (1994), pp. 561–580.

[Bro80] S. S. Brown, Optimal search for a moving target in discrete time and space, Operations Research, 28 (1980), pp. 1275–1289.

[Bru84] P. Brucker, An O(n) algorithm for quadratic knapsack problems, Operations Research Letters, 3 (1984), pp. 163–166.

[BuK63] J. Buchan and E. Koeningsberg, Scientific Inventory Management, Prentice-Hall, New Jersey, NJ, 1963.

[CaM87] P. H. Calamai and J. J. Moré, Quasi-Newton updates with bounds, SIAM Journal on Numerical Analysis, 24 (1987), pp. 1434–1441.

[CeH87] Y. Censor and G. T. Herman, On some optimization techniques in image reconstruction from projections, Applied Numerical Mathematics, 3 (1987), pp. 365–391.

[CeL81] Y. Censor and A. Lent, An iterative row-action method for interval convex programming, Journal of Optimization Theory and Applications, 34 (1981), pp. 321–353.

[CeZ97] Y. Censor and S. A. Zenios, Parallel Optimization: Theory, Algorithms, and Applications, Numerical Mathematics and Scientific Computing, Oxford University Press, Oxford, U.K., 1997.

[ChC58a] A. Charnes and W. W. Cooper, Extremal principles for simulating traffic flow in a network, Proceedings of the National Academy of Sciences of the United States of America, 44 (1958), pp. 201– 204.

[ChC58b] , The theory of search: Optimal distribution of search effort, Management Science, 5 (1958), pp. 44–49.

[ChC61a] , Management Models and Industrial Applications of Linear Programming, vol. I, John Wiley & Sons, New York, NY, 1961.

[ChC61b] , Multicopy traffic network models, in Theory of Traffic Flow, Proceedings of the Symposium on the Theory of Traffic Flow Held at the General Motors Research Laboratories, Warren, MI, December 7–8, 1959, R. Herman, ed., Elsevier, Amsterdam, 1961, pp. 85–96.

[ChL54] A. Charnes and C. E. Lemke, Minimization of non-linear separable convex functionals, Naval Research Logistics Quarterly, 1 (1954), pp. 301–312.

[CAA57] C. W. Churchman, R. L. Ackoff, and E. L. Arnoff, Introduction to Operations Research, John Wiley & Sons, New York, NY, first ed., 1957.

[CAA71] , Introduction to Operations Research, John Wiley & Sons, New York, NY, fifth ed., 1971.

[Coc77] W. G. Cochran, Sampling Techniques, John Wiley & Sons, New York, NY, third ed., 19.

[Coc63] , Sampling Techniques, John Wiley & Sons, New York, NY, 1963.

[CoH93] T. F. Coleman and L. A. Hulbert, A globally and superlinearly convergent algorithm for convex quadratic programs with simple bounds, SIAM Journal on Optimization, 3 (1993), pp. 298–321.

[CoK77] L. Cooper and J. L. Kennington, Steady-state analysis of nonlinear resistive electrical networks using optimization techniques, Technical Report IEOR 77012, Department of Operations Research and Engineering Management, School of Engineering and Applied Science, Southern Methodist University, Dallas, TX, 1977.

[CSS04] J. R. Correa, A. S. Schulz, and N. E. Stier Moses, Selfish routing in capacitated networks, Mathematics of Operations Research, 29 (2004), pp. 961–976.

[CoH94] S. Cosares and D. S. Hochbaum, Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources, Mathematics of Operations Research, 19 (1994), pp. 94–111.

[CoL84] G. Côte and M. A. Laughton, Large-scale integer programming: Benders-type heuristics, European Journal of Operational Research, 16 (1984), pp. 327–333.

[Cot72] R. W. Cottle, Monotone solutions of the parametric linear complementarity problems, Mathematical Programming, 3 (1972), pp. 210–224.

[Cot84] , Application of a block successive overrelaxation method to a class of constrained matrix problems, in Mathematical Programming, R. W. Cottle, M. L. Kelmanson, and B. Korte, eds., Amsterdam, 1984, North-Holland, pp. 89–103.

[CDZ86] R. W. Cottle, S. G. Duvall, and K. Zikan, A Lagrangean relaxation algorithm for the constrained matrix problem, Naval Research Logistics Quarterly, 33 (1986), pp. 55–76.

[CoP82] R. W. Cottle and J.-S. Pang, On the convergence of a block successive over-relaxation method for a class of linear complementarity problems, Mathematical Programming Study, 17 (1982), pp. 126–138.

[Cry71] C. W. Cryer, The solution of a quadratic programming problem using systematic overrelaxation, SIAM Journal on Control, 9 (1971), pp. 385–392.

[Cur93] N. D. Curet, On the dual coordinate ascent approach for nonlinear networks, Computers and Operations Research, 20 (1993), pp. 133–140.

[DaN89] S. Dafermos and A. Nagurney, Supply and demand equilibration algorithms for a class of market equilibrium problems, Transportation Science, (1989), pp. 118–124.

[DaS69] S. Dafermos and F. T. Sparrow, The traffic assignment problem for a general network, Journal of Research of the National Bureau of Standards, 73B (1969), pp. 91–118.

[DaF06] Y.-H. Dai and R. Fletcher, New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Mathematical Programming, 106, pp. 403–421.

[Dan62a] J. M. Danskin, A game theory model of convoy routing, Operations Research, 10 (1962), pp. 774–785.

[Dan62b] , A theory of reconnaissance: I, Operations Research, 10 (1962), pp. 285–299.

[Dan62c] , A theory of reconnaissance: I, Operations Research, 10 (1962), pp. 300–309.

[Dan66] , The theory of max-min, with applications, SIAM Journal on Applied Mathematics, 14 (1966), pp. 641–664.

[Dan67] , The Theory of Max-Min and Its Application to Weapons Allocation Problems, Springer-Verlag, Berlin, 1967.

[deG61] J. de Guenin, Optimal distribution of effort: An extension of the Koopman basic theory, Operations Research, 9 (1961), pp. 1–7.

[DeM80] J. L. Debiesse and G. Matignon, Comparison of different methods for the calculation of traffic matrices, Annales des Telecommuncations, 35 (1980), pp. 91–102.

[DeS40] W. E. Deming and F. F. Stephan, On a least-squares adjustment of a sampled frequency table when the expected marginal totals are known, Annals of Mathematical Statistics, 11 (1940), pp. 427–444.

[DEs59] D. D’Esopo, A convex programming procedure, Naval Research Logistics, 6 (1959), pp. 33–42.

[DMS88] M. Djerdjour, K. Mathur, and H. M. Salkin, A surrogate relaxation based algorithm for a general quadratic multidimensional knapsack problem, Operations Research Letters, 7 (1988), pp. 253–258.

[Dun77] F. D. J. Dunstan, An algorithm for solving a resource allocation problem, Operational Research Quarterly, 28 (1977), pp. 839–851.

[Dup1844] J. Dupuit, De la mesure de l’utilité des travaux publics, Annales des Ponts et Chaussées, 8 (1844), pp. 332–375. English translation by R. H. Barback as On the measurement of the utility of public works, published in International Economic Papers 2, A. T. Peacock, R. Turvey, F. A. Lutz and E. Henderson, eds., Macmillan, London, U.K., 1952, pp. 83–110; translation reprinted in [Mun68, pp. 19–57].

[Dup1849] , On tolls and transport charges, (1849). Reprinted in International Economics Papers, 11 (1962), pp. 7–31.

[DFL86] J.-P. Dussault, J. A. Ferland, and B. Lemaire, Convex quadratic programming with one constraint and bounded variables, Mathematical Programming, 36 (1986), pp. 90–104.

[Ein81] J. M. Einbu, Extension of the Luss–Gupta resource allocation algorithm by means of first order approximation techniques, Operations Research, 29 (1981), pp. 621–626.

[ElC79] M. E. El-Hawary and G. S. Christensen, Optimal Economic Operation of Electric Power Systems, Academic Press, New York, NY, 1979.

[EGP76] E. J. Elton, M. J. Gruber, and M. W. Padberg, Simple criteria for optimal portfolio selection, The Journal of Finance, 31 (1976), pp. 1341–1357.

[ErS90] S. Erlander and N. F. Stewart, The Gravity Model in Transportation Analysis: Theory and Extensions, vol. 3 of Topics in Transportation, VSP, Utrecht, The Netherlands, 1990.

[EvK74] S. P. Evans and H. R. Kirby, A three-dimensional Furness procedure for calibrating gravity models, Transportation Research, 8 (1974), pp. 105–122.

[Eve63] H. Everett, III, Generalized Lagrange multiplier method for solving problems of optimum allocation of resources, Operations Research, 11 (1963), pp. 399–417.

[FeG86] A. Federgruen and H. Groenevelt, Optimal flows in networks with multiple sources and sinks, with applications to oil and gas lease investment programs, Operations Research, 34 (1986), pp. 218– 225.

[FeZ83] A. Federgruen and P. Zipkin, Solution techniques for some allocation problems, Mathematical Programming, 25 (1983), pp. 13–24.

[FeZ84] , A combined vehicle routing and inventory allocation. problem, Operations Research, 32 (1984), pp. 1019–1037.

[FLR78] J. A. Ferland, B. Lemaire, and P. Robert, Analytic solutions for non-linear programs with one or two equality constraints, Publication # 285, Département d’informatique et de recherche opérationnelle, Université de Montréal, Montréal, Canada, 1978.

[Fet73] R. Fetter, Modeling health care delivery systems, WP 30, Health Services Research Program, Yale University, 1973.

[FJR05] I. N. Figueiredo, J. J. Júdice, and S. S. Rosa, A class of mathematical programs with equilibrium constraints: A smooth algorithm and applications to contact problems, Optimization and Engineering, 6 (2005), pp. 203–239.

[FoF58] L. R. Ford, Jr. and D. R. Fulkerson, A suggested computation for maximal multi-commodity network flows, Management Science, 5 (1958), pp. 97–101.

[FoF62] , Flows in Networks, Princeton University Press, Princeton, NJ, 1962.

[Fra78] R. L. Francis, A ”uniformity principle” for evacuation route allocation, working paper, Center for Applied Mathematics, National Bureau of Standards, Department of Commerce, Washington, D.C., 1978.

[Fri61] D. Friedlander, A technique for estimating a contingency table given the marginal totals and some supplementary data, Journal of the Royal Statistics Society, A 124 (1961), pp. 412–420.

[Fur62] K. P. Furness, Trip forecasting. Unpublished note, 1962.

[Fur70] , Time function interaction, Traffic Engineering & Control, 7 (1970), pp. 19–36.

[GHS80] G. Gallo, P. L. Hammer, and B. Simeone, Quadratic knapsack problems, Mathematical Programming, 12 (1980), pp. 132–149.

[Geo69] A. M. Geoffrion, An improved implicit enumeration approach for integer programming, Operations Research, 17 (1969), pp. 437–454.

[Geo70a] , Elements of large-scale mathematical programming. part I: Concepts, Management Science, 16 (1970), pp. 652–675. Reprinted in [Geo72], pp. 25–48.

[Geo70b] , Elements of large-scale mathematical programming. part II: Synthesis of algorithms and bibliography, Management Science, 16 (1970), pp. 767–691.

[Geo70c] , Primal resource-directive approaches for optimizing nonlinear decomposable systems, Operations Research, 18 (1970), pp. 375–403.

[Geo71] , Duality in nonlinear programming: A simplified applications-oriented development, SIAM Review, 13 (1971), pp. 65–101. Reprinted in [Geo72].

[Geo72] , Perspectives on Optimization: A Collection of Expository Articles, Addison-Wesley, Reading, MA, 1972.

[GeK77] M. Gerla and L. Kleinrock, On the topological design of distributed computer networks, IEEE Transactions on Communications, com-25 (1977), pp. 48–60.

[Gib1878a] J. W. Gibbs, Abstract of the ”Equilibrium of heterogeneous substances”, American Journal of Science, Serie 3, 16 (1978), pp. 441–458.

[Gib1878b] , On the equilibrium of heterogeneous substances, Transactions of the Connecticut Academy of Arts and Sciences, III (May 1877– July 1878), pp. 343–524. Reprinted in The Scientific Papers of J. Willard Gibbs, Vol. I: Thermodynamics, Longman, 1906; Dover, 1961, pp. 55–353.

[Gib1876] , On the equilibrium of heterogeneous substances, Transactions of the Connecticut Academy of Arts and Sciences, III (October 1875–May 1876), pp. 108–248. Also in The American Journal of Science and Arts (eds. James D. and E. S. Dana, and B. Silliman), Third Series, vol. XVI, no. 96, December 1878. Reprinted in The Scientific Papers of J. Willard Gibbs, Vol. I: Thermodynamics, Longman, 1906; Dover, 1961, pp. 55–353.

[Gla96] P. Glasserman, Allocating production capacity among multiple products, Operations Research, 44 (1996), pp. 724–734.

[Gla78] C. R. Glassey, A quadratic network optimization model for equilibrium of single commodity trade flows, Mathematical Programming, 14 (1978), pp. 98–107.

[Glo68] F. Glover, Surrogate constraints, Operations Research, 16 (1968), pp. 741–749.

[Gof78] J.-L. Goffin, Nondifferentiable optimization and the relaxation method, in Nonsmooth Optimization, C. Lemaréchal and R. Mifflin, eds., Oxford, U.K., 1978, IIASA, Pergamon Press, pp. 31–49.

[Gos1854] H. H. Gossen, Die Entwicklung der Gesetze des menschlichen Verkehrs und der daraus fliessenden Regeln für menschliches Handeln, Friedrich Vieweg und Sohn, Braunschweig, Germany, 1854.

[Gos83] , The Laws of Human Relations and the Rules of Human Action Derived Therefrom, The MIT Press, Cambridge, MA, 1983. Translated by R. C. Blitz.

[Gra71] J. Grad, Matrix balancing, Computing Journal, 14 (1971), pp. 280–284.

[Gre70] H. J. Greenberg, An application of a Lagrangian penalty function to obtain optimal redundancy, Technometrics, 12 (1970), pp. 545–552.

[GrP70] H. J. Greenberg and W. P. Pierskalla, Surrogate mathematical programming, Operations Research, 18 (1970), pp. 924–939.

[GSAB93] S. J. Grotzinger, R. Srinivasan, R. Akella, and S. Bollapragada, Component procurement and allocation for products assembled to forecast: Risk-pooling effects, IBM Journal of Research and Development, 37 (1993), pp. 523–535.

[HaW63] G. Hadley and T. M. Whitin, Analysis of Inventory Systems, Prentice-Hall, Englewood Cliffs, NJ, 1963.

[HaH93] W. W. Hager and D. W. Hearn, Application of the dual active set algorithm to quadratic network optimization, Computational Optimization and Applications, 1 (1993), pp. 349–373.

[HaP04] W. W. Hager and S. Park, The gradient projection method with exact line searches, Journal of Global Optimization, 30 (2004), pp. 103–118.

[Han68] F. Hanssman, Operations Research Techniques for Capital Investment, John Wiley & Sons, New York, NY, 1968.

[Har13] F. W. Harris, How many parts to make at once, Factory, The Magazine of Management, (1913). Reprinted in Operations Research, 38 (1990), pp. 947–950.

[Har15] , Operations and Cost, Factory Management Series, A. W. Shaw & Co., Chicago, IL, 1915.

[HaC84] A. C. Hax and D. Candea, Production and Inventory Management, Prentice-Hall, Englewood Cliffs, NJ, 1984.

[HWC74] M. Held, P. Wolfe, and H. P. Crowder, Validation of subgradient optimization, Mathematical Programming, 6 (1974), pp. 62–88.

[HKL80] R. V. Helgason, J. L. Kennington, and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program, Mathematical Programming, 18 (1980), pp. 338–343.

[Her80] G. T. Herman, Image reconstruction from projections: The fundamentals of computerized tomography, Computer Science and Applied Mathematics, Academic Press, New York, NY, 1980.

[Hil57] C. Hildreth, A quadratic programming procedure, Naval Research Logistics Quarterly, 4 (1957), pp. 79–85. Erratum, ibid., p. 361.

[Hoc94] D. S. Hochbaum, Lower and upper bounds for the allocation problem and other nonlinear optimization problems, Mathematics of Operations Research, 19 (1994), pp.390–409.

[Hoc95] D. S. Hochbaum, A nonlinear knapsack problem, Operations Research Letters, 17 (1995), pp. 103– 110.

[HoH95] D. S. Hochbaum and S.-P. Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Mathematical Programming, 69 (1995), pp. 269–309.

[HoI99] R. Hohzaki and K. Iida, Efficient algorithms for a convex programming problem with a constraint on the weighted total amount, Mathematica Japonica, 52 (1999), pp. 131–142.

[HMMS60] C. C. Holt, F. Modigliani, J. Moth, and H. Simon, Planning Production, Inventories and Work Force, Prentice-Hall, New Jersey, NJ, 1960.

[Hor81] R. Horst, On reducing a resource allocation problem to a single one-dimensional minimzation of a differentiable convex function, Journal of the Operational Research Society, 32 (1981), pp. 821–824.

[IbK88] T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches, no. 4 in Foundations of Computing Series, The MIT Press, Cambridge, MA, 1988.

[JeS79] T. R. Jefferson and C. H. Scott, The analysis of entropy models with equality and inequality constraints, Transportation Research, 13B (1979), pp. 123–132.

[Joh48] F. John, Extremum problems with inequalities as subsidiary conditions, in Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, NY, 1948, pp. 187–204.

[JoM74] L. A. Johnson and D. Montgomery, Operations Research in Production Planning, Scheduling, and Inventory Control, John Wiley & Sons, New York, NY, 1974.

[Jud75] J. V. Jucker and C. de Faro, A simple algorithm for Stone’s version of the portfolio selection problem, Journal of Financial and Quantitative Analysis, (1975).

[Kar39] W. Karush, Minima of functions of several variables with inequalities as side constraints, Master’s thesis, Department of Mathematics, University of Chicago, Chicago, IL, 1939.

[Kar58] , On a class of minimum cost problems, Management Science, 4 (1958), pp. 136–153.

[Kar62] , A general algorithm for the optimal distribution of effort, Management Science, 9 (1962), pp. 50–72.

[KaR79] M. H. Karwan and R. L. Rardin, Some relations between Lagrangean and surrogate duality in integer programming, Mathematical Programming, 17 (1979), pp. 320–334.

[KIM79] N. Katoh, T. Ibaraki, and H. Mine, A polynomial time algorithm for the resource allocation problem with a convex objective function, Journal of the Operational Research Society, 30 (1979), pp. 449–455.

[KeS77] J. L. Kennington and M. Shalaby, An effective subgradient procedure for minimal cost multicommodity flow problems, Management Science, 23 (1977), pp. 994–1004.

[Ket62] J. D. Kettelle, Jr., Least-cost allocations of reliability investment, Operations Research, 10 (1962), pp. 249–265.

[Kis65] L. Kish, Survey Sampling, John Wiley & Sons, New York, NY, 1965.

[Kiw96a] K. C. Kiwiel, The efficiency of subgradient projection methods for convex optimization, part I: General level methods, SIAM Journal on Control and Optimization, 34 (1996), pp. 660–676.

[Kiw96b] , The efficiency of subgradient projection methods for convex optimization, part II: Implementations and extensions, SIAM Journal on Control and Optimization, 34 (1996), pp. 677–6697.

[KLN00] K. C. Kiwiel, P. O. Lindberg, and A. Nöu, Bregman proximal relaxation of large-scale 0-1 problems, Computational Optimization and Applications, 15 (2000), pp. 33–44.

[Kle76] L. Kleinrock, Queueing Systems, vol. II, John Wiley & Sons, New York, NY, 1976.

[KNS74] D. Klingman, A. Napier, and J. Stuts, NETGEN: A program for generating large-scale capacitated assignment, transportation and minimum cost network flow problems, Management Science, 20 (1974), pp. 814–821.

[Kni24] F. H. Knight, Some fallacies in the interpretation of social cost, Quarterly Journal of Economics, 38 (1924), pp. 582–606. Reprinted in The Ethics of Competition, pp. 217–236, Harper, New York, NY, 1935; and in American Economic Association, Readings in Price Theory, pp. 160–179, Richard D. Irwin, Chicago, IL, 1952.

[Knu68] D. E. Knuth, The Art of Computer Programming, vol. 1: Fundamental algorithms of Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley, Reading, MA, 1968.

[Knu73] , The Art of Computer Programming, vol. 3: Sorting and Searching of Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley, Reading, MA, 1973.

[KoL98] M. S. Kodialam and H. Luss, Algorithms for separable nonlinear resource allocation problems, Operations Research, 46 (1998), pp. 272–284.

[Koo46] B. O. Koopman, Search and screening, OEG Report 56, Operations Evaluations Group, Office of the Chief of Naval Operations, U.S. Navy Department, Washington, D.C., 1946. Reprinted in [Koo80].

[Koo52] , New mathematical models in operations research, Journal of the Operations Research Society of America, 1 (1952), pp. 3–9.

[Koo53] , The optimum distribution of effort, Operations Research, 1 (1953), pp. 52–63.

[Koo54] , The distribution of searching effort, Journal of the Operations Research Society of America, 2 (1954).

[Koo56a] , The fallacies of operations research, Operations Research, 4 (1956), pp. 422–426, comments by Charles Hitch, 426–430.

[Koo56b] , The theory of search, I: Kinematic bases, Operations Research, 4 (1956), pp. 324–346.

[Koo56c] , The theory of search, II: Target detection, Operations Research, 4 (1956), pp. 503–531.

[Koo57] , The theory of search, III: The optimum distribution of effort, Operations Research, 5 (1957), pp. 613–626.

[Koo59] , Search, in Operations Research Center, M.I.T., Notes on Operations Research 1959, The Technology Press, Cambridge, MA, 1959, pp. 40–83.

[Koo79a] , An operational critique of detection laws, Operations Research, 27 (1979), pp. 115–133.

[Koo79b] , Search and its optimization, American Mathematical Monthly, 86 (1979), pp. 527–540.

[Koo80] , Search and Screening. General Principles With Historical Applications, Pergamon Press, Inc., Elmsford, NY, second ed., 1980.

[Koo99] , Search and Screening. General Principles With Historical Applications, Military Operations Research Society, Alexandria, VA, revised ed., 1999.

[Kot71] P. Kotler, Marketing Decision Making: A Model Building Approach, Holt, Rinehart and Winston, New York, NY, 1971.

[Kru37] J. Kruithof, Telefoonverkeersrekening, De Ingenieur, 52 (1937), pp. E15–E25. English translation, Calculation of telephone traffic, by U. K. Post Office Research Department Library, No. 2663, Dollis Hill, London, U.K.

[KuT51] H. W. Kuhn and A. W. Tucker, Nonlinear programming, in Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability, J. Neyman, ed., University of California Press, Berkeley, CA, 1951, pp. 481–492.

[LaS81] B. Lamond and N. F. Stewart, Bregman’s balancing method, Transportation Research, 15B (1981), pp. 239–248.

[LaP92] T. Larsson and M. Patriksson, Simplicial decomposition with disaggregated representation for the traffic assignment problem, Transportation Science, 26 (1992), pp. 4–17.

[LPS96] T. Larsson, M. Patriksson, and A.-B. Strömberg, Conditional subgradient optimization—theory and applications, European Journal of Operational Research, 88 (1996), pp. 382–403.

[Las70] L. S. Lasdon, Optimization Theory for Large Systems, Macmillan, New York, NY, 1970.

[Lau70] D. J. Laughhunn, Quadratic binary programming with application to capital-budgeting problems, Operations Research, 18 (1970), pp. 454–461.

[LNN95] C. Lemaréchal, A. S. Nemirovskii, and Yu. Nesterov, New variants of bundle methods, Mathematical Programming, 69 (1995), pp. 111–147.

[Lew81] C. D. Lewis, Scientific Inventory Control, John Wiley & Sons, New York, NY, 1981.

[LiP87] Y. Y. Lin and J.-S. Pang, Iterative methods for large convex quadratic programs: A survey, SIAM Journal on Control and Optimization, 25 (1987), pp. 383–411.

[Loa71] E. P. Loane, An algorithm to solve finite separable single-constrained optimization problems, Operations Research, 19 (1971), pp. 1477–1493.

[Lot06] P. A. Lotito, Issues in the implementation of the DSD algorithm for the traffic assignment problem, European Journal of Operational Research, (2006), to appear.

[Luk77] M. Lukka, On the optimal searching tracks for a moving target, SIAM Journal on Applied Mathematics, 32 (1977), pp. 126–132.

[Lus73] H. Luss, Mathematical models for marketing effort allocation, PhD thesis, Department of Statistics and Operations Research, University of Pennsylvania, Philadelphia, PA, 1973.

[Lus87] , An algorithm for separable nonlinear minimax problems, Operations Research Letters, 6 (1987), pp. 159–162.

[Lus91] , A nonlinear minimax allocation problem with multiple knapsack constraints, Operations Research Letters, 10 (1991), pp. 183–187.

[Lus92] , Minimax resource allocation problems: Optimization and parametric analysis, European Journal of Operational Research, 60 (1992), pp. 76–86.

[LuG75] H. Luss and S. K. Gupta, Allocation of effort resources among competing activities, Operations Research, 23 (1975), pp. 360–366.

[LuS86] H. Luss and D. R. Smith, Resource allocation among competing activities: A lexicographic minimax approach, Operations Research Letters, 5 (1986), pp. 227–331.

[Mac79] S. H. Macgill, Convergence and related properties for a modified biproportional problem, Environment and Planning, 11A (1979), pp. 499–506.

[MaD89] N. Maculan and G. G. de Paula, Jr, A linear-time median-finding algorithm for projecting a vector on the simplex of ℝ^{n}, Operations Research Letters, 8 (1989), pp. 219–222.

[MMP97] N. Maculan, M. Minoux, and G. Plateau, An O(n) algorithm for projecting a vector on the intersection of a hyperplane and ℝ_{+}^{n}, RAIRO Recherche Opérationnelle, 31 (1997), pp. 6–17.

[MSMJ03] N. Maculan, C. P. Santiago, E. M. Macambira, and M. H. C. Jardim, An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in ℝ^{n}, Journal of Optimization Theory and Applications, 117 (2003), pp. 553–574.

[MaK93] B. M. Maloney and C. M. Klein, Constrained multi-item inventory systems: An implicit approach, Computers & Operations Research, 20 (1993), pp. 639–649.

[Man82] M. Mangel, Probability of success in the search for a moving target, Operations Research, 30 (1982), pp. 216–222.

[Mar52] H. M. Markowitz, Portfolio selection, Journal of Finance, 7 (1952), pp. 77–91.

[Mar59] , Portfolio Selection: Efficient Diversification of Investments, vol. Monograph 16 of Cowles Foundation for Research in Economics at Yale University, John Wiley & Sons, New York, NY, 1959.

[MSM86] K. Mathur, H. M. Salkin, and B. B. Mohanty, A note on a general non-linear knapsack problem, Operations Research Letters, 5 (1986), pp. 79–81.

[MSM83] K. Mathur, H. M. Salkin, and S. Morito, A branch and search algorithm for some separable quadratic programming problems, Operations Research Letters, 2 (1983), pp. 155–160.

[McC7X] C. J. McCallum, Jr, An algorithm for certain quadratic integer programs, technical report, Bell Laboratories, Holmdel, NJ, undated.

[McC79] R. K. McCord, Minimization with one linear equality constraint and bounds on the variables, Technical Report 79-20, System Optimization Library, Department of Operations Research, Stanford University, Stanford, CA, 1979.

[MeT93] N. Megiddo and A. Tamir, Linear time algorithms for some separable quadratic programming problems, Operations Research Letters, 13 (1993), pp. 203–211.

[Meh98] J. Mehra, Josiah Willard Gibbs and the foundations of statistical mechanics, Foundations of Physics, 28 (1998), pp. 1785–1815.

[MeR00] A. Melman and G. Rabinowitz, An efficient method for a class of continuous nonlinear knapsack problems, SIAM Review, 42 (2000), pp. 440–448.

[Mey84] R. R. Meyer, Multipoint methods for separable nonlinear networks, Mathematical Programming Study, 22 (1984), pp. 185–205.

[Mic86] C. Michelot, A finite algorithm for finding the projection of a point onto the canonical simplex of ℝ^{n}, Journal of Optimization Theory and Applications, 50 (1986), pp. 195–200.

[Min78] M. Minoux, Un algorithme de sous-gradient por l’extrapolation des matrices de traffic pour une norme quadratique, internal note, CNET, Issy, France, 1978.

[Min84] , A polynomial algorithm for minimum quadratic cost flow problems, European Journal of Operational Research, 18 (1984), pp. 377–387.

[MoV91] J. J. Moré and S. A. Vavasis, On the solution of concave knapsack problems, Mathematical Programming, 49 (1991), pp. 397–411.

[MoS54] T. Motzkin and I. J. Schoenberg, The relaxation method for linear inequalities, Canadian Journal of Mathematics, 6 (1954), pp. 393–404.

[MuV91] J. M. Mulvey and H. Vladimirou, Solving multistage stochastic networks: An application of scenario aggregation, Networks, 21 (1991), pp. 619–643.

[Mun68] D. Munby, ed., Transport: Selected Readings, Penguin Books, Harmondsworth, Middlesex, England, 1968.

[Mur77] J. D. Murchland, The multiproportional problem, Manuscript JDM-263, Draft 1, Transport Studies Group, University College London, London, U.K., 1977.

[Nag87] A. Nagurney, An algorithm for the classical spatial price equilibrium problem, Operations Research Letters, 6 (1987), pp. 93–98.

[NEK90] A. Nagurney, A. Eyedeland, and D.-S. Kim, Computation of large scale constrained matrix problems: The splitting equilibration algorithm, in Proceedings of the 1990 ACM/IEEE conference on Supercomputing, New York, November 12–16, 1990, New York, NY, 1990, IEEE Computer Society, pp. 214–223.

[NKR90] A. Nagurney, D. S. Kim, and A. G. Robinson, Serial and parallel equilibration of large-scale constrained matrix problems with application to the social and economic sciences, The International Journal of Supercomputer Applications, 4 (1990), pp. 49–71.

[NaR92] A. Nagurney and A. G. Robinson, Algorithms for quadratic constrained matrix problems, Mathematical and Computer Modelling, 16 (1992), pp. 53–65.

[Ney34] J. Neyman, On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection, Journal of the Royal Statistical Society, 97 (1934), pp. 558–606.

[NiZ92] S. S. Nielsen and S. A. Zenios, Massively parallel algorithms for singly constrained convex programs, ORSA Journal on Computing, 4 (1992), pp. 166–181.

[NiZ93] , A massively parallel algorithm for nonlinear stochastic network problems, Operations Research, 41 (1993), pp. 319–337.

[OhK80] A. Ohuchi and I. Kaji, Algorithms for optimal allocation problems having quadratic objective function, Journal of the Operations Research Society of Japan, 23 (1980), pp. 64–80.

[OhK81] , An algorithm for the Hitchcock transportation problems with quadratic cost functions, Journal of the Operations Research Society of Japan, 24 (1981), pp. 170–182.

[OhK84] , Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs, Networks, 14 (1984), pp. 515–530.

[Oma67] F. H. Omar, The projection of input-output coefficients with application to the United Kingdom, PhD thesis, University of Nottingham, Nottingham, U.K., 1967.

[OOK86] T. Oohori, A. Ohuchi, and I. Kaji, Convergence proof of coordinatewise minimization algorithm for convex programming problem with upper and lower bounded constraints, Journal of the Operations Research Society of Japan, 29 (1986), pp. 320–337. In Japanese.

[ORC59] Operations Research Center, M.I.T., Notes on Operations Research 1959, The Technology Press, Cambridge, MA, 1959.

[Osb60] E. E. Osborne, On pre-conditioning of matrices, Journal of the Association of Computing Machinery, 7 (1960), pp. 338–345.

[Pan80] J.-S. Pang, A new and efficient algorithm for a class of portfolio selection problems, Operations Research, 28 (1980), pp. 754–767.

[Pan84] , On the convergence of dual ascent methods for large-scale linearly constrained optimization problems, technical report, School of Management, University of Texas at Dallas, Richardson, TX, 1984.

[PaK90] P. Pardalos and N. Kovoor, An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds, Mathematical Programming, 46 (1990), pp. 321–328.

[PYH91] P. Pardalos, Y. Ye, and C.-G. Han, Algorithms for the solution of quadratic knapsack problems, Linear Algebra and Its Applications, 152 (1991), pp. 69–91.

[Pat94] M. Patriksson, The Traffic Assignment Problem—Models and Methods, Topics in Transportation, VSP BV, Utrecht, The Netherlands, 1994.

[Pig20] A. C. Pigou, The Economics of Welfare, Macmillan & Co, London, U.K., 1920.

[Pig24] , The Economics of Welfare, Macmillan & Co, London, U.K., second ed., 1924.

[Pig29] , The Economics of Welfare, Macmillan & Co, London, U.K., third ed., 1929.

[Pig46] , The Economics of Welfare, Macmillan & Co, London, U.K., fourth ed., 1946.

[PoR69] E. Polak and G. Ribière, Note sur la convergence de méthodes de directions conjuguées, Revue Française Information Recherche Opérationnelle, 16 (1969), pp. 35–43.

[PIS02] V. V. Popovich, Y. A. Ivakin, and S. S. Shaida, Theory of search for moving objects, in Oceans 2002 IEEE/MTS Conference Proceedings, Biloxi, MS, October 29–31, 2002, vol. 3, 2002, pp. 1319– 1329.

[PFTV90] W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in FORTRAN, Cambridge University Press, Cambridge, NY, 1990.

[RJL92] A. G. Robinson, N. Jiang, and C. S. Lemke, On the continuous quadratic knapsack problem, Mathematical Programming, 55 (1992), pp. 99–108.

[Roc70] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

[Roc76a] , Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 1 (1976), pp. 97–116.

[Roc76b] , Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), pp. 877–898.

[Roc81] , Monotropic programming: Descent algorithms and duality, in Nonlinear Programming 4, O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, eds., Academic Press, New York, NY, 1981, pp. 327– 366.

[RoW88] R. T. Rockafellar and R. J.-B. Wets, A note about projections in the implementation of stochastic quasigradient methods, in Numerical Techniques for Stochastic Optimization, Yu. Ermol’ev and R. J.- B. Wets, eds., no. 10 in Springer Series in Computational Mathematics, Berlin, 1988, Springer-Verlag, pp. 385–392.

[Roh79] J. Rohn, Productivity of activities in the optimal allocation of one resource, working paper, Charles University, Prague, 1979.

[Roh82] , Productivity of activities in the optimal allocation of one resource, Aplikace Matematiky, (1982).

[Rou02] T. Roughgarden, The price of anarchy is independent of network topology, in Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, New York, NY, 2002, ACM Press, pp. 428–437.

[RoT02] T. Roughgarden and É. Tardos, How bad is selfish routing?, Journal of the ACM, 49 (2002), pp. 236–259.

[San71] L. Sanathanan, On an allocation problem with multistage constraints, Operations Research, 18 (1971), pp. 1747–1663.

[ScZ90] M. H. Schneider and S. A. Zenios, A comparative study of algorithms for matrix balancing, Operations Research, 38 (1990), pp. 439–455.

[Sha63] W. F. Sharpe, A simplified model for portfolio analysis, Management Science, 9 (1963), pp. 277–293.

[She85] Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice-Hall, Englewood Cliffs, NJ, 1985.

[ShM90] B. Shetty and R. Muthukrishnan, A parallel projection for the multicommodity network model, Journal of the Operational Research Society, 41 (1990), pp. 837–842.

[Sin64] R. Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices, Mathematical Statistics, 35 (1964), pp. 876–879.

[Sla50] M. Slater, Lagrange multipliers revisited: A contribution to nonlinear programming, Cowles Commission Discussion Paper, Mathematics, 403, Chicago, IL, 1950.

[Smi1776] A. Smith, An Inquiry into the Nature and Causes of the Wealth of Nations, W. Strahan & T. Cadell, London, U.K., 1776.

[SmL92] S. Smith and L. Lasdon, Solving large sparse nonlinear programs using GRG, ORSA Journal on Computing, 4 (1992), pp. 2–15.

[Spi02] H. Spiess, Biproportional matrix balancing with upper bounds, in Transportation and Network Analysis: Current Trends, M. Gendreau and P. Marcotte, eds., vol. 63 of Applied Optimization, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002, pp. 237–243.

[Sri63] K. S. Srikantan, A problem in optimum allocation, Operations Research, 18 (1963), pp. 265–273.

[Ste00] S. M. Stefanov, On the implementation of stochastic quasigradient methods to some facility location problems, Yugoslav Journal of Operations Research, 10 (2000), pp. 235–256.

[Ste01a] , Convex separable minimization subject to bounded variables, Computational Optimization and Applications, 18 (2001), pp. 27–48.

[Ste01b] , Separable Programming: Theory and Methods, vol. 53 of Applied Optimization, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001.

[Ste02] , Convex separable minimization problems with a linear constraint and bounds on the variables, in Applications of Mathematics in Engineering and Economics, Proceedings of the 27th Summer School held in Sozopol, 2001, D. Ivanchev and M. D. Todorov, eds., Sofia, 2002, Heron Press, pp. 392–402.

[Ste04a] , Convex quadratic minimization subject to a linear constraint and box constraints, Applied Mathematics Research eXpress, 2004 (2004), pp. 17–42.

[Ste04b] , Polynomial algorithms for projecting a point onto a region defined by a linear constraint and box constraints, Journal of Applied Mathematics, 5 (2004), pp. 409–431.

[Sto73] B. K. Stone, A linear programming formulation of the general portfolio selection problem, Journal of Financial and Quantitative Analysis, 8 (1973), pp. 621–636.

[Sto75] L. D. Stone, Theory of Optimal Search, Academic Press, New York, NY, 1975.

[Tak63] I. Takahashi, Variable separation principle for mathematical programming, Journal of the Operations Research Society of Japan, 6 (1963/64), pp. 82–105.

[Tak70] , A method for solving network transportation problems with quadratic cost functions, Bulletin of the Institute for Research in Productivity, Waseda University, 1 (1970), pp. 25–31.

[Tan88] C. S. Tang, A max-min allocation problem: Its solutions and applications, Operations Research, 36 (1988), pp. 359–367.

[Thv60] H. Theil and C. van de Panne, Quadratic programming as an extension of conventional quadratic maximization, Management Science, 7 (1960), pp. 1–20.

[Tom67] J. A. Tomlin, Mathematical programming models for traffic network problems, PhD thesis, Department of Mathematics, University of Adelaide, Adelaide, Australia, 1967.

[Tra64] J. F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, NJ, 1964.

[Tse90] P. Tseng, Dual ascent methods for problems with strictly convex costs and linear constraints: A unified approach, SIAM Journal on Control and Optimization, 28 (1990), pp. 214–242.

[Tse91] , Descent methods for convex essentially smooth minimization, Journal of Optimization Theory and Applications, 71 (1991), pp. 425–463.

[TsB87] P. Tseng and D. P. Bertsekas, Relaxation methods for problems with strictly convex separable costs and linear constraints, Mathematical Programming, 38 (1987), pp. 303–321.

[TsB90] , Relaxation methods for monotropic programs, Mathematical Programming, 46 (1990), pp. 127– 151.

[Ven89] J. A. Ventura, Algorithms for quadratic transportation networks, in Proceedings of the 28th IEEE Conference on Decision and Control, Tampa, FL, 1989, pp. 1131–1135.

[Ven91] , Computational development of a Lagrangian dual approach for quadratic networks, Networks, 21 (1991), pp. 469–485.

[VeH88] J. A. Ventura and D. W. Hearn, Computational development of a Lagrangian dual approach for quadratic networks, Working paper 8710902, Department of Industrial Engineering, University of Missouri at Columbia, Columbia, MU, 1988.

[VeK88] J. A. Ventura and C. M. Klein, A note on multi-item inventory systems with limited capacity, Operations Research Letters, 7 (1988), pp. 71–75.

[Vid70] P. V. V. Vidal, Operations research in production planning, Ph.D. thesis, IMSOR, The Technical University of Denmark, 1970.

[Vid84] P. V. V. Vidal, A graphical method to solve a family of allocation problems, European Journal of Operational Research, 17 (1984), pp. 31–34.

[Vid86] P. V. V. Vidal, Solving a family of simple allocation problems, Investigaci’on Operacional. Revista, 7 (1986), pp. 33–47.

[Vid87] P. V. V. Vidal, A simple method to solve some simple allocation problems, IIE Transactions, 19 (1987), pp. 234–237.

[vNe28] J. von Neumann, Zur Theorie der Gesellschaftsspiele, Mathematische Annalen, 100 (1928), pp. 295– 320.

[vTh1826] J. H. von Thünen, Der isolierte Staat in Beziehung auf Landwirtschaft und Nationalökonomie, Hamburg, 1826. Translated as Von Thünen’s Isolated State by C. M. Wartenberg, Pergamon Press, London, U.K., 1966.

[WaW58] H. M. Wagner and T. M. Whitin, Dynamic version of the economic lot-size model, Management Science, 5 (1958), pp. 89–96.

[Wal54] A. A. Walters, Track costs and motor taxation, Journal of Industrial Economics, (1954).

[Wal61] , The theory and measurement of private and social cost of highway congestion, Econometrica, 29 (1961), pp. 676–699.

[War52] J. G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institute of Civil Engineers, Part II, (1952), pp. 325–378.

[Was81] A. R. Washburn, Note on constrained maximization of a sum, Operations Research, 29 (1981), pp. 411–414.

[WeC72] H. S. Weigel and J. E. Cremeans, The multicommodity network flow model revised to include vehicle per time period and node constraints, Naval Research Logistics Quarterly, 19 (1972), pp. 77– 89.

[WiG69] C. Wilkinson and S. K. Gupta, Allocating promotional effort to competing activities: A dynamic programming approach, in IFORS Conference, Venice, Italy, 1969, pp. 419–432.

[Wil34] R. H. Wilson, A scientific routine for stock control, Harvard Business Review, 13 (1934), pp. 116–128.

[Wol74] P. Wolfe, Algorithm for a least-distance programming problem, Mathematical Programming Study, 1 (1974), pp. 190–205.

[Wol76] , Finding the nearest point in a polytope, Mathematical Programming, 11 (1976), pp. 128–149.

[WuV95] C.-H. Wu and J. A. Ventura, Computational development of a dual block-coordinate algorithm for constrained matrix problems, Mathematical Modeling and Scientific Computing, (1995).

[YaS87] D. Yao and J. Shanthikumar, The optimal input rates to a system of manufacturing cells, INFOR, 25 (1987), pp. 57–65.

[Zad69] N. Zadeh, A note on the cyclic coordinate ascent method, Management Science, 16 (1969/1970), pp. 642–644.

[Zah63] S. Zahl, An allocation problem with applications to operations research and statistics, Operations Research, (1963).

[Zan69] W. I. Zangwill, Nonlinear Programming: A Unified Approach, Prentice-Hall, Englewood Cliffs, NJ, 1969.

[ZeC91] S. A. Zenios and Y. Censor, Massively parallel row-action algorithms for some nonlinear transportation problems, SIAM Journal on Optimization, 1 (1991), pp. 373–400.

[ZeM85] S. A. Zenios and J. M. Mulvey, Relaxation techniques for strictly convex network problems, Annals of Operations Research, 5 (1985/86), pp. 517–538.

[ZeM88] , A distributed algorithm for convex network optimization problems, Parallel Computing, 6 (1988), pp. 45–56.

[Zie82] H. Ziegler, Solving certain singly constrained convex optimization problems in production planning, Operations Research Letters, 1 (1982), pp. 246–252.

[Zip80a] P. H. Zipkin, Error bounds for aggregated convex transportation problems, working paper, Graduate School of Business, Columbia University, New York, NY, 1980.

[Zip80b] , Simple ranking methods for allocation of one resource, Managemant Science, 26 (1980), pp. 34– 43.