An algorithm for separable piecewise convex programming problems

We present a branch and bound algorithm to solve mathematical programming problems of the form: Find x =|(x₁,…x_n) to minimize Σ?_i0(x₁) subject to x?G, l≦x≦L and Σ?_i0(x₁)≦0, j=1,…,m. With l=(l₁,…,l_n) and L=(L₁,…,L_n), each ?_ij is assumed to be lower aemicontinuous and piecewise convex on the finite interval [l_i.L_i]. G is assumed to be a closed convex set. The algorithm solves a finite sequence of convex programming problems; these correspond to successive partitions of the set C={x|l ≦ x ≦L} on the bahis of the piecewise convexity of the problem functions ?_ij. Computational considerations are discussed, and an illustrative example is presented.     

Transportation problems with some xij negative and transshipment problems

The general solution process of the Hitchcock transportation problem resulting from the application of the method of reduced matrices may give solutions with some negative x_ij values. This paper is devoted to a review of the reduced matrices method, an examination of suitable interpretation of sets of x_ij which include some negative values, and ways of interpreting these values in useful modifications of the Hitchcock problem. Such modifications include a) the reshipment problem, b) the overshipment problem, and c) the transshipment problem. Techniques are developed for determining and eliminating c_ij which are not optimal. These techniques and results are useful in solving the problems indicated above. The natural applicability of the simple and general method of reduced matrices is emphasized.     

A note on a stochastic production-maximizing transportation problem

A stochastic production-maximizing problem with transportation constraints is considered where the production rates, R_ij, of man i — job j combinations are random variables rather than constants. It is shown that for the family of Weibull distributions (of which the Exponential is a special case) with scale parameters λ_ij and shape parameter β, the plan that maximizes the expected rate of the entire line is obtained by solving a deterministic fixed charge transportation problem with no linear costs and with “set-up” cost matrix ‖λ_ij‖.     

Algorithms for minimizing total cost,bottleneck time and bottleneck shipment in transportation problems

We consider the transportation problem of determining nonnegative shipments from a set of m warehouses with given availabilities to a set of n markets with given requirements. Three objectives are defined for each solution: (i) total cost, TC, (ii) bottleneck time, BT (i.e., maximum transportation time for a positive shipment), and (iii) bottleneck shipment, SB (i.e., total shipment over routes with bottleneck time). An algorithm is given for determining all efficient (pareto-optimal or nondominated) (TC, BT) solution pairs. The special case of this algorithm when all the unit cost coefficients are zero is shown to be the same as the algorithms for minimizing BT. provided by Szwarc and Hammer. This algorithm for minimizing BT is shown to be computationally superior. Transportation or assignment problems with m=n=100 average about a second on the UNIVAC 1108 computer (FORTRAN V)) to the threshold algorithm for minimizing BT. The algorithm is then extended to provide not only all the efficient (TC, BT) solution pairs but also, for each such BT, all the efficient (TC, SB) solution pairs. The algorithms are based on the cost operator theory of parametric programming for the transportation problem developed by the authors.     

The transportation paradox

A paradox arises when a transportation problem admits to a total cost solution which is lower than the optimum and is attainable by shipping larger quantities of goods over the same routes that were previously designated as optimal. That is, falling total costs are present in moving to the greater shipment quantities. Necessary conditions for this to occur are established and an algorithm for solving this expanded transportation problem is supplied.     

Instant transportation solutions

This paper presents direct noniterative methods for solving such known problems as shoploading and aggregate scheduling. There is given a simple optimal rule for the shop-loading problem which is quite surprising. The crucial point in solving this problem is what not to assign rather than what to assign. The development of those methods was possible since the discussed problems can be converted into a special transportation model where the given cost coefficients c_ij assume a form cij = ui + uj.     

A transportation problem with competition

The classic transportation problem can be generalized with many carriers and one owner. From the formulation the competition in sense of game theory naturally appears. Here we present and solve this problem using a generalized n-person game. Besides the same composition properties about solutions and regarding zones, related results are considered. Finally, the problem in which there is a modification of the set of destinations assigned to the carriers is also studied.     

Scheduling with earliest start and due date constraints on multiple machines

