An exact aggregation/disaggregation algorithm for large scale markov chains

Many Markov chain models have very large state spaces, making the computation of stationary probabilities very difficult. Often the structure and numerical properties of the Markov chain allows for more efficient computation through state aggregation and disaggregation. In this article we develop an efficient exact single pass aggregation/disaggregation algorithm which exploits structural properties of large finite irreducible mandatory set decomposable Markov chains. The required property of being of mandatory set decomposable structure is a generalization of several other Markov chain structures for which exact aggregation/disaggregation algorithms exist. © 1995 John Wiley & Sons, Inc.     

Algorithms for the design of finite-capacity service units

Finite-capacity queues arise naturally in many practical situations, notably in communications and manufacturing engineering. In this article, the matrix formalism of probability distributions of phase type is used to develop fast algorithms to compute various steady-state distributions for the finite-capacity PH/PH/1 queue. This algorithm is an important ingredient in solving nontraditional but significant design problems. Some of these are described as illustrative examples.     

New worst-case results for the bin-packing problem

In this note we consider the familiar bin-packing problem and provide new worst-case results for a number of classical heuristics. We show that the first-fit and best-fit heuristics have an absolute performance ratio of no more than 1.75, and first-fit decreasing and best-fit decreasing heuristics have an absolute performance ratio of 1.5. The latter is the best possible absolute performance ratio for the bin-packing problem, unless P = NP. © 1994 John Wiley & Sons, Inc.     

Multilateral defense cooperation in the Indo-Asia-Pacific region: Tentative steps toward a regional NATO?

Some U.S. military leaders have asserted that the United States, Japan, Australia, and India and the Republic of Korea are developing multilateral defense cooperation to deter aggression and uphold norms much like North Atlantic Treaty Organization (NATO) has in Europe. Frequent military exercises and China’s threats to freedom of navigation (FoN) and North Korea’s nuclear missiles comprise the motive force for such cooperation. However, cooperation thus far has been trilateral and minimal, given divergent national interests and dispersed geopolitical locations. Cooperation among Japan, Republic of Korea (ROK), and the United States is increasing given the threat, but ROK’s public opinion is divided about Japan. Australia, Japan, and India have increased cooperation with the United States but are reluctant to conduct FoN operations with the United States to challenge China’s expansionism in the South China Sea. If China becomes more aggressive and blocks FoN or seizes territory, development toward an Asian NATO is possible.     

Honour,Comradeship and Betrayal: Lord Capel’s Sword

The sword which is the subject of this article and which will be referred to as the Capel sword, is a fine example of what has become known as an Irish basket-hilt. Whilst there are other examples in existence, what makes this sword unique and particularly important is the fact that it is known to have been owned by two important Royalist military leaders, Lord Arthur Capel and Sir John Owen. These two extraordinary men came from different backgrounds but their fate was linked through circumstances beyond their control. The story this sword tells is one of comradeship, loyalty, total belief in a cause, betrayal and ultimate sacrifice.     

A learning tabu search for a truck allocation problem with linear and nonlinear cost components

The two‐level problem studied in this article consists of optimizing the refueling costs of a fleet of locomotives over a railway network. The goal consists of determining: (1) the number of refueling trucks contracted for each yard (truck assignment problem denoted TAP) and (2) the refueling plan of each locomotive (fuel distribution problem denoted FDP). As the FDP can be solved efficiently with existing methods, the focus is put on the TAP only. In a first version of the problem (denoted (P1)), various linear costs (e.g., fuel, fixed cost associated with each refueling, weekly operating costs of trucks) have to be minimized while satisfying a set of constraints (e.g., limited capacities of the locomotives and the trucks). In contrast with the existing literature on this problem, two types of nonlinear cost components will also be considered, based on the following ideas: (1) if several trucks from the same fuel supplier are contracted for the same yard, the supplier is likely to propose discounted prices for that yard (Problem (P2)); (2) if a train stops too often on its route, a penalty is incurred, which represents the dissatisfaction of the clients (Problem (P3)). Even if exact methods based on a mixed integer linear program formulation are available for (P1), they are not appropriate anymore to tackle (P2) and (P3). Various methods are proposed for the TAP: a descent local search, a tabu search, and a learning tabu search (LTS). The latter is a new type of local search algorithm. It involves a learning process relying on a trail system, and it can be applied to any combinatorial optimization problem. Results are reported and discussed for a large set of instances (for (P1), (P2), and (P3)), and show the good performance of LTS. © 2014 Wiley Periodicals, Inc. 62:32–45, 2015     

A two product dynamic economic lot size production model with either-or production constraints

This paper considers the production of two products with known demands over a finite set of periods. The production and inventory carrying costs for each product are assumed to be concave. We seek the minimum cost production schedule meeting all demands, without backlogging, assuming that at most one of the two products can be produced in any period. The optimization problem is first stated as a nonlinear programming problem, which allows the proof of a result permitting the search for the optimal policy to be restricted to those which produce a product only when its inventory level is zero. A dynamic programming formulation is given and the model is then formulated as a shortest route problem in a specially constructed network.