Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

An extreme-point approach for obtaining weighted ratings in qualitative multicriteria decision making

Many attempts have been made in the past to obtain estimates for the weights and ratings values of a multicriteria linear utility function. In particular, the problem arises when both criteria importance and alternatives' ratings are expressed in a qualitative ordinal manner. This article proposes an extreme-point approach for obtaining the overall ratings in the presence of ordinal preferences both for the criteria importance and the alternatives' rankings. In particular it is shown that Borda's method of scores is obtained as a special case. © 1996 John Wiley & Sons, Inc.     

Interactive multicriteria linear programming: An extension of the method of Zionts and Wallenius

This article presents an extension of the interactive multicriteria linear-programming method of Zionts and Wallenius [see Management Science, 29 (5) (1983)]. The decision maker's underlying utility function is assumed to be pseudoconcave, and his preference structure is assessed through pairwise comparison questions. In the method of Zionts and Wallenius, the decision maker's preference structure is represented as constraints on the weights on the objectives derived from his responses. This representation is only a linear approximation to the underlying nonlinear utility function. Accordingly, inconsistency among the constraints on the weights arises while solving the problem. Therefore, some of the constraints have to be dropped, resulting in a loss of information on the preference structure, and hence an increase in the total number of questions. In this article we develop a hybrid representation scheme to avoid this problem. The proposed scheme is implemented within the algorithmic framework of the method of Zionts and Wallenius, and its underlying theory is developed. Computational results show that the number of questions required by the Zionts and Wallenius method can be sinificantly reduced using the proposed scheme.     

Dominating sets for rectilinear center location problems with polyhedral barriers

In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems are important since they model various actual applications. The resulting mathematical models have a nonconvex objective function and are therefore difficult to tackle using standard methods of location theory even in the case of simple barrier shapes and distance functions. For the case of center objectives with barrier distances obtained from the rectilinear or Manhattan metric, it is shown that the problem can be solved in polynomial time by identifying a dominating set. The resulting genuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connected restricted location and network location problems. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 647–665, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10038     

Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine

This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed‐integer linear programming formulation. By relaxing some constraints, a Lagrangean relaxation algorithm is designed which gives both lower and upper bounds. The special case where jobs have equal weights is analyzed. Computational results are presented and, although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 50: 2003     

Dynamic learning,pricing, and ordering by a censored newsvendor

We address the problem of determining optimal ordering and pricing policies in a finite‐horizon newsvendor model with unobservable lost sales. The demand distribution is price‐dependent and involves unknown parameters. We consider both the cases of perishable and nonperishable inventory. A very general class of demand functions is studied in this paper. We derive the optimal ordering and pricing policies as unique functions of the stocking factor (which is a linear transformation of the safety factor). An important expression is obtained for the marginal expected value of information. As a consequence, we show when lost sales are unobservable, with perishable inventory the optimal stocking factor is always at least as large as the one given by the single‐period model; however, if inventory is nonperishable, this result holds only under a strong condition. This expression also helps to explain why the optimal stocking factor of a period may not increase with the length of the problem. We compare this behavior with that of a full information model. We further examine the implications of the results to the special cases when demand uncertainty is described by additive and multiplicative models. For the additive case, we show that if demand is censored, the optimal policy is to order more as well as charge higher retail prices when compared to the policies in the single‐period model and the full information model. We also compare the optimal and myopic policies for the additive and multiplicative models. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Analytic solution for the nucleolus of a three‐player cooperative game

The nucleolus solution for cooperative games in characteristic function form is usually computed numerically by solving a sequence of linear programing (LP) problems, or by solving a single, but very large‐scale, LP problem. This article proposes an algebraic method to compute the nucleolus solution analytically (i.e., in closed‐form) for a three‐player cooperative game in characteristic function form. We first consider cooperative games with empty core and derive a formula to compute the nucleolus solution. Next, we examine cooperative games with nonempty core and calculate the nucleolus solution analytically for five possible cases arising from the relationship among the value functions of different coalitions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

A note on “resource flexibility with responsive pricing”

