Search

The Fermat location problem is to find a point whose sum of weighted distances from m given points (vertices) is a minimum. The best known method of solution is an iterative scheme devised by Weiszfeld in 1937, which converges to the unique minimum point unless one of the iterates happens to "land" on a nonoptimal vertex. The convergence proof of this scheme depends on two theorems, one of which (descent theorem) states that the objective function strictly decreases at each step. This paper extends the descent theorem by proving: (1) there is a "ball" whose radius and center depend on the Weiszfeld iteration, such that any algorithm whose iterates are "in the ball" or "on its surface" is a descent algorithm; (2) under certain circumstances, one or more of the vertices may be deleted, although the weight(s) are taken into account, and the Weiszfeld algorithm retains its descent property. In general there are several subsets of vertices which may be deleted, and for each subset, a corresponding iterate; (3) the convex hull of these iterates is such that all points within it have the descent property. Examples of the potential application of these extensions are given, including the construction of a modified Weiszfeld algorithm that without exception converges to the optimum. Beyond that, it is hoped the theorems may in time be useful in proving the descent property of yet to be discovered, very fast, nongradient algorithms. [ABSTRACT FROM AUTHOR]

The traffic assignment problem associated with a given transportation network is the process of distributing zone-to-zone trips on links of the network. A number of methods have been proposed to solve this problem, but none have been found to be entirely satisfactory. This paper is concerned with the nonlinear mathematical model of the problem, where the link-traveling costs are increasing functions of the link flows and no explicit capacity constraint is imposed on individual links. An efficient algorithm is developed, using a node-arc formulation of the problem. It is an adaptation of the convex-simplex method that takes advantage of the very special network structure of the traffic assignment problem formulated in this way. Numerical results obtained with a moderate size street network are presented. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present efficient algorithms for computing solutions to systems of nonlinear equations with a block diagonal structure. The special structure of the systems, which arises in economic models, allows us to use the decomposition of the problems. [ABSTRACT FROM AUTHOR]

This paper presents two new combinatorial algorithms for the generalized circulation problem. After an initial step in which all flow-generating cycles are canceled and excesses are created, both algorithms bring these excesses to the sink via highest-gain augmenting paths. Scaling is applied to the fixed amount of flow that the algorithms attempt to send to the sink, and both node and arc excesses are used. The algorithms have worst-case complexities of O(m²(m + n log n) log B), where n is the number of nodes, in is the number of arcs, and B is the largest integer used to represent the gain factors and capacities in the network. This bound is better than the previous best bound for a combinatorial algorithm for the generalized circulation problem, and if m = O(n4/3-c), it is better than the previous best bound for any algorithm for this problem. [ABSTRACT FROM AUTHOR]

This paper presents a fast algorithm to solve the intersection problem for a pair of nondecreasing and nonincreasing strong map sequences of submodular systems. The worst-case time bound is the same as that of the push/relabel algorithm for a single intersection problem. This extends the Gallo-Grigoriadis-Tarjan (GGT) method for parametric maximum flow problems and reveals an algorithmic significance of the concept of strong maps for submodular systems. [ABSTRACT FROM AUTHOR]

Given a certain monotone horizontal linear complementarity problem (HLCP), we can naturally construct a family of systems of nonlinear equations parametrized by a parameter t € (0, 1] with the property that, as I tends to 0, the corresponding system "converges" to the HLCP. Under reasonable conditions, it has been shown that each system of the family has a unique solution and that, as t tends to 0, these solutions converge to a specific solution of the HLCP. The main purpose of this paper is to study the asymptotic behavior of the derivative of the trajectory of solutions and therefore obtain information on the way the trajectory approaches the solution set of the HLCP. We show that the trajectory of solutions converges to the solution set along a unique and well-characterized direction. Moreover, if the HLCP has a solution satisfying strict complementarity then the direction forms a definite angle with any face of the feasible region which contains the limit point; otherwise, the direction is tangent to some face of the feasible region. [ABSTRACT FROM AUTHOR]

