A survey on the continuous nonlinear resource allocation problem
---
paper_title: Issues in the implementation of the DSD algorithm for the traffic assignment problem

paper_content:

Abstract In this paper we consider the practical implementation of the disaggregated simplicial decomposition (DSD) algorithm for the traffic assignment problem. It is a column generation method that at each step has to solve a huge number of quadratic knapsack problems (QKP). We propose a Newton-like method to solve the QKP when the quadratic functional is convex but not necessarily strictly. Our O( n ) algorithm does not improve the complexity of the current methods but extends them to a more general case and is better suited for reoptimization and so a good option for the DSD algorithm. It also allows the solution of many QKP’s simultaneously in a vectorial or parallel way.
---
paper_title: A Massively Parallel Algorithm for Nonlinear Stochastic Network Problems

paper_content:

We develop an algorithm for solving nonlinear, two-stage stochastic problems with network recourse. The algorithm is based on the framework of row-action methods. The problem is formulated by replicating the first-stage variables and then adding nonanticipativity side constraints. A series of independent deterministic network problems are solved at each step of the algorithm, followed by an iterative step over the nonanticipativity constraints. The solution point of the iterates over the nonanticipativity constraints is obtained analytically. The row-action nature of the algorithm makes it suitable for parallel implementations. A data representation of the problem is developed that permits the massively parallel solution of all the scenario subproblems concurrently. The algorithm is implemented on a Connection Machine CM-2 with up to 32K processing elements and achieves computing rates of 276 MFLOPS. Very large problems-8,192 scenarios with a deterministic equivalent nonlinear program with 868,367 constraints and 2,474,017 variables-are solved within a few minutes. We report extensive numerical results regarding the effects of stochasticity on the efficiency of the algorithm.
---
paper_title: The efficiency of subgradient projection methods for convex optimization, part I: general level methods

paper_content:

We study subgradient methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We present several variants and show that they enjoy almost optimal efficiency estimates. In another paper we discuss possible implementations of such methods. In particular, their projection subproblems may be solved inexactly via relaxation methods, thus opening the way for parallel implementations. They can also exploit accelerations of relaxation methods based on simultaneous projections, surrogate constraints, and conjugate and projected (conditional) subgradient techniques.
---
paper_title: Projection methods for variational inequalities with application to the traffic assignment problem

paper_content:

It is well known [2, 3, 16] that if \(\bar T:R^n \to R^n\) is a Lipschitz continuous, strongly monotone operator and X is a closed convex set, then a solution x *∈X of the variational inequality \((x - x^ * )'\bar T(x^ * ) \geqslant 0\), ∨x∈X can be found iteratively by means of the projection method \(x_{k - 1} = Px[x_k - \alpha \bar T(x_k )]\), x 0∈X, provided the stepsize α is sufficiently small. We show that the same is true if \(\bar T\) is of the form \(\bar T = A'TA\), where A:R n→R m is a linear mapping, provided T:R m→R m is Lipschitz continuous and strongly monotone, and the set X is polyhedral. This fact is used to construct an effective algorithm for finding a network flow which satisfies given demand constraints and is positive only on paths of minimum marginal delay or travel time.
---
paper_title: Solving multistage stochastic networks: An application of scenario aggregation

paper_content:

The scenario aggregation algorithm is specialized for stochastic networks. The algorithm determines a solution that does not depend on hindsight and accounts for the uncertain environment depicted by a number of appropriately weighted scenarios. The solution procedure decomposes the stochastic program to its constituent scenario subproblems, thus preserving the network structure. Computational results are reported demonstrating the algorithm's convergence behavior. Acceleration schemes are discussed along with termination criteria. The algorithm's potential for execution on parallel multiprocessors is discussed.
---
paper_title: Bregman Proximal Relaxation of Large-Scale 0–1 Problems

paper_content:

We apply a recent extension of the Bregman proximal method for convex programming to LP relaxations of 0–1 problems. We allow inexact subproblem solutions obtained via dual ascent, increasing their accuracy successively to retain global convergence. Our framework is applied to relaxations of large-scale set covering problems that arise in airline crew scheduling. Approximate relaxed solutions are used to construct primal feasible solutions via a randomized heuristic. Encouraging preliminary experience is reported.
---
paper_title: On projection algorithms for solving convex feasibility problems

paper_content:

Due to their extraordinary utility and broad applicability in many areas of classical mathematics and modern physical sciences (most notably, computerized tomography), algorithms for solving convex feasibility problems continue to receive great attention. To unify, generalize, and review some of these algorithms, a very broad and flexible framework is investigated. Several crucial new concepts which allow a systematic discussion of questions on behaviour in general Hilbert spaces and on the quality of convergence are brought out. Numerous examples are given.
---
paper_title: Supply and Demand Equilibration Algorithms for a Class of Market Equilibrium Problems

paper_content:

In this paper, we describe a family of progressive equilibration algorithms which can be used to solve a variety of market equilibrium problems such as the general spatial price equilibrium problem, the single price spatial price equilibrium problem, etc. They are relaxation-type algorithms which attempt to equilibrate the whole system by equilibrating successively each supply market (producer), or each demand market (consumer). One noteworthy feature of these algorithms is that, due to the special structure of the problem, the restricted equilibrium for each supply market (or demand market) can be obtained explicitly in closed form; another feature is that they are intuitive and straightforward to implement. Moreover, the computational results demonstrate that the algorithms are efficient and suitable for large-scale problems.
---
paper_title: Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem

paper_content:

The class of simplicial decomposition (SD) schemes has shown to provide efficient tools for nonlinear network flows. When applied to the traffic assignment problem, shortest route subproblems are solved in order to generate extreme points of the polyhedron of feasible flows, and, alternately, master problems are solved over the convex hull of the generated extreme points. We review the development of simplicial decomposition and the closely related column generation methods for the traffic assignment problem; we then present a modified, disaggregated, representation of feasible solutions in SD algorithms for convex problems over Cartesian product sets, with application to the symmetric traffic assignment problem. The new algorithm, which is referred to as disaggregate simplicial decomposition (DSD), is given along with a specialized solution method for the disaggregate master problem. Numerical results for several well known test problems and a new one are presented. These experimentations indicate that only few shortest route searches are needed; this property is important for large-scale applications. The modification proposed maintains the advantages of SD, and the results show that the performance of the new algorithm is at least comparable to that of state-of-the-art codes for traffic assignment. Moreover, the reoptimization capabilities of the new scheme are significantly better; this is a main motive for considering it. The reoptimization facilities, especially with respect to changes in origin-destination flows and network topology, make the new approach highly profitable for more complex models, where traffic assignment problems arise as subproblems.
---
paper_title: New variants of bundle methods

paper_content:

In this paper we describe a number of new variants of bundle methods for nonsmooth unconstrained and constrained convex optimization, convex—concave games and variational inequalities. We outline the ideas underlying these methods and present rate-of-convergence estimates.
---
paper_title: Quasi-Newton updates with bounds

paper_content:

We develop a quasi-Newton method which preserves known bounds on the Jacobian matrix. We show that this update can be computed with the same amount of work as competitive methods. In particular, we prove that the number of operations required to obtain this update is proportional to the number of nonzeros in the sparsity pattern of the Jacobian matrix. The method is also shown to share the local convergence properties of Broyden’s and Schubert’s method.
---
paper_title: Solving certain singly constrained convex optimization problems in production planning

paper_content:

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.
---
paper_title: ON THE DESIGN OF HIERARCHICAL PRODUCTION PLANNING SYSTEMS

paper_content:

Abstract : To provide effective managerial support to the decisions related to the production planning and scheduling processes, it is useful to partition this set of decisions in a hierarchical framework. In the resulting system higher level decisions impose constraints to lower level actions, and lower level decisions provide the necessary feedback to reevaluate higher level actions. The purpose of this paper is to suggest optimum procedures to deal with the resulting subproblems, and to analyze the interaction mechanisms among the different hierarchical levels. Computational results are given. (Author)
---
paper_title: A note on multi-item inventory systems with limited capacity

paper_content:

Functional relationships between the Lagrange multiplier and system parameters for multi-item inventory systems with one restriction are identified and used to establish tight bounds on the optimal multiplier value. A recursive process which rapidly converges to the optimal multiplier is also discussed. Finally, a comparative analysis of the new bounds in relation to existing bounds is presented.
---
paper_title: Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables

paper_content:

The allocation of a specific amount of a given resource among competitive alternatives can often be modelled as a knapsack problem. This model formulation is extremely efficient because it allows convex cost representation with bounded variables to be solved without great computational efforts. Practical applications of this problem abound in the fields of operations management, finance, manpower planning, marketing, etc. In particular, knapsack problems emerge in hierarchical planning systems when a first level of decisions need to be further allocated among specific activities which have been previously treated in an aggregate way. In this paper we provide a recursive procedure to solve such problems. The method differs from classical optimization algorithms of convex programming in that it determines at each iteration the optimal value of at least one variable. Applications and computational results are presented.
---
paper_title: Dynamic Version of the Economic Lot Size Model

paper_content:

(This article originally appeared in Management Science, October 1958, Volume 5, Number 1, pp. 89-96, published by The Institute of Management Sciences.) ::: ::: A forward algorithm for a solution to the following dynamic version of the economic lot size model is given: allowing the possibility of demands for a single item, inventory holding charges, and setup costs to vary over N periods, we desire a minimum total cost inventory management scheme which satisfies known demand in every period. Disjoint planning horizons are shown to be possible which eliminate the necessity of having data for the full N periods.
---
paper_title: On the Two Different Aspects of the Representative Method: the Method of Stratified Sampling and the Method of Purposive Selection

paper_content:

Owing to the work of the International Statistical Institute,* and perhaps still more to personal achievements of Professor A.L. Bowley, the theory and the possibility of practical applications of the representative method has attracted the attention of many statisticians in different countries. Very probably this popularity of the representative method is also partly due to the general crisis, to the scarcity of money and to the necessity of carrying out statistical investigations connected with social life in a somewhat hasty way. The results are wanted in some few months, sometimes in a few weeks after the beginning of the work, and there is neither time nor money for an exhaustive research.
---
paper_title: Josiah Willard Gibbs and the Foundations of Statistical Mechanics

paper_content:

In this study, I discuss the development of the ideas of Josiah Willard Gibbs' Elementary Principles in Statistical Mechanics and the fundamental role they played in forming the modern concepts in that field. Gibbs' book on statistical mechanics became an instant classic and has remained so for almost a century.
---
paper_title: Track Costs and Motor Taxation

paper_content:

I. IN the field of transport economics, few problems have aroused more heated and prolonged controversy than that of track costs. Railway executives in many developed countries of the world have called upon the Public's sense of fair play to witness the railway's disadvantage in having to pay out enormous sums annually in the form of track maintenance and interest. How can the railways engage in fair competition with road haulage and 'bus firms who do not have to pay for the highways? It is argued that the conditions under which the two great transport industries compete should be equalized; then the rules of the competitive game would be fair to all players and the public would gain a more efficient transport system. I The main purpose of this article is to examine the validity of arguments showing that road users should pay for the services of the highways. It is concluded that motor taxation is not, and should not, be related to the cost of the track. Criteria other than the cost of the track should determine aggregate motor taxation. Finally it is sugt gested that motor taxation should be levied so that the marginal private cost of vehicle operation is brought nearer to the marginal social costs and the degree of congestion on our roads is reduced. 2. Before we can get some idea of the quantities involved, some definition of the term 'track costs' must be given. The arguments about the unfair burden of the railways stem from the fact that road users are not charged specifically for certain kinds of input while the railways have to pay for similar inputs. Without straining terminology, it is impossible to include all of these outlays under the head of track costs; for example, the accounts of road users do not show debits for police traffic control, but the railways must pay for their police. But the major bone of contention is the 'legacy of the past' in the shape of highways. Consequently we shall arbitrarily define track costs to include only those outlays of the railways connected with the maintenance and interest on the permanent way. The interest element is quite an arbitrary figure. Accountants have their own procedures for determining that proportion of the compensation payments which is called the capital cost of the track taken over; the figures have little economic significance. Sir Reginald Wilson (Comptroller of the B.T.C.) estimates the (accounting) interest payments on
---
paper_title: How bad is selfish routing?