We revisit the capacity investment decision problem studied in the article “Resource Flexibility with Responsive Pricing” by Chod and Rudi [Operations Research 53, (2005) 532–548]. A monopolist firm producing two dependent (substitutable or complementary) products needs to determine the capacity of one flexible resource under demand risk so as to maximize its expected profit. Product demands are linear functions of the prices of both products, and the market potentials are random and correlated. We perform a comparative statics analysis on how demand variability and correlation impact the optimal capacity and the resulting expected profit. In particular, C&R study this problem under the following assumptions/approximations: (i) demand intercepts follow a bivariate Normal distribution; (ii) demand uncertainty is of an additive form; (iii) and under approximate expressions for the optimal capacity and optimal expected profit. We revisit Propositions 2, 3, 4, 5, and 10 of C&R without these assumptions and approximations, and show that these results continue to hold (i) for the exact expressions for the optimal expected profit and optimal capacity, and (ii) under any arbitrary continuous distribution of demand intercepts. However, we also show that the additive demand uncertainty is a critical assumption for the C&R results to hold. In particular, we provide a case of multiplicative uncertainty under which the C&R results (Propositions 2 and 3) fail. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

A graphical aid for sensitivity analysis of estimated regression coefficients

A problem often arising in applied linear regression modeling is determining the appropriate weight to attach to each observation. In the extreme, the problem extends to the deletion of observations from a data base. Since the choice of weights, fitting criteria, and estimation procedure depend on the specific objectives of the modeling, universally applicable guidelines are virtually nonexistent. However, the sensitivity of analytic conclusions to weights assigned to “suspect” observations can be conveniently assessed using a graphical display. This report develops such a display based on a modeling of outliers which leads naturally to estimators based on a weighted least-squares criterion, and a data-analytic method for determining how much downweighting to impose on a specific subset of observations. This technique is illustrated with several examples, including one relating air pollution to human mortality.     

Incorporation dynamic aspects and uncertainty in 1‐median location problems

In this paper we present several 1‐median formulations on a tree network which incorporate dynamic evolution and/or uncertainty of node demands and transportation costs over a planning horizon. Dynamic evolution is modeled using linear demand functions for the nodes and linear length functions for the edges. Uncertainty is modeled with the use of multiple scenarios, where a scenario is a complete specification of the uncertain node demands and/or edge lengths. We formulate our objective using minimax regret like criteria. We use two different criteria, namely, robust deviation and relative robustness. We discuss what motivated the introduction of these objectives, as well as their relation to existing literature and decision making practices. For all of the models presented, we provide low‐order polynomial time algorithms. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 147–168, 1999     

基于区间数的第4代战斗机空战效能评估

根据第4代战斗机所具有的典型特征,建立了第4代战斗机的空战效能评估指标体系。采用区间数特征向量法确定了效能评估指标体系中的各指标的权重,给出了定量指标和定性指标的规范化方法,提出了采用区间数形式的加权和关系进行效能指标聚合的方法。最后,通过实例验证了所建立的空战效能评估指标体系的合理,评估方法的有效、可行。     

Utility assessment procedures for polynomial-exponential functions

This article develops a methodology for testing constant exchange risk properties and identifying an appropriate form for a decision maker's utility function. These risk properties characterize six different utility functions which are sums of products of polynomials and exponential functions. Such functional forms are commonly used in decision analysis applications. The practical advantage of this methodology is that these constant exchange risk properties eliminate the usual arbitrariness in the selection of a parametric utility function and often reduce the data requirements for subsequent estimation. The procedure is straightforward to apply. The decision maker need only provide certainty equivalents for two-outcome gambles and determine the more-preferred gamble in paired comparisons. The technical details of the procedure can be handled by interactive computer software.     

The collection depots location problem on networks

In this paper we investigate the collection depots location problem on a network. A facility needs to be located to serve a set of customers. Each service consists of a trip to the customer, collecting materials, dropping the materials at one of the available collection depots and returning to the facility to wait for the next call. Two objectives are considered: minimizing the weighted sum of distances and minimizing the maximum distance. The properties of the solutions to these problems are described. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 15–24, 2002; DOI 10.1002/nav.10000     

Detection of a Markovian target with optimization of the search efforts under generalized linear constraints

This paper deals with search for a target following a Markovian movement or a conditionally deterministic motion. The problem is to allocate the search efforts, when search resources renew with generalized linear constraints. The model obtained is extended to resource mixing management. New optimality equations of de Guenin's style are obtained. Practically, the problem is solved by using an algorithm derived from the FAB method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 117–142, 2002; DOI 10.1002/nav.10009     

Markovian models of three‐on‐one combat involving a hidden defender

In this paper, Markovian models of three‐on‐one stochastic firefights between ground‐based weapon systems are developed. These models address a common scenario of interest to the military, but one which has been much neglected in analytic combat models, that of combat between a hidden defender and an exposed attacking force. Each combatant must detect an opponent before commencing their firing cycle, a task which is considerably more difficult for the attacker. In the models developed here, the defender detects the exposed attacking group after an exponentially distributed time interval, while each attacker has a fixed probability of detecting the defender via the flash signature produced after each shot fired by him. The utility of the approach is demonstrated by investigating what impact the introduction of a coordinated gun‐laying system for the attacking force might have, a system made possible by battlefield digitization. The method used here allows models to be developed incrementally. This and other advantages of the Markovian approach are discussed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 627–646, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10041     

