An analysis of degeneracy

Degeneracy in linear programming models has been analyzed for its impacts on algorithmic properties. A complementary analysis here is on what the solutions mean. The framework presented is couched in marginal sensitivity analysis, introducing concepts of “compatible bases” and “transition graphs”.     

The interactive fixed charge linear programming problem

In many decision-making situations, each activity that can be undertaken may have associated with it both a fixed and a variable cost. Recently, we have encountered serveral practical problems in which the fixed cost of undertaking an activity depends upon which other activities are also undertaken. To our knowledge, no existing optimization model can accomodate such a fixed cost structure. To do so, we have therefore developed a new model called the interactive fixed charge linear programming problem (IFCLP). In this paper we present and motivate problem (IFCLP), study some of its characteristics, and present a finite branch and bound algorithm for solving it. We also discuss the main properties of this algorithm.     

Single server queues with hyperexponential service times

Single server queues with hyperexponential service times are studied. Explicit expressions are derived for the waiting time and state distributions.     

An Imperfect Jewel: Military Theory and the Military Profession

This article explores a perennial theme in the literature of strategic studies: the relationship between military theory and the military profession. It begins with a conceptual analysis of this relationship. It then investigates what military theorists themselves have had to say about the utility of their craft. It concludes by assessing the actual influence of military theory on selected individuals and institutions. The individuals are George S. Patton, Jr., and Ulysses S. Grant. The institutions are the United States Army and the United States Air Force in the late twentieth century. The fundamental finding is suggested in the title: military theory can indeed be quite useful in the maturation of military commanders and in the development of martial institutions, but it is not always necessary and by no means perfect. It should thus be studied assiduously but used with caution.     

Maximizing the ratio of two convex functions over a convex set

The purpose of this article is to present an algorithm for globally maximizing the ratio of two convex functions f and g over a convex set X. To our knowledge, this is the first algorithm to be proposed for globally solving this problem. The algorithm uses a branch and bound search to guarantee that a global optimal solution is found. While it does not require the functions f and g to be differentiable, it does require that subgradients of g can be calculated efficiently. The main computational effort of the algorithm involves solving a sequence of subproblems that can be solved by convex programming methods. When X is polyhedral, these subproblems can be solved by linear programming procedures. Because of these properties, the algorithm offers a potentially attractive means for globally maximizing ratios of convex functions over convex sets. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

An approximation for the waiting time distribution in single server queues

Single server queues with general interarrival and service times are approximated by queues with two-point (Bernoulli) interarrival times and exponential service times. The parameters are chosen such that the first four moments of the difference of the service times and interarrival times in the approximating system equal those of the original system. The aptness of the approximation is discussed and some examples are presented comparing the exact and approximate waiting time distributions. A more complicated approximation is presented using the dual system (exponential arrivals, Bernoulli service) for those cases where the original approximation cannot be used.     

Facing an uncertain economic future: Environmental management spending and rural regions surrounding the U.S. DOE's nuclear weapons facilities

Using an economic simulation model, the study finds that the proposed expenditure by the U.S. Department of Energy of billions of dollars to manage the nuclear weapons environmental legacy followed by sharp reductions in expenditures would cause economic spikes and then depressions in three rural regions (Hanford in Washington, INEEL in Idaho, and SRS in South Carolina). The economies of larger and growing metropolitan regions with DOE sites will not be noticeably impacted. Simulations suggest pronounced impacts on income, jobs, and gross regional product in the three dependent rural regions. Policy options are reviewed to address the economic stresses of these rural dependent regions.     

Concave envelopes of monomial functions over rectangles

The construction of convex and concave envelopes of real‐valued functions has been of interest in mathematical programming for over 3 decades. Much of this interest stems from the fact that convex and concave envelopes can play important roles in algorithms for solving various discrete and continuous global optimization problems. In this article, we use a simplicial subdivision tool to present and validate the formula for the concave envelope of a monomial function over a rectangle. Potential algorithmic applications of this formula are briefly indicated. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.