In this paper we present a new primal-dual affine scaling method for linear programming. The method yields a strictly complementary optimal solution pair, and also allows a polynomial-time convergence proof. The search direction is obtained by using the original idea of Dikin, namely by minimizing the objective function (which is the duality gap in the primal-dual case), over some suitable ellipsoid. This gives rise to completely new primal-dual affine scaling directions, having no obvious relation with the search directions proposed in the literature so far. The new directions guarantee a significant decrease in the duality gap in each iteration, and at the same time they drive the iterates to the central path. In the analysis of our algorithm we use a barrier function which is the natural primal-dual generalization of Karmarkar's potential function. The iteration bound is O(nL), which is a factor O(L) better than the iteration bound of an earlier primal-dual affine scaling method (Monteiro, Adler and Resende 1990). [ABSTRACT FROM AUTHOR]

The article presents fast algorithms that find approximate solutions for a general class of problems, which is called fractional packing and covering problems. According to the authors, the only previously known algorithms for solving these problems are based on general linear programming techniques. The algorithm developed by the authors in this study, is a Lagrangian relaxation technique and greatly outperforms the general methods in many applications. The new approach as devised by the authors, yields several orders of magnitude of improvement over the best previously known running times for algorithms for the scheduling of unrelated parallel machines in both the preemptive and the non-preemptive models, for the job shop problem, for the Held and Karp bound for the traveling salesman problem, for the cutting-stock problem, for the network embedding problem, and for the minimum-cost multicommodity flow problem. The cutting-stock problem is an example of a covering problem: paper is produced in wide rolls, called raws, and then subdivided into several different widths of narrower ones, called finals.

This paper studies approximation algorithms for the problem of nonpreemptively scheduling n jobs on a single machine to minimize total weighted late work, where the late work for a job is the amount of processing of this job that is performed after its due date. A family of approximation algorithms {DP€} is derived. For any € > 0, DP€ delivers a schedule having total weighted late work which does not exceed (1 + €) times that of an optimal schedule. Since DP€ requires O(n³ log n + n³/€) time, the family {DP€} is a fully polynomial approximation scheme. [ABSTRACT FROM AUTHOR]

A dynamic factorization algorithm is developed which uses a partition of the basis to permit the simplex method to be executed from a small working inverse and a small, sparse triangular submatrix of the basis. This partition is maintained dynamically using spike swapping in a way which seeks to keep the size of the working inverse as small as possible. The algorithm is intended for use in solving general large scale linear programming problems. It is especially well suited for problems whose simplex basis has a small number of spikes after application of the Hellerman and Rarick P³ procedure. Preliminary computation experience and direct comparison with Reid's sparsity-exploiting variant of the Bartels-Golub decomposition for LP bases indicate that a significant reduction is obtained with the dynamic factorization approach in the nonzero elements needed to represent the basis inverse. For all bases considered the number of nonzero elements needed to represent the inverse immediately prior to reinversion is reduced by a factor of 1.7 to 20. [ABSTRACT FROM AUTHOR]

N jobs are to be sequenced on a single machine, each job carrying a penalty cost which is a quadratic function of its completion time. The objective is to find a sequence which minimizes the total penalty. Criteria are developed for ordering a pair of adjacent jobs in a sequence and these are incorporated into a branch-and-bound procedure. [ABSTRACT FROM AUTHOR]

The production smoothing problem with known demands that are assumed to increase with time is treated. The production and inventory costs are concave. The cost of increasing production from one period to the next is a concave function of the increase; similarly, the cost of decreasing production is a concave function of the decrease. Backlogging is not permitted. In each period, a fixed production capacity that does not vary with time is available. The problem is similar to that discussed by Zangwill, except for the important difference of capacity constraint. Feasible production plans are partitioned into sets on the basis of production differences from period to period -- those with production increases in all N periods, those with a decrease only in the final period, etc. A minimum cost plan is an extreme point of one of these sets. We show that an extreme point plan is such that in between periods with zero inventory there is at most one sequence of periods when production is neither zero nor capacity and within these periods, production does not change. An algorithm is proposed for generating extreme point production plans. It is shown that finding the minimum cost production plan is equivalent to finding the shortest route through an acyclic network of extreme point production plans. The approach put forth enables a complete solution to the problem discussed. [ABSTRACT FROM AUTHOR]