We consider the scheduling of n jobs on m identical machines when the jobs become available for processing at ready times a_i, a_i, ? 0, require d_i time units for processing and must be completed by times b_i for i = 1, 2, … n. The objective chosen is that of minimizing the total elapsed time to complete all jobs subject to the ready time and due date constraints, preemption is not allowed. We present a multi-stage solution algorithm for this problem that is based on an implicit enumeration procedure and also uses the labelling type algorithm which solves the problem when preemption is allowed.     

Adaptive competitive decision in repeated play of a matrix game with uncertain entries

This study is concerned with a game model involving repeated play of a matrix game with unknown entries; it is a two-person, zero-sum, infinite game of perfect recall. The entries of the matrix ((pij)) are selected according to a joint probability distribution known by both players and this unknown matrix is played repeatedly. If the pure strategy pair (i, j) is employed on day k, k = 1, 2, …, the maximizing player receives a discounted income of β^{k - 1} X_ij, where β is a constant, 0 ≤ β ? 1, and X_ij assumes the value one with probability p_ij or the value zero with probability 1 - p_ij. After each trial, the players are informed of the triple (i, j, X_ij) and retain this knowledge. The payoff to the maximizing player is the expected total discounted income. It is shown that a solution exists, the value being characterized as the unique solution of a functional equation and optimal strategies consisting of locally optimal play in an auxiliary matrix determined by the past history. A definition of an ?-learning strategy pair is formulated and a theorem obtained exhibiting ?-optimal strategies which are ?-learning. The asymptotic behavior of the value is obtained as the discount tends to one.     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

Weighted vertex packing problem for specially structured geometric graphs

Consider a set of vertices V = {1, 2,…, n} placed on a two-dimensional Euclidean plane R² with each vertex attached a nonnegative weight w: V → R. For a given constant d>0, the geometric graph G = (V, E) is defined to have edge set E = {(i, j): d_ij ⩽ d} with d_ij being the Euclidean distance between vertices i and j. The geometric vertex packing (GVP) problem, which is often called the independent set problem, is defined as selecting the set of pairwise nonadjacent vertices with maximum total weight. We limit our attention to the special case that no vertex is within a distance βd of any other vertices where 0 ⩽ β < 1. A special value of β (= 1/2) is referred to frequently because of its correspondence to a manufacturing problem in circuit board testing. In this article we show that the weighted vertex packing problem for the specially structured geometric graph (SGVP) defined with the above restriction is NP-complete even for the case that all vertex weights are unity and for any β. Polynomial procedures have been designed for generating cuts to obtain tight LP upper bounds for the SGVP. Two heuristics with bounded worst-case performance are applied to the LP solution to produce a feasible solution and a lower bound. We then use a branch-and-bound procedure to solve the problem to optimality. Computational results on large-scale SGVP problems will be discussed. © 1995 John Wiley & Sons, Inc.     

Determining optimal growth paths in logistics operations

This paper considers a logistics system modelled as a transportation problem with a linear cost structure and lower bounds on supply from each origin and to each destination. We provide an algorithm for obtaining the growth path of such a system, i. e., determining the optimum shipment patterns and supply levels from origins and to destinations, when the total volume handled in the system is increased. Extensions of the procedure for the case when the costs of supplying are convex and piecewise linear and for solving transportation problems that are not in “standard form” are discussed. A procedure is provided for determining optimal plant capacities when the market requirements have prespecified growth rates. A goal programming growth model where the minimum requirements are treated as goals rather than as absolute requirements is also formulated.     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

Solution of minisum and minimax location–allocation problems with Euclidean distances

A new method for the solution of minimax and minisum location–allocation problems with Euclidean distances is suggested. The method is based on providing differentiable approximations to the objective functions. Thus, if we would like to locate m service facilities with respect to n given demand points, we have to minimize a nonlinear unconstrained function in the 2m variables x₁,y₁, ?,x_m,y_m. This has been done very efficiently using a quasi-Newton method. Since both the original problems and their approximations are neither convex nor concave, the solutions attained may be only local minima. Quite surprisingly, for small problems of locating two or three service points, the global minimum was reached even when the initial position was far from the final result. In both the minisum and minimax cases, large problems of locating 10 service facilities among 100 demand points have been solved. The minima reached in these problems are only local, which is seen by having different solutions for different initial guesses. For practical purposes, one can take different initial positions and choose the final result with best values of the objective function. The likelihood of the best results obtained for these large problems to be close to the global minimum is discussed. We also discuss the possibility of extending the method to cases in which the costs are not necessarily proportional to the Euclidean distances but may be more general functions of the demand and service points coordinates. The method also can be extended easily to similar three-dimensional problems.     

