Search

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

This paper investigates a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. Our methodology relies on the partition of the objective function into separate low-dimensional dynamic programming (DP) models, each of which can be equivalently represented as a shortest-path problem in an underlying state-transition graph. We show that the associated transition graphs can be related by a mixed-integer linear program (MILP) so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism that dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function, and it may be embedded in branch-and-bound procedures to find provably optimal solutions. We describe how to specialize our technique for structured objectives (e.g., submodular functions) and consider three problems arising in revenue management, portfolio optimization, and healthcare. Numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in these applications. Data and the online appendix are available at https://doi.org/10.1287/mnsc.2017.2849. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

This paper combines two rival preference modeling techniques in a new approach to multi-attribute decision making. Currently existing multi-attribute procedures use either global or local preference modeling. In the global modeling technique, a single preference function is constructed in the large; its maximum is the optimal alternative. In the local procedure, sequential approximations of the preference function are constructed in the small. Each approximation generates a trial solution. Under suitable conditions, each trial solution is preferred to its predecessor, so the trial sequence eventually reaches the optimum. Each technique has advantages and disadvantages; this paper combines the desirable features of both techniques in a new improved method. This new method, called the proxy approach, uses the advantages of one technique to overcome the disadvantages of the other. This paper first develops the theoretical aspects of the proxy approach and then compares it to existing procedures. Finally, the proxy algorithm is applied to a curriculum planning problem and numerous insights are gained. [ABSTRACT FROM AUTHOR]

The motivation for this paper is a problem faced by banks which process large volumes of deposited checks. The checks must be separated by bank number before shipment to the Federal Reserve or other banks. The sorting is usually accomplished using a reader-sorter which reads the magnetic ink characters on the checks and separates them into different "pockets." This paper characterizes the optimal sorting strategy and describes an efficient procedure for finding the optimal solution for problems of the size generally found in practice. The algorithm is based on a two state dynamic programming recursion in which characterization theorems are used to drastically reduce the size of the state space and in which the storage requirements are minimal. The paper includes an analysis of computational experience and describes how the algorithm can be used in a real time environment with deadlines. [ABSTRACT FROM AUTHOR]

Consider the linear complementarity problem given in the system: (1) W = MZ + q (2) W ≥ 0, Z ≥ 0 (I) (3) Z[sup T] W = 0 where, W, Z and q are vectors of dimension n. M is a matrix of order n x n and Z[sup T] is the transpose of Z. Any (Z, W) satisfying (1), (2), and (3) is a complementary feasible solution to system (I). In the literature, a class of matrices is defined such that if M belongs to this class, then existence of a feasible solution to system (I) implies the existence of a complementary feasible solution to system (I) with W = 0. In this paper, a new class of matrices M is developed. It is shown that membership of a matrix M in M is equivalent to the property; for any q existence of a feasible solution to system (I) implies the existence of a complementary feasible solution to system (I) for that q with W = 0. This new class of matrices is not contained in any one of the known classes, namely, copositive plus, positive definite or semidefinite, P-matrices, P-matrices, Z-class, etc. [ABSTRACT FROM AUTHOR]

New lock box solution techniques have recently been suggested by Stone and Nauss-Markland. This paper briefly discusses these new methodologies and shows how the algorithms can be combined into a third solution procedure which exploits the computational efficiency of the Stone heuristic and retains the optimizing property of the Nauss-Markland algorithm. [ABSTRACT FROM AUTHOR]

The subject of this paper is a classification and discussion of algorithms for solution of nonlinear pure integer programming problems. The survey is organized by characterizing the mathematical form of the nonlinear optimization problems addressed by the various algorithms. If any method can be used without changes to solve mixed integer nonlinear programming problems that fact is mentioned in the description of the algorithm. However algorithms which must be applied only to mixed integer problems are not surveyed. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper examines the problem of deriving the tangent (or market) portfolio from a given set of risky assets and a specified risk-free borrowing and lending rate. Deriving the tangent portfolio involves solving a mathematical programming problem which can be specified as the minimization of a quadratic objective function with linear constraints. The complementary pivot algorithm has previously been shown to be capable of deriving the optimal solution to certain quadratic programming problems, subject to a nonnegativity constraint. This paper demonstrates that the algorithm can be used to derive the tangent portfolio and that the nonnegativity constraint does not pose any serious handicap. Furthermore, it is shown that the algorithm can efficiently solve large-scale problems of this nature. [ABSTRACT FROM AUTHOR]