paper_content:

We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times---the total latency---is minimized.In many settings, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance.In this article, we quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and nondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulated selfish network users may be arbitrarily larger than the minimum possible total latency; however, we prove that it is no more than the total latency incurred by optimally routing twice as much traffic.
---
paper_title: Selfish routing in capacitated networks

paper_content:

According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A Nash equilibrium does not optimize any global criterion per se, and so there is no apparent reason why it should be close to a solution of minimal total travel time, i.e., the system optimum. In this paper, we offer positive results on the efficiency of Nash equilibria in traffic networks. In contrast to prior work, we present results for networks with capacities and for latency functions that are nonconvex, nondifferentiable, and even discontinuous.The inclusion of upper bounds on arc flows has early been recognized as an important means to provide a more accurate description of traffic flows. In this more general model, multiple Nash equilibria may exist and an arbitrary equilibrium does not need to be nearly efficient. Nonetheless, our main result shows that the best equilibrium is as efficient as in the model without capacities. Moreover, this holds true for broader classes of travel cost functions than considered hitherto.
---
paper_title: On the Optimal Searching Tracks for a Moving Target

paper_content:

Necessary conditions for the optimal searching tracks for a moving target are presented. The motion of the target is determined by a parameter vector having a known probability distribution function.
---
paper_title: An Operational Critique of Detection Laws

paper_content:

This paper applies the test of operational meaningfulness to the many detection laws that have been formulated and used in the mathematical optimization of search, and given as generalizations of those first developed in the United States Navy during and immediately following World War II. The word "operational" is used both in the sense of practical O.R. and in that of P. W. Bridgman's well-known requirement: that in applying mathematics to the material world, the physical preconditions implied in the quantities used, the operations for measuring them, and their laws of consistency must be set forth explicitly. It is submitted that this criterion will orient O.R. work toward useful developments in the search theory and may serve to identify as such those theories that are of chief interest as developments in pure mathematics. Finally, we note that the requirement that every numerical assumption of probability distributions in a study of the outside world must be based on objective evidence is perfectly consistent with the "subjective" conception of probability, viz., that its meaning is apprehended intuitively-the former measures what the latter defines.
---
paper_title: An Allocation Problem with Applications to Operations Research and Statistics

paper_content:

A considerable number of problems in operations research and statistics have the following form maximize ∫ f[x, yx] dx subject to ∫ g[x, yx] dx = constant with respect to bounded yx. We give a necessary and sufficient condition for a maximizing function under fairly weak restrictions and prove its existence. The solution is applied to a general version of B. O. Koopman's search problem, and to the Neyman, Pearson lemma of statistics. We also show that in the discrete version of this problem, where x is replaced by an index and sums replace integrals, our condition is sufficient but not necessary and give, as illustration of the sufficiency, a solution to an assignment problem.
---
paper_title: Theory of search for moving objects

paper_content:

The objectives of the paper are a development of a system of rules called "theory of search for moving objects", and a development of a new class of search problems for moving objects within the frames of this system, rather than a selection, classification or enumeration of all published articles, manuals, monographs, tasks statements and other in the theory of search area. The following issues are considered in the paper: (1) analysis and classification of search problems; (2) an axiomatic basis of the research approach; (3) axioms of the theory of search; (4) common theorem of additivity; (5) theorems of multiplicity; and (6) computer prototype for the theory of search. The case of a complex observation system integrated within one carrier is a core of the proposed approach. A case of two different observation systems is considered, when an observation zone for the second system (contact detector like a laser) is approximated as a line or a rectangle. It is possible to determine a probability area of target localization when one or both observation systems detected the target (theorem of multiplicity). A computer prototype of the theory of search for moving objects has been designed based on the object-oriented approach. It appeared to be a useful tool for any theoretical research and a flexible media for the further development of the theory of search for moving objects. It is also shown that it can be implemented for an adequate computer interpretation of search problems.
---
paper_title: A Game Theory Model of Convoy Routing

paper_content:

This paper considers a nonlinear two-person zero-sum game in which one of the players plays over the direct product of two spaces. In fact he allocates ships and escort vessels, separately, to various routes, and his antagonist allocates submarines to the various routes. Its interest lies first in the methodology connected with the curious nature of the one player's space, and second in its conclusions and some economic considerations related to them, for example the “virtual cost” of a route. The paper is a much condensed version of a paper done in 1953 for the Operations Evaluation Group of the Navy Department. The lengthy discussions and numerical computations in that paper have been deleted here, and the loss function taken slightly less general than there. The solution techniques are essentially the same.
---
paper_title: Validation of subgradient optimization

paper_content:

The "relaxation" procedure introduced by Held and Karp for approximately solving a large linear programming problem related to the traveling-salesman problem is refined and studied experimentally on several classes of specially structured large-scale linear programming problems, and results on the use of the procedure for obtaining exact solutions are given. It is concluded that the method shows promise for large-scale linear programming
---
paper_title: A benders decomposition based heuristic for the hierarchical production planning problem

paper_content:

Abstract In this paper a heuristic procedure for determining good feasible solutions to a multi-item dynamic production planning problem is described and evaluated. The problem, which is modelled as a mixed-integer linear program, has a hierarchical structure where production items are aggregated into families, and families into product types. A decomposition of the original problem creates a trivial subproblem providing feasible solutions on the type level, and a master problem which separates into one uncapacitated lot-sizing problem for each family. The latter problems can be solved by dynamic programming with very little computational effort. Besides the nice structure of both the sub- and master problem, the dual information from the subproblem can be given interesting economic interpretations. As distinguished from Hax and Meal's hierarchical framework for production planning and also they hybrid approach suggested by Graves in 1982, there exists a direct information flow from the family level problem to the type level problem in form of a production plan. The heuristic is essentially an application of Benders decomposition, the only difference being that the Benders cuts are relaxed using Lagrangean multipliers. A subgradient procedure is used to update the Lagrangean multipliers. One iteration of this heuristic requires less computational effort compared to Grave's algorithm. This is due to the fact that the Benders subproblem can be solved by inspection, while Graves' algorithm involves solving an LP-problem on the type level. For thirtysix medium-size test problems the average deviation from optimum is 2.34%, and the deviation ranges between 0.00% and 5.95%.
---
paper_title: An Improved Implicit Enumeration Approach for Integer Programming

paper_content:

This paper synthesizes the Balasian implicit enumeration approach to integer linear programming with the approach typified by Land and Doig and by Roy, Bertier, and Nghiem. The synthesis results from the use of an imbedded linear program to compute surrogate constraints that are as "strong" as possible in a sense slightly different from that originally used by Glover. A simple implicit enumeration algorithm fitted with optional imbedded linear programming machinery was implemented and tested extensively on an IBM 7044. Use of the imbedded linear program greatly reduced solution times in virtually every case, and seemed to render the tested algorithm superior to the five other implicit enumeration algorithms for which comparable published experience was available. The crucial issue of the sensitivity of solution time to the number of integer variables was given special attention. Sequences were run of set-covering, optimal-routing, and knapsack problems with multiple constraints of varying sizes up to 90 variables. The results suggest that use of the imbedded linear program in the prescribed way may mitigate solution-time dependence on the number of variables from an exponential to a low-order polynomial increase. The dependence appeared to be approximately linear for the first two problem classes, with 90-variable problems typically being solved in about 15 seconds; and approximately cubic for the third class, with 80-variable problems typically solved in less than 2 minutes. In the 35-variable range for all three classes, use of the imbedded linear program reduced solution times by a factor of about 100.
---
paper_title: Dual ascent methods for problems with strictly convex costs and linear constraints: a unified approach

paper_content:

Consider problems of the form \[({\text{P}})\qquad min \{ . {f(x)} |Ex \geqq b\} ,\] where f is a strictly convex (possibly nondifferentiable) function and E and b are, respectively, a matrix and a vector. A popular method for solving special cases of (P) (e.g., network flow, entropy maximization, quadratic program) is to dualize the constraints $Ex \geqq b$ to obtain a differentiable maximization problem and then apply an iterative ascent method to solve it. This method is simple and can exploit sparsity, thus making it ideal for large-scale optimization and, in certain cases, for parallel computation. Despite its simplicity, however, convergence of this method has been shown only under certain very restrictive conditions and only for certain special cases of (P). In this paper a block coordinate ascent method is presented for solving (P) that contains as special cases both dual coordinate ascent methods and dual gradient methods. It is shown, under certain mild assumptions on f and (P), that this method...
---
paper_title: Computational development of a lagrangian dual approach for quadratic networks

paper_content:

A Lagrangian dual approach for large-scale quadratic programs due to Lin and Pang is adapted to the quadratic cost network flow problem. The unconstrained dual problem is solved iteratively by combining conjugate gradient directions with finite line-search methods. By exploiting the graph structure, matrix and vector operations are streamlined so that the technique can be used for large problems. A computational study of randomly generated networks with up to 500 nodes and 20,000 arcs gives a comparison between combinations of different conjugate direction formulas with three line-search techniques. The results demonstrate the clear superiority of the Polak-Ribiere direction formula combined with a variant of a line-search technique originally developed by Bitran and Hax for convex knapsack problems.
---
paper_title: Application of the dual active set algorithm to quadratic network optimization

paper_content:

A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature.
---
paper_title: Simple Ranking Methods for Allocation of One Resource

paper_content:

This paper considers optimization problems with a nonlinear-additive objective function and a single linear constraint. Such models have numerous direct applications and serve as subproblems in procedures for more complex problems. Some important portfolio selection problems can be expressed in this form, and the problem also arises in economic theory. Several authors have noticed independently that special cases and variants of the problem can be solved exactly by surprisingly simple, finite algorithms. The major purpose of this paper is to present these results in a unified framework, which then permits substantial generalizations and extensions. The results lend themselves to an appealing managerial interpretation, similar to the rate-of-return cutoff rules of capital budgeting.
---
paper_title: Solving certain singly constrained convex optimization problems in production planning

paper_content:

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.
---
paper_title: Minimax resource allocation problems: Optimization and parametric analysis

paper_content:

Abstract We consider a linear minimax resource allocation problem with single-variable terms in the objective function and multiple knapsack-type resource constraints. All variables are continuous and nonnegative. Efficient algorithms for such large-scale problems have been developed by Luss and Smith and by Tang. This paper describes an enhanced algorithm that provides a more efficient search for the optimal solution. Further, we develop post-optimization schemes and parametric analysis that are employed once an optimal solution for the original minimax problem is obtained. Post-optimization provides a perturbed optimal solution under a specified change in the data, whereas parametric analysis provides a continuum of optimal solutions when some data elements are changed over a given interval.
---
paper_title: An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds

paper_content:

This paper gives an O(n) algorithm for a singly constrained convex quadratic program using binary search to solve the Kuhn-Tucker system. Computational results indicate that a randomized version of this algorithm runs in expected linear time and is suitable for practical applications. For the nonconvex case ane-approximate algorithm is proposed which is based on convex and piecewise linear approximations of the objective function.
---
paper_title: The Optimal Buffer Allocation Problem