A Lagrangian column-generation procedure is developed which retains the original problem functions for column generation but uses transformed penalty functions in the Lagrangian optimization. The class of penalty functions considered maintains the original order of differentiability and often enhances the optimization operation. Convergence is proven for convex problems and limited computational experience cited where the new procedure converges two to four times faster than the standard method. Certain modifications of these techniques to attack nonconvex problems are also presented. [ABSTRACT FROM AUTHOR]

Decision-making processes usually involve time-consuming and costly operations of observation and communication of the state of the environment and generation and implementation of appropriate actions. Collectively these activities may be called computational and the procedure required to carry them out may be called an algorithm. If the environment is changing stochastically the fixed computational delay involved in operating the algorithm yields obsolete actions resulting in reduced expected return. The loss as a function of delay is a measure of efficiency of the algorithm which depends upon the stochastic properties of the environment. If it is possible to reduce the loss by employing a faster algorithm at a higher cost, the algorithm may be optimally designed and selected from a given family. [ABSTRACT FROM AUTHOR]

This paper presents algorithms for finding solutions and planning horizons to two related T period, one product, deterministic production problems with capacity constraints and penalty costs for unsatisfied demand. The algorithms are derived from an application of 1 techniques to problems with inequality constraints. [ABSTRACT FROM AUTHOR]

This paper presents two versions of a method for solving large linear programs through decomposition. In both versions the problem is decomposed into subprograms as in the DANTZIG-WOLFE model, but each version uses a different type of linking program. The subprograms are first solved, and then the infeasibility of the resulting solution for the linking program is used to generate a price-adjustment process (much like a market mechanism), which gradually corrects the objective functions of the subprograms, until either some optimal solutions to the latter yield a feasible solution to the linking program (then the problem is solved), or evidence is obtained that the problem has no feasible solution. [ABSTRACT FROM AUTHOR]

The article presents information on professor Egon Balas' approach to solve linear programs. The purpose of this note is to propose additional test meant to increase the power of Balas' algorithm by reducing the number of possible solutions examined in the course of computation and to propose an application for which the algorithm appears particularly well-suited. It now includes the issue of generating and searching the solution tree. One should first note that for many problems a feasible solution is known in advance. This solution may be used to establish a starting value for other than infinity, thereby expediting convergence to the optimum. But such a solution may also be used in another way. If it is suspected that an appreciable fraction of the variables for the feasible solution coincide in value to those for some optimal solution, it may be useful to employ a two-stage algorithm that treats the 'primary' variables set at unity in the feasible solution differently from the 'secondary' variables set equal to zero.

Group theory is used to integrate a wide variety of integer programming methods into a common computational process. Included are group optimization algorithms, Lagrangian methods, the cutting plane method, and the method of surrogate constraints. These methods are controlled by a supervisor which performs four main functions: set-up, directed search, subproblem analysis, and prognosis. Some computational experience is given. One appendix contains an algorithm for dynamically solving unconstrained group problems. A second appendix gives an algorithm for solving zero-one group problems. [ABSTRACT FROM AUTHOR]

The problem of simultaneously making price and production decisions for a single product with a known deterministic demand function is considered. The objective is to maximize profit, and backorders are not allowed. Results which reduce the computations necessary for the pricing decision are given, and planning horizons are identified as in previous inventory research. These results are combined into an efficient forward algorithm. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm that can be used to solve two types of network sensitivity problems. In the first, arcs are subject to breakdowns that degrade their capacities. It is required, within certain confidence limits, to find the maximum possible effect of n breakdowns on maximum flow. In the second, arcs are subject to improvements that reduce their lengths. It is required, also within certain confidence limits, to find the maximum possible effect n total improvements can have on shortest path length. Capacities resulting from breakdown and lengths resulting from improvements are random variables specified by their mean values and variances. [ABSTRACT FROM AUTHOR]

By constructing a new infinite dimensional space for which the extreme point--linear independence and opposite sign theorems of Charnes and Cooper continue to hold, and, building on a little-known work of Ear (herein presented), an extended dual theorem comparable in precision and exhaustiveness to the finite space theorem is developed. Building further on this a dual theorem is developed for arbitrary convex programs with convex constraints which subsumes in principle all characterizations of optimality or duality in convex programming. No differentiability or constraint qualifications are involved, and the theorem lends itself to new computational procedures. [ABSTRACT FROM AUTHOR]