This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e. maximization of quotients subject to constraints. In Part 1, duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too. [ABSTRACT FROM AUTHOR]

This paper investigates the optimal allocation of the marketing budget within the marketing-mix decision variables so that sales (or profit) is maximized in a planning horizon. Since the influence of marketing mix variables upon sales are, in reality, nonlinear and interactive, a geometric programming algorithm is used that solves this problem. A procedure to estimate a functional of sales on the marketing mix and environmental variables utilizing the experienced judgments of the firm's executives and the raw data is provided. The derived functional is later optimized by the Geometric Programming algorithm under a constraint set consisting of budget and strategy restrictions imposed by a firm's marketing environment, and conditions under which the optimal solution is either local or global are identified. An empirical application for a large midwestern brewery is provided which utilizes and illustrates both the estimation an optimization procedures. [ABSTRACT FROM AUTHOR]

In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed by Bock, Kantner, and Haynes [2], Pollack [7], [8], Clarke, Krikorian, and Rausan [3], Sakarovitch [9] and others. This paper first reviews the algorithms presently available for finding the K shortest loopless paths in terms of the computational effort and memory addresses they require. This is followed by the presentation of the new algorithm and its justification. Finally, the efficiency of the new algorithm is examined and compared with that of other algorithms. [ABSTRACT FROM AUTHOR]

This paper analyzes the problem of balancing resource capacity utilization against the costs of user delay or inventory investment. Instead of formulating algorithms to solve more classical versions of the problem, this paper describes ways that organizations can drop the cost curve prior to applying an optimizing algorithm. This is done by classifying the techniques and giving examples from organizations which have faced serious smoothing problems. Other organizations can improve their coat performance by adopting some of these techniques. [ABSTRACT FROM AUTHOR]

Motivated by applications in freight handling and open-pit mining, Rhys, Balinski, and Picard studied the problems of selection and closure in papers published in Management Science in 1970 and 1976. They identified efficient algorithms based on linear programming and maximum-flow/minimum-cut procedures to solve these problems. This research has had major impact well beyond the initial applications, reaching across three decades and inspiring work on numerous applications and extensions. The extensions are nontrivial optimization problems that are of theoretical interest. The applications ranged from evolving technologies, image segmentation, revealed preferences, pricing, adjusting utilities for consistencies, just-in-time production, solving certain integer programs in polynomial time, and providing efficient 2-approximation algorithms for a wide variety of hard problems. A recent generalization to a convex objective function has even produced novel solutions to prediction and Bayesian estimation problems. This paper surveys the streams of research stimulated by these papers as an example of the impact of Management Science on the optimization field and an illustration of the far-reaching implications of good original research. [ABSTRACT FROM AUTHOR]

One of the basic assumptions of the classical dynamic lot-sizing model is that the aggregate demand of a given period must be satisfied in that period. Under this assumption, if backlogging is not allowed, then the demand of a given period cannot be delivered earlier or later than the period. If backlogging is allowed, the demand of a given period cannot be delivered earlier than the period, but it can be delivered later at the expense of a backordering cost. Like most mathematical models, the classical dynamic lot-sizing model is a simplified paraphrase of what might actually happen in real life. In most real-life applications, the customer offers a grace period--we call it a demand time window--during which a particular demand can be satisfied with no penalty. That is, in association with each demand, the customer specifies an acceptable earliest and a latest delivery time. The time interval characterized by the earliest and latest delivery dates of a demand represents the corresponding time window. This paper studies the dynamic lot-sizing problem with demand time windows and provides polynomial time algorithms for computing its solution. If backlogging is not allowed, the complexity of the proposed algorithm is O(T²) where T is the length of the planning horizon. When backlogging is allowed, the complexity of the proposed algorithm is O(T³). [ABSTRACT FROM AUTHOR]

In this paper, we focus on a useful modeling concept that is frequently ignored while formulating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises: a telecommunications network design problem, a noise pollution problem, and a machine procurement and operation problem. For each case, we identify the indistinguishable objects in the model that create the problem symmetry and show how imposing certain decision hierarchies within the model significantly enhances its solvability, while using a popular modern-day commercial branch-and-cut software (CPLEX 6.5). [ABSTRACT FROM AUTHOR]