Designing a screening experiment for highly reliable products

Within a reasonable life‐testing time, how to improve the reliability of highly reliable products is one of the great challenges to today's manufacturers. By using a resolution III experiment together with degradation test, Tseng, Hamada, and Chiao (1995) presented an interesting case study of improving the reliability of fluorescent lamps. However, in conducting such an experiment, they did not address the problem of how to choose the optimal settings of variables, such as sample size, inspection frequency, and termination time for each run, which are influential to the correct identification of significant factors and the experimental cost. Assuming that the product's degradation paths satisfy Wiener processes, this paper proposes a systematic approach to the aforementioned problem. First, an intuitively appealing identification rule is proposed. Next, under the constraints of a minimum probability of correct decision and a maximum probability of incorrect decision of the proposed identification rule, the optimum test plan (including the determinations of inspection frequency, sample size, and termination time for each run) can be obtained by minimizing the total experimental cost. An example is provided to illustrate the proposed method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 514–526, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10024     

Multiple-attribute decision making with partial information: The comparative hypervolume criterion

A new approach is presented for analyzing multiple-attribute decision problems in which the set of actions is finite and the utility function is additive. The problem can be resolved if the decision makers (or group of decision makers) specifies a set of nonnegative weights for the various attributes or criteria, but we here assume that the decision maker(s) cannot provide a numerical value for each such weight. Ordinal information about these weights is therefore obtained from the decision maker(s), and this information is translated into a set of linear constraints which restrict the values of the weights. These constraints are then used to construct a polytope W of feasible weight vectors, and the subsets H_i (polytopes) of W over which each action a_i has the greatest utility are determined. With the Comparative Hypervolume Criterion we calculate for each action the ratio of the hypervolume of H_i to the hypervolume of W and suggest the choice of an action with the largest such ratio. Justification of this choice criterion is given, and a computational method for accurately approximating the hypervolume ratios is described. A simple example is provided to evaluate the efficiency of a computer code developed to implement the method.     

Modeling and analysis of multiobjective lot splitting for N‐product M‐machine flowshop lines

Lot splitting is a new approach for improving productivity by dividing production lots into sublots. This approach enables accelerating production flow, reducing lead‐time and increasing the utilization of organization resources. Most of the lot splitting models in the literature have addressed a single objective problem, usually the makespan or flowtime objectives. Simultaneous minimization of these two objectives has rarely been addressed in the literature despite of its high relevancy to most industrial environments. This work aims at solving a multiobjective lot splitting problem for multiple products in a flowshop environment. Tight mixed‐integer linear programming (MILP) formulations for minimizing the makespan and flowtime are presented. Then, the MinMax solution, which takes both objectives into consideration, is defined and suggested as an alternative objective. By solving the MILP model, it was found that minimizing one objective results in an average loss of about 15% in the other objective. The MinMax solution, on the other hand, results in an average loss of 4.6% from the furthest objective and 2.5% from the closest objective. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Optimal service rates of a service facility with perishable inventory items

In this paper we optimally control service rates for an inventory system of service facilities with perishable products. We consider a finite capacity system where arrivals are Poisson‐distributed, lifetime of items have exponential distribution, and replenishment is instantaneous. We determine the service rates to be employed at each instant of time so that the long‐run expected cost rate is minimized for fixed maximum inventory level and capacity. The problem is modelled as a semi‐Markov decision problem. We establish the existence of a stationary optimal policy and we solve it by employing linear programming. Several numerical examples which provide insight to the behavior of the system are presented. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 464–482, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10021     

Determination of suppliers' optimal quantity discount schedules with heterogeneous buyers

Although the quantity discount problem has been extensively studied in the realm of a single supplier and a single buyer, it is not well understood when a supplier has many different buyers. This paper presents an analysis of a supplier's quantity discount decision when there are many buyers with different demand and cost structures. A common discrete all‐unit quantity discount schedule with many break points is used. After formulating the model, we first analyze buyers' responses to a general discrete quantity discount schedule. This analysis establishes a framework for a supplier to formulate his quantity discount decision. Under this framework, the supplier's optimal quantity discount schedule can be formulated and solved by a simple non‐linear programming model. The applicability of the model is discussed with an application for a large U.S. distribution network. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 46–59, 2002; DOI 10.1002/nav.1052