A point lies on a network according to some unknown probability distribution. Starting at a specified root of the network, a Searcher moves to find this point at speeds that depend on his location and direction. He seeks the randomized search algorithm that minimizes the expected search time. This is equivalent to modeling the problem as a zero-sum hide-and-seek game whose value is called the search value of the network. We make a new and direct derivation of an explicit formula for the search value of a tree, proving that it is equal to half the sum of the minimum tour time of the tree and a quantity called its incline. The incline of a tree is an average over the leaf nodes of the difference between the time taken to travel from the root to a leaf node and the time taken to travel from a leaf node to the root. This difference can be interpreted as height of a leaf node, assuming uphill is slower than downhill. We then apply this formula to obtain numerous results for general networks. We also introduce a new general method of comparing the search value of networks that differ in a single arc. Some simple networks have very complicated optimal strategies that require mixing of a continuum of pure strategies. Many of our results generalize analogous ones obtained for constant velocity (in both directions) by S. Gal, but not all of those results can be extended. [ABSTRACT FROM AUTHOR]

We present a branch-and-price algorithm to solve personalized multi-activity shift scheduling problems. The subproblems in the column generation method are formulated using grammars and solved with dynamic programming. The expressiveness of context-free grammars is exploited to easily model restrictions over shifts, allowing the branch-and-price algorithm to solve large-scale problem instances. We present computational experiments on two types of multi-activity shift scheduling problems and compare our approach with existing methods in the literature. These experiments show that our approach can efficiently solve large-scale instances and is flexible enough to model different classes of problems. [ABSTRACT FROM AUTHOR]

We study the problem of finding an envy-free allocation of a cake to d+1 players using d cuts. Two models are considered, namely, the oracle-function model and the polynomial-time function model. In the oracle-function model, we are interested in the number of times an algorithm has to query the players about their preferences to find an allocation with the envy less than ∈. We derive a matching lower and upper bound of θ(1/∈)d-1 for players with Lipschitz utilities and any d >1. In the polynomial-time function model, where the utility functions are given explicitly by polynomial-time algorithms, we show that the envy-free cake-cutting problem has the same complexity as finding a Brouwer's fixed point, or, more formally, it is PPAD-complete. On the fiip side, for monotone utility functions, we propose a fully polynomial-time algorithm (FPTAS) to find an approximate envy-free allocation of a cake among three people using two cuts. [ABSTRACT FROM AUTHOR]

We study the problem of (re)designing the regional network by which cadaveric livers are allocated. Whereas W prior research focused mainly on maximizing a measure of efficiency of the network that was based on aggregate patient survival, we explicitly account for the trade-off between efficiency and a measure of geographical equity in the allocation process. To this end, we extend earlier optimization models to incorporate both objectives and develop an exact branch-and-price approach to solve this problem, generalizing a solution approach studied for the case where only efficiency is taken into account. In addition, we propose an effective solution algorithm that approximates the (generally nonconcave) frontier of Pareto-efficient solutions with respect to the two objectives by simultaneously generating and successively improving upper and lower bounds on this frontier. We implement and test our approach on observed data and show that solutions significantly dominating the current configuration in both efficiency and equity can be found. Of course, other subjective criteria are needed to choose among the different Pareto-efficient candidate solutions. [ABSTRACT FROM AUTHOR]

The problem of routing trains through railway junctions is an integral part of railway operations. Large junctions are highly interconnected networks of track where multiple railway lines merge, intersect, and split. The number of possible routings makes this a very complicated problem. We show how the problem can be formulated as a set-packing model with a resource-based constraint system. We prove that this formulation is tighter than the conventional node-packing model, and develop a branch-and-price algorithm that exploits the structure of the set-packing model. A discussion of the variable generation phase, as well as a pricing routine in which these variables are represented by tree structures, is also described. Computational experiments on 25 random timetables show this to be an efficient approach. [ABSTRACT FROM AUTHOR]

A choice model based on direct utility maximization subject to an arbitrary number of constraints is developed and applied to conjoint data. The model can accommodate both corner and interior solutions, and it provides insights into the proportion of respondents bound by each constraint. Application to volumetric choice data reveals that the majority of respondents make choices consistent with price and quantity restrictions. Estimates based on a single monetary-constraint choice model are shown to lead to biased estimates of the monetary value of attribute levels. [ABSTRACT FROM AUTHOR]