In this paper we consider a loss system where the arrivals can be classified into different groups according to their arrival rate and expected service time. While the standard admission policy consists of rejecting only those customers who arrive when all servers are busy, we address the problem of finding the optimal static admission policy (with respect to a given reward structure) when customers can be discriminated according to the group they belong to, thus customers of some groups might be automatically rejected (even if some servers remain idle) in order to enhance the global efficiency of the system. The optimality of a cmu-rule is shown, from which finite-time algorithms for the one- and two-server cases are derived. [ABSTRACT FROM AUTHOR]

The problem of determining consistent and realistic reorder intervals in complex production-distribution environments was formulated as a large scale, nonlinear, integer programming problem by Maxwell and Muckstadt (1985). They show how the special structure of the problem permits its solution by a standard network flow algorithm. In this paper, we review the Maxwell-Muckstadt model, provide necessary and sufficient conditions that characterize the solution, and show that the optimal partition of nodes in the production-distribution network is invariant to an arbitrary scaling of the set-up and holding cost parameters. We consider two capacitated versions of the model: one with a single constrained work center, and the other with multiple constrained work centers. For single constraint problems, the invariance corollary provides a simple closed-form solution. For the multiple work center problem, the invariance corollary is exploited in the development of a Lagrange multiplier method of solution. The technique is illustrated by means of a small example problem and a problem taken from a real industrial setting. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of the capacitated dynamic lot size problem, where, over time, the setup costs are nonincreasing, the unit holding costs have arbitrary pattern, the unit production costs are nonincreasing and the capacities are nondecreasing. We investigate the properties of the optimal solution for the problem and develop the concept of candidate subplan. It is proven that only the candidate subplans need to be examined in searching for an optimal solution. A dynamic programming algorithm, incorporating the concept of candidate subplan, is then devised which has run time complexity of O(T[SUP2]). [ABSTRACT FROM AUTHOR]

In this paper we study the problem of coordinating the purchase and shipment of I items in a one-warehouse, N-retailer inventory system. The model includes positive echelon holding costs, fixed costs for ordering and shipping each item, and a fixed joint item order cost at each retailer. Demand for each item at each retailer is assumed to occur at a constant and continuous rate. A mathematical model is developed based on these assumptions and the assumption that a stationary nested policy is followed. An efficient algorithm is presented based on the problem's structure that involves only sorting and runs in O(NI log NI) time. The cost of the policy computed is proven to be within 6% of the cost of an optimal nested policy. An example is presented to illustrate the problem structure and the proposed algorithm. [ABSTRACT FROM AUTHOR]

The solution technique developed in this paper integrates the simplex search algorithm into the recursive calculations of dynamic programming in order to mitigate the "curse-of-dimensionality." Since differentiation is not required as a means of optimization procedure, it is expected that this technique will have an important impact on planning problems, such as the multiple resource allocation problems which involve nondifferentiable and/or highly nonlinear performance functions. Applications of the technique to very complex problems seem to confirm the anticipated polynomial average performance. [ABSTRACT FROM AUTHOR]

Successive Linear Programming (SLP) has been used extensively in the refining and petrochemical industries for over 20 years. This paper concentrates on some recent work at Exxon to unify the treatment of nonlinear terms in 'mostly linear' models. We first discuss the source of nonlinearities in refining and petrochemical problems and propose a multiplicative formulation for the linearized subproblems to be solved by SLP. We then describe a SLP algorithm which is shown to be related to the concept of trust regions. Finally, we present an example formulation and computational results for a series of large industrial applications. [ABSTRACT FROM AUTHOR]

This paper gives optimality conditions to obtain a priori precedence relationships among some of the jobs in a single machine scheduling problem so as to curtail the enumeration while using branch-and-bound technique. The objective is to minimize a quadratic (or generalized quadratic) penalty function of job completion times. [ABSTRACT FROM AUTHOR]