minimax问题的广义共轭向量法

本文按照共轭向量法的理论,针对非奇异对称矩阵提出了广义共轭向量的概念,并论述了它的三个重要性质(线性独立性、可寻驻点和可扩展性)。在此基础上,构造了极小极大(minimax)问题的广义共轭向量法。理论分析表明,该算法具有二次终止性质,且在每一维搜索时具有确定的寻优特征(求极小或求极大)。该算法为用拉格朗日乘子法求解数学规划提供了一个可能的途径。计算实例表明该算法是有效的。     

Solving incremental quantity discounted transportation problems by vertex ranking

Logistics managers often encounter incremental quantity discounts when choosing the best transportation mode to use. This could occur when there is a choice of road, rail, or water modes to move freight from a set of supply points to various destinations. The selection of mode depends upon the amount to be moved and the costs, both continuous and fixed, associated with each mode. This can be modeled as a transportation problem with a piecewise-linear objective function. In this paper, we present a vertex ranking algorithm to solve the incremental quantity discounted transportation problem. Computational results for various test problems are presented and discussed.     

Minimax and maximin facility location problems on a sphere

The problem dealt with in this article is as follows. There are n “demand points” on a sphere. Each demand point has a weight which is a positive constant. A facility must be located so that the maximum of the weighted distances (distances are the shortest arcs on the surface of the sphere) is minimized; this is called the minimax problem. Alternatively, in the maximin problem, the minimum weighted distance is maximized. A setup cost associated with each demand point may be added for generality. It is shown that any maximin problem can be reparametrized into a minimax problem. A method for finding local minimax points is described and conditions under which these are global are derived. Finally, an efficient algorithm for finding the global minimax point is constructed.     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

Technical note: Finite-time regret analysis of Kiefer-Wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand

We consider the problem of nonparametric multi-product dynamic pricing with unknown demand and show that the problem may be formulated as an online model-free stochastic program, which can be solved by the classical Kiefer-Wolfowitz stochastic approximation (KWSA) algorithm. We prove that the expected cumulative regret of the KWSA algorithm is bounded above by where κ₁, κ₂ are positive constants and T is the number of periods for any T = 1, 2, … . Therefore, the regret of the KWSA algorithm grows in the order of , which achieves the lower bounds known for parametric dynamic pricing problems and shows that the nonparametric problems are not necessarily more difficult to solve than the parametric ones. Numerical experiments further demonstrate the effectiveness and efficiency of our proposed KW pricing policy by comparing with some pricing policies in the literature.     

An extension of the (szwarc) truck assignment problem

In this journal in 1967. Szware presented an algorithm for the optimal routing of a common vehicle fleet between m sources and n sinks with p different types of commodities. The main premise of the formulation is that a truck may carry only one commodity at a time and must deliver the entire load to one demand area. This eliminates the problem of routing vehicles between sources or between sinks and limits the problem to the routing of loaded trucks between sources and sinks and empty trucks making the return trip. Szwarc considered only the transportation aspect of the problem (i. e., no intermediate points) and presented a very efficient algorithm for solution of the case he described. If the total supply is greater than the total demand, Szwarc shows that the problem is equivalent to a (mp + n) by (np + m) Hitchcock transportation problem. Digital computer codes for this algorithm require rapid access storage for a matrix of size (mp + n) by (np + m); therefore, computer storage required grows proportionally to p². This paper offers an extension of his work to a more general form: a transshipment network with capacity constraints on all arcs and facilities. The problem is shown to be solvable directly by Fulkerson's out-of-kilter algorithm. Digital computer codes for this formulation require rapid access storage proportional to p instead of p². Computational results indicate that, in addition to handling the extensions, the out-of-kilter algorithm is more efficient in the solution of the original problem when there is a mad, rate number of commodities and a computer of limited storage capacity.