Tree-search algorithms for quadratic assignment problems

Problems having the mathematical structure of a quadratic assignment problem are found in a diversity of contexts: by the economist in assigning a number of plants or indivisible operations to a number of different geographical locations; by the architect or indusatrial engineer in laying out activities, offices, or departments in a building; by the human engineer in arranging the indicators and controls in an operators control room; by the electronics engineer in laying out components on a backboard; by the computer systems engineer in arranging information in drum and disc storage; by the production scheduler in sequencing work through a production facility; and so on. In this paper we discuss several types of algorithms for solving such problems, presenting a unifying framework for some of the existing algorithms, and dcscribing some new algorithms. All of the algorithms discussed proceed first to a feasible solution and then to better and better feasible solutions, until ultimately one is discovered which is shown to be optimal.     

A tactical warfare simulation program

The Tactical Warfare Simulation Program is a procedure by which the major interactions among opposing military units and terrain features can be treated in a tactical limited warfare situation. It is a critical-area, sequence-of-event model and is programmed in SIM-SCRIPT. In this program a military unit is described by such properties as strength, size, location, velocity, and attrition rates. Some of the events which can occur to a military unit are entering/leaving terrain features, becoming engaged/disengaged with opposing units, retreating, reaching an objective, and breaking. Following a discussion of the general features of the program, a study of a hypothetical war is presented.     

A note on duality in homogeneous fractional programming

For a linear fractional programming problem, Sharma and Swarup have constructed a dual problem, also a linear fractional program, in which the objective functions of both primal and dual problems are the same. Craven and Mond have extended this result to a nonlinear fractional programming problem with linear constraints, and a dual problem for which the objective function is the same as that of the primal. This theorem is now further extended from linear to differentiable convex constraints.     

The mixed ordering policy in periodic review stochastic multi-commodity inventory systems

In multi-commodity inventory systems with variable setup costs, the mixed ordering policy assumes that commodities may be ordered either individually, or may be arbitrarily grouped for joint ordering. Thus, for a two-commodity system, commodity one or commodity two or commodities one and two may be ordered incurring respectively fixed order costs of K, K₁, or K₂, where max (K₁, K₂) ≤ K ≤ K₁ + K₂, This paper considers a two-commodity periodic review system. The stationary characteristics of the system are analyzed, and, for a special case, explicit solutions are obtained for the distribution of the stock levels at the beginning of the periods. In a numerical example, optimal policy variables are computed, and the mixed ordering policy is compared with individual and joint ordering policies.     

Constructing bimatrix games with special properties

This work is concerned primarily with presenting techniques for constructing bimatrix games with predetermined equilibrium points. Some partial results on Nash-solvability are also given.     

Satellite constellation design for forest fire monitoring via a stochastic programing approach

There is significant value in the data collected by satellites during and after a natural disaster. The current operating paradigm in practice is for satellites to passively collect data when they happen to fly over a disaster location. Conversely, this article considers the alternative approach of actively maneuvering satellites to fly directly overhead of the disaster site on a routine basis. Toward this end, we seek to compute a satellite constellation design that minimizes the expected maneuver costs for monitoring an unknown forest fire. In this article, we present a 2‐stage stochastic programing model for this problem as well as a accelerated L‐shaped decomposition approach. A comparison between our approach and the current operating paradigm indicates that our solution provides longer duration data collections and a greater number of data collections. Analysis also shows that our proposed solution is robust over a wide array of scenarios.