This paper is concerned with the modeling and resolution of the energy generation planning problem of a large hydroelectric system for a horizon up to two years, with emphasis on hydro plant generation, hydro system aggregation, and objective function modeling. The problem has been formulated as a deterministic discrete-time optimal control problem, with linear transition equations, a highly nonlinear objective, and bounds on both the state and the control variables. The solution algorithm is of the reduced gradient type, with the control variables nonbasic to provide good conditioning. Because of the linear relationship between the state and control variables, the set of feasible directions at a point is a polyhedral convex cone and the bounds both on the state and control variables can be accounted for by means of an algorithm for the orthogonal projection of the gradient on the cone. Some computational experience with this large-scale non-linear program is given, followed by a discussion of implementation. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for deploying a crime directed patrol force. The optimization problem is formulated as the allocation of N patrol units among R high crime regions so as to maximize the weighted probability of a patrol intercept of a crime. The algorithm has full sensitivity analysis capabilities. This capability is critical because the model's input parameters include (1) crime weights, which in general will have a subjective component, (2) crime descriptive data, which are difficult to estimate, and (3) crime frequency data, which are likely to change with time. The paper presents an illustrative application of the algorithm. The resultant allocation is compared to a strategy which allocates patrol units in direct proportion to each region's total crime rate. The optimal allocation significantly increased the probability of an intercept. [ABSTRACT FROM AUTHOR]

This paper describes the integration of a network optimization algorithm with a decision and reformation system for the Graduate School of Management at UCLA. This optimization algorithm plays an important role in the determination of the annual teaching schedule by assigning faculty to courses and other activities on the basis of their responses to course preference questionnaires. In addition, the network structure provides an ideal framework for a compact information system for the department. The system can also provide some assistance in determining faculty recruiting priorities or in studying the impacts of changes in student enrollments. Our actual experiences in implementing and using this system are described. [ABSTRACT FROM AUTHOR]

The paper presents a means of attempting to account for overhead, as well as function evaluations, in evaluating unconstrained optimization techniques. Criteria are established which compare techniques on classes of algorithms. While not completely machine independent, and certainly not programmer independent, the new method eliminates much of the machine dependency of earlier criteria. The criteria are applied to three known and one new quasi-Newton algorithm, with interesting results. [ABSTRACT FROM AUTHOR]

Many nonlinear programming algorithms utilize a one-dimensional search along directions generated by the algorithm. This paper describes a method for performing this search. The method finds 3 points which bracket the minimum, fits a quadratic through them to yield a fourth point, then fits successive cubics through 4 points, discarding one each time, until certain stop criteria are met. No gradient evaluations are required. Detailed flow charts of this procedure are given, and its performance is compared with that of 2 other algorithms. Eight test problems are used in this comparison, each solved using both exterior and interior penalty functions. The Davidon-Fletcher-Powell method is used to generate the search directions. Results show that the proposed procedure requires about ½ to ¾ the computer time of its nearest competitor, a procedure designed to be especially efficient when applied to penalty functions, and about &frac13 the time of the other competitor, the 2 point cubic search using derivatives. [ABSTRACT FROM AUTHOR]

This paper is intended to present a simple and quick method for obtaining approximate solutions to large scale zero-one programming problems. The method does not use enumeration. Instead, it assigns measures of preferability to zero-one variables that change the values of the variables from zero to one. The method yields very good approximate solutions to zero-one programming problems in dramatically short computation time. Even for problems involving more than a thousand zero-one variables the computation time is of little concern. The method is applicable not only to those problems associated with obtaining the optimal package of variables with the value one but also to a great variety of binary choice ("Yes-No") problems. [ABSTRACT FROM AUTHOR]

Randomly-generated linear programming problems of three different types and five different sizes were solved by the criss-cross method and by the simplex method. One hundred problems of each type and size were solved, and the results are overwhelmingly favorable to the criss-cross method. An improvement to the criss-cross method used in these tests is given, and the extension of the results of the paper to variations of the criss-cross and simplex methods is discussed. [ABSTRACT FROM AUTHOR]

The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such problems is presented. Two numerical examples are also included. [ABSTRACT FROM AUTHOR]

The author responds to the paper "The Loading Problem," by Eilon and Christofides. He focuses on suggesting a solution to the problem. The recommended solution involves a heuristic algorithm that allegedly requires fewer computations than the one proposed by Eilon and Christofides. It is suggested that the simpler algorithm offered by the author reaches mathematical optimization as often as the aforementioned algorithm. It is further proposed that the algorithm presented by Eilon and Christofides cannot be used to solve multi-dimensional programming problems. The author goes on to discuss a numerical analysis that can be used for the allocation of industrial resources. Related mathematical models are discussed in detail. A table comparing the results of the two algorithms is also presented.

A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulation: Source of 'Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of 'Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography. [ABSTRACT FROM AUTHOR]

In this paper the Fiacco-McCormick SUMT technique is embedded in a class of inside-out algorithms. Convergence is demonstrated for the nonlinear programming problem under fairly general conditions and the algorithms are interpreted in a geometric structure. [ABSTRACT FROM AUTHOR]

