A forward network simplex algorithm for solving multiperiod network flow problems

An optimization model which is frequently used to assist decision makers in the areas of resource scheduling, planning, and distribution is the minimum cost multiperiod network flow problem. This model describes network structure decision-making problems over time. Such problems arise in the areas of production/distribution systems, economic planning, communication systems, material handling systems, traffic systems, railway systems, building evacuation systems, energy systems, as well as in many others. Although existing network solution techniques are efficient, there are still limitations to the size of problems that can be solved. To date, only a few researchers have taken the multiperiod structure into consideration in devising efficient solution methods. Standard network codes are usually used because of their availability and perceived efficiency. In this paper we discuss the development, implementation, and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method is a forward algorithm which exploits the natural decomposition of multiperiod network problems by limiting its pivoting activity. A forward algorithm is an approach to solving dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Such procedures are available for a large number of special structure models. Here we describe the specialization of the forward simplex method of Aronson, Morton, and Thompson to solving multiperiod network network flow problems. Computational results indicate that both the solution time and pivot count are linear in the number of periods. For standard network optimization codes, which do not exploit the multiperiod structure, the pivot count is linear in the number of periods; however, the solution time is quadratic.     

Forecasting Civil Conflict with Zero-Inflated Count Models

Advances in the study of civil war have led to the proliferation of event count data, and to a corresponding increase in the use of (zero-inflated) count models for the quantitative analysis of civil conflict events. Our ability to effectively use these techniques is met with two current limitations. First, researchers do not yet have a definitive answer as to whether zero-inflated count models are a verifiably better approach to civil conflict modeling than are ‘less assuming’ approaches such as negative binomial count models. Second, the accurate analysis of conflict-event counts with count models – zero-inflated or otherwise – is severely limited by the absence of an effective framework for the evaluation of predictive accuracy, which is an empirical approach that is of increasing importance to conflict modelers. This article rectifies both of these deficiencies. Specifically, this study presents count forecasting techniques for the evaluation and comparison of count models' predictive accuracies. Using these techniques alongside out-of-sample forecasts, it then definitively verifies – for the first time – that zero-inflated count models are superior to comparable non-inflated models for the study of intrastate conflict events.     

Technical note: A computationally efficient algorithm for undiscounted Markov decision processes with restricted observations

We present a computationally efficient procedure to determine control policies for an infinite horizon Markov Decision process with restricted observations. The optimal policy for the system with restricted observations is a function of the observation process and not the unobservable states of the system. Thus, the policy is stationary with respect to the partitioned state space. The algorithm we propose addresses the undiscounted average cost case. The algorithm combines a local search with a modified version of Howard's (Dynamic programming and Markov processes, MIT Press, Cambridge, MA, 1960) policy iteration method. We demonstrate empirically that the algorithm finds the optimal deterministic policy for over 96% of the problem instances generated. For large scale problem instances, we demonstrate that the average cost associated with the local optimal policy is lower than the average cost associated with an integer rounded policy produced by the algorithm of Serin and Kulkarni Math Methods Oper Res 61 (2005) 311–328. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

A model to design recreational boat mooring fields

This article develops a mathematical model and heuristic algorithm to design recreational boating mooring fields. The boating industry is important to the Florida economy, and boat storage is becoming a concern among those in the industry. The mooring field design problem is formulated to maximize the total number of boat feet moored in the mooring field. In the model, we allow two adjacent moorings to overlap, which introduces a risk that under certain conditions the boats on these moorings could contact each other. We identify the conditions when contact is possible and quantify the probability of contact. The mooring field design problem is formulated as a nonlinear mixed‐integer programming problem. To solve the problem, we decompose it into two separate models, a mooring radii assignment model and a mooring layout model, which are solved sequentially. The first is solved via exhaustive enumeration and the second via a depth‐first search algorithm. Two actual mooring fields are evaluated, and in both cases our model leads to better layouts than ones experts developed manually. The mooring field design model rationalizes the mooring field design and shows that in one case by increasing the risk from 0 to 1%, the mooring efficiency increases from 74.8% to 96.2%. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Sandwich approximation of univariate convex functions with an application to separable convex programming

In this article an algorithm for computing upper and lower ? approximations of a (implicitly or explicitly) given convex function h defined on an interval of length T is developed. The approximations can be obtained under weak assumptions on h (in particular, no differentiability), and the error decreases quadratically with the number of iterations. To reach an absolute accuracy of ? the number of iterations is bounded by

     

Minimizing flow time on a single machine with job classes and setup times

We examine the static sequencing problem of ordering the processing of jobs on a single machine so as to minimize the average weighted flow time. It is assumed that all jobs have zero ready times, and that the jobs are grouped into classes with the property that setup tasks are only required when processing switches from jobs of one class to jobs of another class. The time required for each setup task is given by the sum of a setdown time from the previous class and a setup time for the new class. We show that an algorithm presented in the literature for solving a special case of this problem gives suboptimal solutions. A number of properties of the optimal solution are derived, and their use in algorithms is evaluated. Computational results are presented for both a branch-and-bound procedure and a simpler depth-first search.