We consider a network where nodes communicate by exchanging information packets whose fields include the address of the sending node and that of the destination node. In the absence of some verification mechanism, an attacking node can send packets to another node using a forged origin address. In this study, we consider an optimization problem of identifying a minimum cardinality subset of verification nodes on a tree such that the number of attacks from any forged origin to any destination is limited to a prescribed level. For the case in which communication is permitted between every node in the tree, we develop an optimal polynomial-time dynamic programming algorithm for this problem. We compare the performance of the dynamic programming algorithm against a mixed-integer programming model on randomly generated tree networks at varied levels of security. [ABSTRACT FROM AUTHOR]

We consider the problem of determining a set of optimal tariffs for an agent in the network, who owns a subset of all the arcs, and who receives revenue by setting the tariffs on the arcs he owns. Multiple rational clients are active in the network, who route their demands on the least expensive paths from source to destination. The cost of a path is determined by fixed costs and tariffs on the arcs of the path. We introduce a remodeling of the network, using shortest paths. We develop three algorithms based on this shortest-path graph model: a combinatorial branch-and-bound algorithm, a path-oriented mixed integer program, and a known-arc-oriented mixed integer program. Combined with reduction methods, this remodeling enables us to solve the problem to optimality, for quite large instances. We provide computational results for the methods developed and compare them with the results of the arc-oriented mixed integer programming formulation of the problem, applied to the original network. [ABSTRACT FROM AUTHOR]

When is the linear image of a closed convex cone closed? We present very simple and intuitive necessary conditions that (1) unify, and generalize seemingly disparate, classical sufficient conditions such as polyhedrality of the cone, and Slater-type conditions; (2) are necessary and sufficient, when the dual cone belongs to a class that we call nice cones (nice cones subsume all cones amenable to treatment by efficient optimization algorithms, for instance, polyhedral, semidefinite, and p-cones); and (3) provide similarly attractive conditions for an equivalent problem: the closedness of the sum of two closed convex cones. [ABSTRACT FROM AUTHOR]

The article presents O(N log N) algorithm for the rectilinear round-trip location problem. It refers to papers by authors A.W. Chan and D.W. Hearn, where the problem definition is given and by authors T. Ichimori and T. Nishida, where it is shown that this problem can be solved in O(N log N) time.

We consider both branch-and-cut and column-generation approaches for the problem of finding a minimum-cost assignment of jobs with release dates and deadlines to unrelated parallel machines. Results are presented for several variants both with and without constraint programming. Among the variants, the most effective strategy is to combine a tight and compact, but approximate, mixed integer programming (MIP) formulation with a global constraint testing single machine feasibility. Instances with up to nine machines and 54 jobs have been solved. All the algorithms have been implemented in the Mosel modeling and optimization language. [ABSTRACT FROM AUTHOR]

Deterministic fluid models are developed to provide simple first-order performance descriptions for multiserver queues with abandonment under heavy loads. Motivated by telephone call centers, the focus is on multiserver queues with a large number of servers and nonexponential service-time and time-to-abandon distributions. The first fluid model serves as an approximation for the G/GI/s + GI queueing model, which has a general stationary arrival process with arrival rate λ, independent and identically distributed (IID) service times with a general distribution, s servers and IID abandon times with a general distribution. The fluid model is useful in the overloaded regime, where λ > s, which is often realistic because only a small amount of abandonment can keep the system stable. Numerical experiments, using simulation for M/GI/s + GI models and exact numerical algorithms for M/M/s + M models, show that the fluid model provides useful approximations for steady-state performance measures when the system is heavily loaded. The fluid model accurately shows that steadystate performance depends strongly upon the time-to-abandon distribution beyond its mean, but not upon the service-time distribution beyond its mean. The second fluid model is a discrete-time fluid model, which serves as an approximation for the Gt/GI/s + GI queueing model, having a state-dependent and time-dependent arrival process. The discretetime framework is exploited to prove that properly scaled queueing processes in the queueing model converge to fluid functions as s → ∞. The discrete-time framework is also convenient for calculating the time-dependent fluid performance descriptions. [ABSTRACT FROM AUTHOR]