Two dynamic economic lot size production systems are analyzed in this paper, the first being a single product model with backlogging and the second a multi-echelon model. In each model the objective is to find a production schedule that minimizes the total production and inventory costs. A key conceptual difficulty is that the mathematically perplexing problem of minimizing a concave function is being considered, it is shown that both models are naturally represented via single source networks. The network formulations reveal the underlying structure of the models, and facilitate development of efficient dynamic programming algorithms for calculating the optimal production schedules. [ABSTRACT FROM AUTHOR]

The usefulness of integer programming as a tool of capital budgeting hinges on the development of an efficient solution technique. An algorithm based on partial enumeration has been developed by E. L. Lawler and M. D. Bell for solving integer linear programs with 0-1 decision variables; however their algorithm is not general enough to deal with all problems in which the objective function is quadratic. This paper extends Lawler and Bell's method so that it can be generally applied to integer quadratic programs. The new algorithm is illustrated by examples from capital budgeting. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of dynamic programming problems requiring the determination of optimal policies for the control of a special class of stochastic processes when the time horizon of the planning period is at infinity. These processes can be mathematically described as discrete time parameter Markov chains with a finite number of states which have been "embedded" in continuous time in the sense that the time between transitions is a random variable whose probability distribution depends only on the states between which the transition takes place. Such processes are called Markov-renewal processes. The Markov processes considered by R. A. Howard in [1] are really two special cases of this somewhat wider class of stochastic processes. In these two special cases, the algorithm of this paper is identical with Howard's. In fact, with only slight modification, Howard's algorithm can be extended to this wider class of stochastic processes. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to illustrate some applications of the functional equation technique of the theory of dynamic programming to a general class of problems arising in the study of networks, particularly those arising in transportation theory. [ABSTRACT FROM AUTHOR]

In this paper, it is shown that the "caterer" problem, a problem in mathematical economics and logistics which has been discussed by Jacobs, Gaddum, Hoffman and Sokolowsky, and Prager, can be reduced to the problem of determining the maximum of the linear form Ln = ∑I=1nv1, subject to a series of constraints of the form V1 ≦ b1, v1 +v2 ≦ b2, v1 + v2 +v3 ≦ b2, ߪ, v1 + v2 + … + vK ≦ bK, v2 + v3 + … + vK+1 ≦ bK+1, …, vb-h+1 + … + Vn ≦ bn, 0 ≦ rI, I = 1, 2, … , n, under an assumption concerning the nonaccumulation of dirty laundry. This maximization problem is solved explicitly, using the functional equation technique of dynamic programming. [ABSTRACT FROM AUTHOR]

In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and finds all the desired points in a finite number of steps by changing the weights of the objective functions in a systematic way. We develop further variations of the algorithm to improve its computational performance and demonstrate our algorithm’s performance on multiobjective assignment, knapsack, and traveling salesperson problems with three and four objectives. [ABSTRACT FROM AUTHOR]

In this paper, a market-based decomposition method for decomposable linear systems is developed. The solution process iterates between a master problem that solves the market-matching problem, and subproblems that solve the agents' bundle-determination problems. Starting from any initial price and feasible allocation, system optimality can be achieved under a dynamic market-trading algorithm in a finite number of trades. The final market-clearing prices are discovered by this market trading and an efficient allocation is achieved by direct, wealth-improving resource exchanges among self-interested agents. Certain types of strategic behavior by the agents and a dealer in the marketplace are studied as well. Our proposed market mechanism addresses price dynamics, incentive issues, and economic transactions of real-world, distributed decision-making situations more realistically than traditional decomposition approaches. In addition, it can be operated in both synchronous and asynchronous environments. We provide a market-based paradigm for decentralized problem solving and information processing that can be easily implemented to support real-time optimization of distributed systems. [ABSTRACT FROM AUTHOR]

In a recent article, Bertsimas and Popescu showed that a tight upper bound on a European-type call option price, given the first n moments of the distribution of the underlying security price, can be obtained by solving an associated semidefinite programming problem (SDP). The purpose of this paper is to improve and extend their results. We will show that a tight lower bound can be calculated by solving another SDP. Also, we will show that these problems can be solved very quickly by a newly developed cutting plane algorithm when n is less than six or seven. [ABSTRACT FROM AUTHOR]