paper_content:

Pathwise probabilistic arguments are used to justify a simple rule of thumb by which buffer allocation can be carried out. The model for the underlying network is the skeleton of an open Jackson network. The problem of how to distribute in the best possible way a fixed number N of available buffer spaces among the nodes of the network is considered. The goal is to optimize some performance criterion associated with the time to buffer overflow, such as its mean or the probability that it exceeds some value. It is argued that for any such performance criterion the assignment should be done roughly in inverse proportion to the logarithms of the effective service rates at the nodes. Effective service means the ratio of the service rate to the stationary arrival rate at the node in the network with inifinite buffers. >
---
paper_title: A note on multi-item inventory systems with limited capacity

paper_content:

Functional relationships between the Lagrange multiplier and system parameters for multi-item inventory systems with one restriction are identified and used to establish tight bounds on the optimal multiplier value. A recursive process which rapidly converges to the optimal multiplier is also discussed. Finally, a comparative analysis of the new bounds in relation to existing bounds is presented.
---
paper_title: Massively Parallel Algorithms for Singly Constrained Convex Programs

paper_content:

We develop four iterative algorithms for the solution of separable, convex nonlinear optimization problems with a single linear constraint and bounded variables. The design of the algorithms makes them suitable for implementation on massively parallel computers of the SIMD (i.e., Single Instruction, Multiple Data) class. The algorithms are specialized for the solution of network problems whereby the linear constraint reflects conservation of flow. Details of implementations on a Connection Machine CM-2 are reported. The numerical results indicate that all algorithms are very effective, and can solve very large problems. Three of the algorithms are also very efficient when implemented on the massively parallel system. Interestingly, the most effective algorithm (in number of steps required to solve the test problems) is the least efficient (in solution time) when implemented in parallel. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: Component procurement and allocation for products assembled to forecast: risk-pooling effects

paper_content:

This paper considers procurement and allocation policies in a manufacturing environment where common components are assembled into various products that have stochastic demands. The components are allocated to the assembly of a product at a time when product demand is still uncertain (assemble to forecast, ATF). The special case of one component shared by N different products is analyzed, and insights into the general problem are obtained for the situation in which the common component can be reallocated to different products as product demands change. An allocation policy is developed for general distributions and prices in an ATF environment. The policy first addresses anomalies in the state of the system and then, for a feasible state, minimizes the expected excess finished-goods inventory. A procurement level that is nearly optimal is obtained from a Monte Carlo simulation in which the probability of satisfying all of the random product demands simultaneously is considered relative to this allocation policy. Numerical studies indicate that the total component and finished-goods inventory is significantly reduced by an allocation policy that incorporates risk pooling while still fulfilling sevice-level requirements.
---
paper_title: Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables

paper_content:

The allocation of a specific amount of a given resource among competitive alternatives can often be modelled as a knapsack problem. This model formulation is extremely efficient because it allows convex cost representation with bounded variables to be solved without great computational efforts. Practical applications of this problem abound in the fields of operations management, finance, manpower planning, marketing, etc. In particular, knapsack problems emerge in hierarchical planning systems when a first level of decisions need to be further allocated among specific activities which have been previously treated in an aggregate way. In this paper we provide a recursive procedure to solve such problems. The method differs from classical optimization algorithms of convex programming in that it determines at each iteration the optimal value of at least one variable. Applications and computational results are presented.
---
paper_title: Elements of large-scale mathematical programming

paper_content:

Abstract : A unifying framework of concepts central to the optimization of large structured systems is developed and used in the organization of the literature. The basic concepts are divided in two groups, (1) problem manipulations, in which a given problem is restated in an alternative form more amenable to solution, and (2) solution strategies which reduce an optimization problem to a related sequence of simpler problems that can be solved by specialized methods.
---
paper_title: The Optimal Input Rates To A System Of Manufacturing Cells

paper_content:

AbstractA manufacturing system capable of processing multiple part types generates input, at a given rate, R, to a set of m cells. Each cell processes a certain type of parts and has its own production and buffer capacities. We study the problem of aEocating the production rate, R, among the m cells, such that the total throughput (over all m cells) will be maximised, while the blocking probabilities willl be kept below a given set of limits. An optimisation problem is formulated, which maximises a concave function over a convex set. An algorithm is developed, which fuUy exploits the problem structure and efficiently generates the optimal solution. Several extensions of the model are also discussed.
---
paper_title: A Max-Min Allocation Problem: Its Solutions and Applications

paper_content:

This paper describes a max-min allocation problem that has M constraints and N nonnegative integer variables. By exploring the structure of the optimal solution to this max-min allocation problem, we develop a nonsimplex-based algorithm that finds an optimal solution within OMN2 operations. In addition, we show that a space allocation problem for a flexible component insertion machine can be formulated as a special case of this max-min allocation problem with one constraint. Furthermore, we present some manufacturing and production problems that can he formulated as max-min allocation problems, and hence, can be solved efficiently.
---
paper_title: Technical Note - Extension of the Luss-Gupta Resource Allocation Algorithm by Means of First Order Approximation Techniques

paper_content:

A resource allocation algorithm proposed by Luss and Gupta is extended by the introduction of a numerical method for the optimal distribution of a continous resource among preselected activities as an option to the analytical method applied in the original algorithm. The numerical method allows return functions which cannot be dealt with by the analytical method. An integral part of the numerical method is a composite recurrence relation obtained from the Kuhn-Tucker conditions of the problem with linear functions substituted for the derivatives of the return functions. The convergency of the recurrence process is proven for a class of return functions.
---
paper_title: Primal Resource-Directive Approaches for Optimizing Nonlinear Decomposable Systems

paper_content:

This study presents some new results on three primal-feasible computational approaches for optimizing a system composed of interrelated subsystems. The general structure treated is the same as the principal one of the classic paper by Dantzig and Wolfe, except that convex nonlinearities are permitted, provided that the overall criterion function and coupling constraints are separable by subsystem. Each approach decentralizes the optimization by iteratively allocating system resources to the subsystems, with each subsystem computing its own optimal utilization of the given resources at each iteration. The chief obstacle to directing the resource allocation centrally toward an overall optimum is that the optimal response of each subsystem, as a function of its allowed resources, is not available explicitly. All three procedures therefore approximate or generate the optimal response functions “as needed.”
---
paper_title: A Problem in Optimum Allocation

paper_content:

In this paper we have developed an iterative process for obtaining, in a stratified sampling design, optimum allocation of the total sample to the various strata in order to secure minimum variance at a given cost and, at the same time, provide strata estimates with variabilities not exceeding specified levels. The process has been illustrated and generalized. The application of the extended procedure has been discussed.
---
paper_title: A polynomially bounded algorithm for a singly constrained quadratic program

paper_content:

This paper presents a characterization of the solutions of a singly constrained quadratic program. This characterization is then used in the development of a polynomially bounded algorithm for this class of problems.
---
paper_title: Simple Ranking Methods for Allocation of One Resource

paper_content:

This paper considers optimization problems with a nonlinear-additive objective function and a single linear constraint. Such models have numerous direct applications and serve as subproblems in procedures for more complex problems. Some important portfolio selection problems can be expressed in this form, and the problem also arises in economic theory. Several authors have noticed independently that special cases and variants of the problem can be solved exactly by surprisingly simple, finite algorithms. The major purpose of this paper is to present these results in a unified framework, which then permits substantial generalizations and extensions. The results lend themselves to an appealing managerial interpretation, similar to the rate-of-return cutoff rules of capital budgeting.
---
paper_title: ON THE DESIGN OF HIERARCHICAL PRODUCTION PLANNING SYSTEMS

paper_content:

Abstract : To provide effective managerial support to the decisions related to the production planning and scheduling processes, it is useful to partition this set of decisions in a hierarchical framework. In the resulting system higher level decisions impose constraints to lower level actions, and lower level decisions provide the necessary feedback to reevaluate higher level actions. The purpose of this paper is to suggest optimum procedures to deal with the resulting subproblems, and to analyze the interaction mechanisms among the different hierarchical levels. Computational results are given. (Author)
---
paper_title: Minimax resource allocation problems: Optimization and parametric analysis

paper_content:

Abstract We consider a linear minimax resource allocation problem with single-variable terms in the objective function and multiple knapsack-type resource constraints. All variables are continuous and nonnegative. Efficient algorithms for such large-scale problems have been developed by Luss and Smith and by Tang. This paper describes an enhanced algorithm that provides a more efficient search for the optimal solution. Further, we develop post-optimization schemes and parametric analysis that are employed once an optimal solution for the original minimax problem is obtained. Post-optimization provides a perturbed optimal solution under a specified change in the data, whereas parametric analysis provides a continuum of optimal solutions when some data elements are changed over a given interval.
---
paper_title: Component procurement and allocation for products assembled to forecast: risk-pooling effects

paper_content:

This paper considers procurement and allocation policies in a manufacturing environment where common components are assembled into various products that have stochastic demands. The components are allocated to the assembly of a product at a time when product demand is still uncertain (assemble to forecast, ATF). The special case of one component shared by N different products is analyzed, and insights into the general problem are obtained for the situation in which the common component can be reallocated to different products as product demands change. An allocation policy is developed for general distributions and prices in an ATF environment. The policy first addresses anomalies in the state of the system and then, for a feasible state, minimizes the expected excess finished-goods inventory. A procurement level that is nearly optimal is obtained from a Monte Carlo simulation in which the probability of satisfying all of the random product demands simultaneously is considered relative to this allocation policy. Numerical studies indicate that the total component and finished-goods inventory is significantly reduced by an allocation policy that incorporates risk pooling while still fulfilling sevice-level requirements.
---
paper_title: Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables

paper_content:

The allocation of a specific amount of a given resource among competitive alternatives can often be modelled as a knapsack problem. This model formulation is extremely efficient because it allows convex cost representation with bounded variables to be solved without great computational efforts. Practical applications of this problem abound in the fields of operations management, finance, manpower planning, marketing, etc. In particular, knapsack problems emerge in hierarchical planning systems when a first level of decisions need to be further allocated among specific activities which have been previously treated in an aggregate way. In this paper we provide a recursive procedure to solve such problems. The method differs from classical optimization algorithms of convex programming in that it determines at each iteration the optimal value of at least one variable. Applications and computational results are presented.
---
paper_title: Optimization Procedure for the Analysis of Coherent Structures

paper_content:

The determination of the reliability level at which to manufacture the components of a coherent structure so that the system reliability h(p) is at a certain level and the overall system cost is minimized is considered. The cost of utilizing component ci at reliability level pi, Ci(pi), is assumed to be a convex increasing function of pi with a continuous first derivative and Ci'(qi)>0 where qi is the lower bound on the reliability level for component ci. Since for most coherent structures the constraint set defines a nonconvex set, any mathematical programming procedure blindly applied to the program converges to a local optimum rather than a global optimum. However, in certain cases, the global optimum can be found for the series and parallel (SP) type of systems. The key to the solution is to optimize each module separately and then to substitute a component for each module where the cost function for the component is the value of the objective function for the module. As long as the cost function for each module maintains the convexity property with In R or In(1 - R) as the argument (R being the reliability of the module), the optimization procedure can continue and a global optimum found.
---
paper_title: Technical Note - Extension of the Luss-Gupta Resource Allocation Algorithm by Means of First Order Approximation Techniques

paper_content:

A resource allocation algorithm proposed by Luss and Gupta is extended by the introduction of a numerical method for the optimal distribution of a continous resource among preselected activities as an option to the analytical method applied in the original algorithm. The numerical method allows return functions which cannot be dealt with by the analytical method. An integral part of the numerical method is a composite recurrence relation obtained from the Kuhn-Tucker conditions of the problem with linear functions substituted for the derivatives of the return functions. The convergency of the recurrence process is proven for a class of return functions.
---
paper_title: On an Allocation Problem with Multistage Constraints

paper_content:

This paper gives a simple algorithm for finding optimal allocations subject to a hierarchy of limits when the loss function is separable strictly convex and the resources function is linear. Its applications to capital budgeting and multistage sampling are pointed out. The allocation problem considered by Srikantan [Opns. Res. 11, 265–273 (1963)] is a special case of the problem considered in this paper.
---
paper_title: A nonlinear Knapsack Problem

paper_content:

The nonlinear Knapsack problem is to minimize a separable concave objective function, subject to a single ''packing'' constraint, in nonnegative variables. We consider this problem in integer and continuous variables, and also when the packing constraint is convex. Although the nonlinear Knapsack problem appears difficult in comparison with the linear Knapsack problem, we prove that its complexity is similar. We demonstrate for the nonlinear Knapsack problem in n integer variables and knapsack volume limit B, a fully polynomial approximation scheme with running time [email protected]?((1/@e^2) (n + 1/@e^2)) (omitting polylog terms); and for the continuous case an algorithm delivering an @e-accurate solution in O(n log(B/@e)) operations.
---
paper_title: A note on a general non-linear knapsack problem

paper_content:

This paper discusses a general non-linear knapsack problem with a concave objective function and a single conves constraint. in particular, it includes an efficient procedure to find the continuous (relaxed) solution and a reduction process which computes tight lower and upper bounds on the integer variables. Some implicit enumeration criteria to be used in an enumeration algorithm are also suggested.
---
paper_title: The Nonlinear Resource Allocation Problem

paper_content:

In this paper we study the nonlinear resource allocation problem, defined as the minimization of a convex function over one convex constraint and bounded integer variables. This problem is encountered in a variety of applications, including capacity planning in manufacturing and computer networks, production planning, capital budgeting, and stratified sampling. Despite its importance to these and other applications, the nonlinear resource allocation problem has received little attention in the literature. Therefore, we develop a branch-and-bound algorithm to solve this class of problems. First we present a general framework for solving the continuous-variable problem. Then we use this framework as the basis for our branch-and-bound method. We also develop reoptimization procedures and a heuristic that significantly improve the performance of the branch-and-bound algorithm. In addition, we show how the algorithm can be modified to solve nonconvex problems so that a concave objective function can be handled. The general algorithm is specialized for the applications mentioned above and computational results are reported for problems with up to 200 integer variables. A computational comparison with a 0, 1 linearization approach is also provided.
---
paper_title: A Problem in Optimum Allocation

paper_content:

In this paper we have developed an iterative process for obtaining, in a stratified sampling design, optimum allocation of the total sample to the various strata in order to secure minimum variance at a given cost and, at the same time, provide strata estimates with variabilities not exceeding specified levels. The process has been illustrated and generalized. The application of the extended procedure has been discussed.
---
paper_title: A polynomially bounded algorithm for a singly constrained quadratic program

paper_content:

This paper presents a characterization of the solutions of a singly constrained quadratic program. This characterization is then used in the development of a polynomially bounded algorithm for this class of problems.
---
paper_title: Solving certain singly constrained convex optimization problems in production planning

paper_content:

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.
---
paper_title: Solution techniques for some allocation problems

paper_content:

This paper presents methods for solving allocation problems that can be stated as convex knapsack problems with generalized upper bounds. Such bounds may express upper limits on the total amount allocated to each of several subsets of activities. In addition our model arises as a subproblem in more complex mathematical programs. We therefore emphasize efficient procedures to recover optimality when minor changes in the parameters occur from one problem instance to the next. These considerations lead us to propose novel data structures for such problems. Also, we introduce an approximation method to solve certain equations, which arise during the procedures.
---
paper_title: Massively Parallel Algorithms for Singly Constrained Convex Programs

paper_content:

We develop four iterative algorithms for the solution of separable, convex nonlinear optimization problems with a single linear constraint and bounded variables. The design of the algorithms makes them suitable for implementation on massively parallel computers of the SIMD (i.e., Single Instruction, Multiple Data) class. The algorithms are specialized for the solution of network problems whereby the linear constraint reflects conservation of flow. Details of implementations on a Connection Machine CM-2 are reported. The numerical results indicate that all algorithms are very effective, and can solve very large problems. Three of the algorithms are also very efficient when implemented on the massively parallel system. Interestingly, the most effective algorithm (in number of steps required to solve the test problems) is the least efficient (in solution time) when implemented in parallel. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: MONOTONE OPERATORS AND THE PROXIMAL POINT ALGORITHM*

paper_content:

For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence $\{ z^k \} $ by taking $z^{k + 1} $ to be the minimizes of $f(z) + ({1 / {2c_k }})\| {z - z^k } \|^2 $, where $c_k > 0$. This algorithm is of interest for several reasons, but especially because of its role in certain computational methods based on duality, such as the Hestenes-Powell method of multipliers in nonlinear programming. It is investigated here in a more general form where the requirement for exact minimization at each iteration is weakened, and the subdifferential $\partial f$ is replaced by an arbitrary maximal monotone operator T. Convergence is established under several criteria amenable to implementation. The rate of convergence is shown to be “typically” linear with an arbitrarily good modulus if $c_k $ stays large enough, in fact superlinear if $c_k \to \infty $. The case of $T = \partial f$ is treated in extra detail. Applicati...
---
paper_title: Quadratic resource allocation with generalized upper bounds

paper_content:

In this paper we present an algorithm for solving a quadratic resource allocation problem that includes a set of generalized upper bound (GUB) constraints. The problem involves minimizing a quadratic function over one linear constraint, a set of GUB constraints, and bounded variables. GUB constraints, when added to a standard resource allocation problem, can be used to set upper limits on the amount of a resource consumed by one or more subsets of the activities. To solve the problem, we present an efficient algorithm that solves a series of quadratic knapsack subproblems and box constrained quadratic subproblems. Computational results are reported for large-scale problems with as many as 100 000 variables and 1000 constraints. The computational results indicate that our algorithm is up to 4000 times faster than the general purpose nonlinear programming software LSGRG.
---
paper_title: Algorithms for Separable Nonlinear Resource Allocation Problems

paper_content:

We consider a simple resource allocation problem with a single resource constraint. The objective function is composed of separable, convex performance functions, one for each activity. Likewise, the constraint has separable, convex resource-usage functions, one for each activity. The objective is to minimize the sum of the performance functions, subject to satisfying the resource constraint and nonnegativity constraints. This problem extends the well-studied problem in which the resource constraint is linear. We present several algorithms to solve the problem. These algorithms extend approaches developed for the linearly constrained problem. They can readily solve large problems and find the optimal solution in a number of iterations that does not exceed the number of variables. We provide several examples for illustration purposes, present computational results, and highlight the similarities and differences among the algorithms.
---
paper_title: A lagrangean relaxation algorithm for the constrained matrix problem

paper_content:

We present variants of a convergent Lagrangean relaxation algorithm for minimizing a strictly convex separable quadratic function over a transportation polytope. The algorithm alternately solves two “subproblems,” each of which has an objective function that is defined by using Lagrange multipliers derived from the other. Motivated by the natural separation of the subproblems into independent and very easily solved “subsubproblems,” the algorithm can be interpreted as the cyclic coordinate ascent method applied to the dual problem. We exhibit our computational results for different implementations of the algorithm applied to a set of large constrained matrix problems.
---
paper_title: Convex quadratic programming with one constraint and bounded variables

paper_content:

In this paper we propose an iterative algorithm for solving a convex quadratic program with one equality constraint and bounded variables. At each iteration, a separable convex quadratic program with the same constraint set is solved. Two variants are analyzed: one that uses an exact line search, and the other a unit step size. Preliminary testing suggests that this approach is efficient for problems with diagonally dominant matrices.
---
paper_title: Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming

paper_content:

The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated. Rate-of-convergence results for the “method of multipliers,” of the strong sort already known, are derived in a generalized form relevant also to problems beyond the compass of the standard second-order conditions for oplimality. The new algorithm, the “proximal method of multipliers,” is shown to have much the same convergence properties, but with some potential advantages.
---
paper_title: A pegging algorithm for the nonlinear resource allocation problem

paper_content:

In this paper we present a new algorithm for solving the nonlinear resource allocation problem. The nonlinear resource allocation problem is defined as the minimization of a convex function over a single convex constraint and bounded integer variables. We first present a pegging algorithm for solving the continuous variable problem, and then incorporate the pegging method in a branch and bound algorithm for solving the integer variable problem. We compare the computational performance of the pegging branch and bound algorithm with three other methods: a multiplier search branch and bound algorithm, dynamic programming, and a 0,1 linearization method. The computational results demonstrate that the pegging branch and bound algorithm advances the state of the art in methods for solving the nonlinear resource allocation problem.
---
paper_title: Quasi-Newton updates with bounds

paper_content:

We develop a quasi-Newton method which preserves known bounds on the Jacobian matrix. We show that this update can be computed with the same amount of work as competitive methods. In particular, we prove that the number of operations required to obtain this update is proportional to the number of nonzeros in the sparsity pattern of the Jacobian matrix. The method is also shown to share the local convergence properties of Broyden’s and Schubert’s method.
---

Title: A Survey on the Continuous Nonlinear Resource Allocation Problem

Section 1: Introduction and motivation
Description 1: Introduce the problem under consideration and discuss its general mathematical formulation, along with practical applications that motivate the study.

Section 2: Euclidean projection
Description 2: Discuss the problem of Euclidean projection onto a convex set and its applications in various optimization methods.

Section 3: Portfolio selection
Description 3: Explore the resource allocation problem in the context of portfolio selection, including the classic Markowitz optimization model.

Section 4: Resource allocation models in production economics
Description 4: Describe resource allocation problems in production economics, such as the lot sizing problem and hierarchical production planning.

Section 5: Optimum allocation in stratified sampling
Description 5: Explain the problem of optimum allocation in stratified sampling within statistics, including the goal of minimizing variance.

Section 6: Motivation and outline
Description 6: Provide the overall motivation for the survey and outline the main contributions and structure of the paper.

Section 7: The theory of search and equilibria in special games
Description 7: Present various equilibrium concepts related to the resource allocation problem, including examples from thermodynamics and marginal utility theory.

Section 8: Traffic equilibrium
Description 8: Discuss traffic equilibrium problems and their mathematical formulation, including historical context.

Section 9: The theory of search
Description 9: Describe the theory of search, particularly the problem of the US Navy searching for enemy vessels, and other related search problems.

Section 10: A weapons allocation problem
Description 10: Detail a weapons allocation problem originally studied at the RAND Corporation, using tools such as Gibbs' Lemma.

Section 11: An example application arising as a subproblem
Description 11: Provide an example where the resource allocation problem arises as a subproblem in larger optimization methods.

Section 12: Dual ascent methods for convex problems with linear constraints
Description 12: Introduce dual ascent methods for solving convex optimization problems with linear constraints.

Section 13: Dual ascent methods for separable strictly convex network flows
Description 13: Discuss the specific case of dual ascent methods applied to separable strictly convex cost network flow problems.

Section 14: A survey of techniques for our problem
Description 14: Summarize the different techniques available for solving the continuous nonlinear resource allocation problem, categorized into dual and primal (pegging) algorithms.