We consider the n-player houseswapping game of Shapley and Scarf (1974), with indifferences in preferences allowed. It is well known that the strict core of such a game may be empty, single valued, or multi valued. We define a condition on such games called segmentability, which means that the set of players can be partitioned into a top trading segmentation. It generalizes Gale's well-known idea of the partition of players into top trading cycles (which is used to find the unique strict core allocation in the model with no indifference). We prove that a game has a nonempty strict core if and only if it is segmentable. We then use this result to devise an O n3 algorithm which takes as input any houseswapping game, and returns either a strict core allocation or a report that the strict core is empty. Finally, we are also able to construct a linear inequality system whose feasible region's extreme points precisely correspond to the allocations of the strict core. This last result parallels the results of Vande Vate (1989) and Rothblum (1992) for the marriage game of Gale and Shapley (1962). [ABSTRACT FROM AUTHOR]

We propose a numerical approach to compute stationary Markov perfect Nash equilibrium advertising strategies of the Lanchester model. The algorithm can be implemented using a standard mathematical package, and, importantly, it does not require that the players discount their future earnings at a zero rate, an assumption that has been made in the literature. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing project duration in an environment where each project activity can be executed by a number of different flexible resources. The capabilities of the flexible resources are modeled using a binary activity-resource matrix A called the availability matrix. Activity durations are known deterministically. We develop tight lower bounds and a variety of heuristics accompanied with extensive computational tests regarding their performance. It is shown that our algorithms consistently perform near optimally. Using these heuristics, we perform experiments on the effect of operating flexibility on project duration, where resource flexibility is measured by the number of resources available per activity, and the form of the availability matrix A. Our experiments lead to important managerial guidelines regarding the role of resource flexibility on project duration. For instance, it is found that when the flexible capabilities of the resources are evenly distributed across the activities, small improvements in resource flexibilities provide nearly the same benefits in project duration as a system of fully flexible resources. [ABSTRACT FROM AUTHOR]

We provide a new mathematical model for strategic traffic management, formulated and analyzed as a mathematical program with equilibrium constraints (MPEC). The model includes two types of control (upper-level) variables, which may be used to describe such traffic management actions as traffic signal setting, network design, and congestion pricing. The lower-level problem of the MPEC describes a traffic equilibrium model in the sense of Wardrop, in which the control variables enter as parameters in the travel costs. We consider a (small) variety of model settings, including fixed or elastic demands, the possible presence of side constraints in the traffic equilibrium system, and representations of traffic flows and management actions in both link-route and link-node space. For this model, we also propose and analyze a descent algorithm. The algorithm utilizes a new reformulation of the MPEC into a constrained, locally Lipschitz minimization problem in the product space of controls and traffic flows. The reformulation is based on the Minty (1967) parameterization of the graph of the normal cone operator for the traffic flow polyhedron. Two immediate advantages of making use of this reformulation are that the resulting descent algorithm can be operated and established to be convergent without requiring that the travel cost mapping is monotone, and without having to ever solve the lower-level equilibrium problem. We provide example realizations of the algorithm, establish their convergence, and interpret their workings in terms of the traffic network. [ABSTRACT FROM AUTHOR]

The problem of minimizing the time taken to load the containers from the container stack yard onto the ship is called the transtainer routing problem. We first do a theoretical investigation of the problem to understand the structural properties of the problem. We then use these results to prove that the problem is NP-Complete. The problem is then formulated as an integer program. A branch-and-bound based enumerative method is developed to obtain an exact solution to the problem. An algorithm to solve the matching problem on a line at the root node of the branch-and-bound tree is developed. Several lower bounds to prune the size of the tree are also developed. A result which states that there cannot exist a polynomial time heuristic with a bounded worst case unless P = NP is proved. Based on this result, an enumerative heuristic with a worst-case performance ratio of 1.5 is designed. Computational tests on randomly generated problems are conducted to evaluate the exact and heuristic algorithms. [ABSTRACT FROM AUTHOR]