Cell suppression is a widely used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2-and 3-dimensional tables whose entries are subject to marginal totals. In this paper we address the problem of protecting sensitive data in a statistical table whose entries are linked by a generic system of linear constraints. This very general setting covers, among others, k -dimensional tables with marginals as well as the so-called hierarchical and linked tables that are very often used nowadays for disseminating statistical data. In particular, we address the optimization problem known in the literature as the (secondary) Cell Suppression Problem, in which the information loss due to suppression has to be minimized. We introduce a new integer linear programming model and outline an enumerative algorithm for its exact solution. The algorithm can also be used as a heuristic procedure to find near-optimal solutions. Extensive computational results on a test-bed of 1,160 real-world and randomly generated instances are resented, showing the effectiveness of the approach In particular, we were able to solve to proven optimality 4-dimensional tables with marginals as well as linked tables of reasonable size (to our knowledge, tables of this kind were never solved optimally by previous authors). [ABSTRACT FROM AUTHOR]

Routing problems appear frequently when dealing with the operation of communication or transportation networks. Among them, the message routing problem plays a determinant role in the optimization of network performance. Much of the motivation for this work comes from this problem which is shown to belong to the class of nonlinear convex multicommodity flow problems. This paper emphasizes the message routing problem in data networks, but it includes a broader literature overview of convex multicommodity flow problems. We present and discuss the main solution techniques proposed for solving this class of large-scale convex optimization problems. We conduct some numerical experiments on the message routing problem with four different techniques. [ABSTRACT FROM AUTHOR]

Approaches like finite differences with common random numbers, infinitesimal perturbation analysis, and the likelihood ratio method have drawn a great deal of attention recently as ways of estimating the gradient of a performance measure with respect to continuous parameters in a dynamic stochastic system. In this paper, we study the use of such estimators in stochastic approximation algorithms, to perform so-called "single-run optimizations" of steady-state systems. Under mild conditions, for an objective function that involves the mean system time in a G//G/1 queue, we prove that many variants of these algorithms converge to the minimizer. In most cases, however, the simulation length must be increased from iteration to iteration; otherwise the algorithm may converge to the wrong value. One exception is a particular implementation of infinitesimal perturbation analysis, for which the single-run optimization converges to the optimum even with a fixed (and small) number of ends of service per iteration. As a by-product of our convergence proofs, we obtain some properties of the derivative estimators that could be of independent interest. Our analysis exploits the regenerative structure of the system, but our derivative estimation and optimization algorithms do not always take advantage of that regenerative structure. In a companion paper, we report numerical experiments with an M/M/1 queue, which illustrate the basic convergence properties and possible pitfalls of the various techniques. [ABSTRACT FROM AUTHOR]

The bandwidth packing (BWP) problem is a combinatorially difficult problem arising in the area of telecommunications. The problem consists of assigning calls to paths in a capacitated graph, such that capacities are not violated and the total profit is maximized. In this paper we discuss the development of a tabu search (TS) method for the BWP problem. The method makes use of an efficient implementation of the k-shortest path algorithm, that allows the identification of a controlled set of feasible paths for each call. A tabu search is then performed to find the best path assignment for each call. The TS method developed here incorporates a number of features that have proved useful for obtaining optimal and near optimal solutions to difficult combinatorial problems. We establish the effectiveness of our approach by comparing its performance in speed and solution quality to other specialized heuristics and to a standard optimization package applied to a 0-1 integer programming formulation of the problem. [ABSTRACT FROM AUTHOR]

It is known that minimum cost flow problems can be solved by successive augmentations along shortest paths. In this paper the issues of implementing shortest path algorithms in this context are examined. Of particular interest is the dynamic topology that the flow networks exhibit. We develop a network generator capable of emulating such topology. Strategies for exploiting the special structures in such networks are discussed. A set of 9000 test problems is offered, from which a particular strategy/algorithm combination is shown to consistently produce superior results when compared to the other combinations. [ABSTRACT FROM AUTHOR]

This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given. [ABSTRACT FROM AUTHOR]

Recently there has been considerable interest in the average-case performance of heuristics. This paper pursues that interest, where it concerns sequencing and packing problems. In particular, we survey the methods that have been used to obtain formal probabilistic analyses of heuristics for makespan scheduling and one-dimensional bin packing. In so doing, we present many of thc key results in these research areas. [ABSTRACT FROM AUTHOR]