The undirected capacitated are routing problem (CARP)arises naturally in several applications where streets require maintenance, or customers located along road must be serviced. Basic algorithmic procedures have recently been developed for the design of heuristics in an arc routing context. This article reports on the use of these basic tools in a variable neighborhood descent algorithm for the solution of the undirected CARP. [ABSTRACT FROM AUTHOR]

Retrieving information from heterogeneous database systems involves a complex process and remains a challenging research area.We propose a cognitively guided approach for developing an information-retrieval agent that takes the user's information request, identifies relevant information sources,and generates a multidatabase access plan. Our work is distinctive in that the agent design is based on an empirical study of how human experts retrieve information from multiple, heterogeneous database systems. To improve on empirically observed information-retrieval capabilities, the design incorporates mathematical models and algorithmic components. These components optimize the set of information sources that need to be considered to respond to a user query and are used to develop efficient multidatabase-access plans. This agent design, which integrates cognitive and mathematical models, has been implemented using Soar, a knowledge-based architecture. [ABSTRACT FROM AUTHOR]

This article proposes an optimization model for simultaneous estimation of an origin-destination (O-D) matrix and a travel-cost coefficient for congested networks in a logit-based stochastic user equilibrium (SUE). The model is formulated in the form of a standard differentiable, nonlinear optimization problem with analytical stochastic user equilibrium constraints. Explicit expressions of the derivatives of the stochastic user equilibrium constraints with respect to origin-destination demand, link flow, and travel-cost coefficient are derived and computed efficiently through a stochastic network-loading approach. A successive quadratic-programming algorithm using the derivative information is applied to solve the simultaneous estimation model. This algorithm converges to a Karusch-Kuhn-Tucker point of the problem under certain conditions. The proposed model and algorithm are illustrated with a numerical example. [ABSTRACT FROM AUTHOR]

The problem of distributing gas through a network of pipelines is formulated as a cost minimization subject to nonlinear flow-pressure relations, material balances, and pressure bounds. The solution method is based on piecewise linear approximations of the nonlinear flow-pressure relations. The approximated problem is solved by an extension of the Simplex method. The solution method is tested on real-world data and compared with alternative solution methods. [ABSTRACT FROM AUTHOR]

Copyright of Management Science is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This article develops and illustrates a new knowledge discovery algorithm tailored to the action requirements of management science applications. The challenge is to develop tactical planning forecasts at the SKU level. We use a traditional market-response model to extract information from continuous variables and use datamining techniques on the residuals to extract information from the many-valued nominal variables, such as the manufacturer or merchandise category. This combination means that a more complete array of information cart be used to develop tactical planning forecasts. The method is illustrated using records of the aggregate sales during promotion events conducted by a 95-store retail chain in a single trading area. In a longitudinal cross validation, the statistical forecast (PromoCast™) predicted the exact number of cases of merchandise needed in 49% of the promotion events and was within ± one case in 82% of the events. The dataminer developed rules from an independent sample of 1.6 million observations and applied these rules to almost 460,000 promotion events in the validation process. The dataminer had sufficient confidence to make recommendations on 46% of these forecasts. In 66% of those recommendations, the dataminer indicated that the forecast should not be changed. In 96% of those promotion events where "no change" was recommended, this was the correct "action" to take. Even including these "no change" recommendations, the dataminer decreased the case error by 9% across all promotion events in which rules applied. [ABSTRACT FROM AUTHOR]

We present a modification of the simulated annealing algorithm designed for solving discrete stochastic optimization problems. Like the original simulated annealing algorithm, our method has the hill climbing feature, so it can find global optimal solutions to discrete stochastic optimization problems with many local solutions. However, our method differs from the original simulated annealing algorithm in that it uses a constant (rather than decreasing) temperature. We consider two approaches for estimating the optimal solution. The first approach uses the number of visits the algorithm makes to the different states (divided by a normalizer) to estimate the optimal solution. The second approach uses the state that has the best average estimated objective function value as estimate of the optimal solution. We show that both variants of our method are guaranteed to converge almost surely to the set of global optimal solutions, and discuss how our work applies in the discrete deterministic optimization setting. We also show how both variants can be applied for solving discrete optimization problems when the objective function values are estimated using either transient or steady-state simulation. Finally, we include some encouraging numerical results documenting the behavior of the two variants of our algorithm when applied for solving two versions of a particular discrete stochastic optimization problem, and compare their performance with that of other variants of the simulated annealing algorithm designed for solving discrete stochastic optimization problems. [ABSTRACT FROM AUTHOR]

Generically, ejection chains are methods conceived to allow solution transformations to be efficiently carried out by modifying a variable number of their components at each step of a local search algorithm. We consider a subpath ejection chain method for the vehicle routing problem (VRP) under capacity and route length restrictions. The method undertakes the identification of a substructure named the flower reference structure which, besides coordinating moves during an ejection chain construction, allows the creation of neighborhood structures with interesting combinatorial characteristics. Specifically, we base the method on a fundamental property of creating alternating paths and cycles during an ejection chain construction. A new algorithm based on a Tabu search framework is proposed, and computational results on a set of academic and real-world problems indicate that the algorithm may be a good alternative to the best heuristic algorithms for the VRP. [ABSTRACT FROM AUTHOR]

This article studies the mean cost cyclical game in a more general setting than that in the study by V.A. Gurvich and colleagues, and A.V. Karzanow and V.N. Lebedev. The game is played on a directed graph and generalizes the single source shortest path problem, the minimum mean cycle problem, and the ergodic extension of matrix games. The article proves the existence of a solution in uniform stationary strategies and present an algorithm for finding such optimal strategies. Let G = (V,E) be a directed graph with vertex set V containing v vertices and arc set E containing m arcs. It is assumed that G may have loops but has no multiple arcs and dead ends, i.e., vertices without leaving arcs. These assumptions are introduced for notational convenience only. F(v) may be exponentially large in d(v). In interesting applications, however, F(v) is usually described combinatorially and can be given by use of an efficient membership procedure, e.g., when F(v) is given by a system of linear inequalities. The players have complete information about all moves and the game lasts infinitely long. The payoff function f(c,P) depends on the cost function.

We study echelon-stock (R, nQ) policies in a multistage, serial inventory system with compound Poisson demand. We provide a simple method for determining near-optimal control parameters. This is achieved in two steps. First, we establish lower and upper bounds on the cost function by over- and under-charging a penalty cost to each upstream stage for holding inadequate stock. Second, we minimize the bounds, which are simple, separable functions of the control parameters, to obtain heuristic solutions. We also provide an algorithm that guarantees an optimal solution at the expense of additional computational effort. A numerical study suggests that the heuristic solutions are easy to compute (even for systems with many stages) and are close to optimal. It also suggests that a traditional approach for determining the order quantities can be seriously suboptimal. All the results can be easily extended to the discrete-time case with independent, identically distributed demands. [ABSTRACT FROM AUTHOR]

D.-c. programming is a recent technique of global optimization that allows the solution of problems whose objective function and constraints can be expressed as differences of convex (i.e., d.-c.) functions. Many such problems arise in continuous location theory. The problem first considered is to locate a known number of source facilities to minimize the sum of weighted Euclidean distances between a user's fixed location and the source facility closest to the location of each user. We also apply d.-c. programming to the solution of the conditional Weber problem, an extension of the multisource Weber Problem, in which some facilities are assumed to be already established. In addition, we consider a generalization of Weber's problem, the facility location problem with limited distances, where the effective service distance becomes a constant when the actual distance attains a given value. Computational results are reported for problems with up to 10,000 users and two new facilities, 50 users and three new facilities, 1,000 users, 20 existing facilities and one new facility or 200 users, 10 existing and two new facilities. [ABSTRACT FROM AUTHOR]

Hit-and-Run algorithms are Monte Carlo procedures for generating points that are asymptotically distributed according to general absolutely continuous target distributions G over open bounded regions S. Applications include nonredundant constraint identification, global optimization, and Monte Carlo integration. These algorithms are reversible random walks that commonly incorporate uniformly distributed step directions. We investigate nonuniform direction choice and show that, under regularity conditions on the region S and target distribution G, there exists a unique direction choice distribution, characterized by necessary and sufficient conditions depending on S and G, which optimizes the Doob bound on rate of convergence. We include computational results demonstrating greatly accelerated convergence for this optimizing direction choice as well as for more easily implemented adaptive heuristic rules. [ABSTRACT FROM AUTHOR]