Catálogo de publicaciones - libros

Every student of linear programming is exposed to the Farkas lemma, either in its original form or as the duality theorem of linear programming. What most students don’t realize is just how ubiquitous the lemma is. I’ve managed to make a good living by simply trying to express problems in the form of linear inequalities and then examining the Farkas alternative. It stared with my dissertation (under Saul’s supervision) and continues even today. So I could think of no better gift on the occasion of Saul’s birthday than a compilation of some applications of the Farkas lemma. These applications have been pulled together from a variety of different sources.

In this work, we investigate parametric probing methods based on solution cardinality for set partitioning problems. The methods used are inspired by the early work of Gass and Saaty on the parametric solution to linear programs, as well as the later work of Joseph, Gass, and Bryson that examined the duality gap between the integer and relaxation solutions to general integer programming problems. Computational results are presented for a collection of set partitioning problems found in the literature.

Using a popular setup, in solving a linear programming problem one looks for a tableau of the problem that has no negative elements in the last column and no positive elements in the last row. We study a matrix whose ()-th entry counts the tableaux for such a problem (here taken to be totally nondegenerate) having negative elements in the last column and positive elements in the last row. It is shown that this matrix possesses a certain symmetry, which is described.

In this paper we discuss some applications of Gass & Saaty’s parametric programming procedure (GSP). This underutilized procedure is relevant to solution strategies for many problem types but is often not considered as a viable alternate approach. By demonstrating the utility of this procedure, we hope to attract other researchers to explore the use of as a solution approach for important problems in operations research, computer science, information systems, and other areas.

Consider a truck that visits households each day. The specific households (and their locations) vary slightly from one day to the next. In the noisy traveling salesman problem, we develop a rough (skeleton) route which can then be adapted and modified to accommodate the actual node locations that need to be visited from day to day. In this paper, we conduct extensive computational experiments on problems with = 100, 200, and 300 nodes in order to compare several heuristics for solving the noisy traveling salesman problem including a new method based on quad trees. We find that the quad tree approach generates high-quality results quickly.

The use of radio frequency identification (RFID) allows utility companies to read meters from a distance. Thus a meter reader need not visit every customer on his route, but only get within a certain radius of each customer. In finding an optimal route — one that minimizes the distance the meter reader travels while servicing each customer on his route — this notion of only needing to be close enough changes the meter reading problem from a standard Traveling Salesperson Problem (TSP) into a variant problem: Close Enough TSP (CETSP). As a project for a graduate course in network optimization various heuristics for finding near optimal CETSP solutions were developed by six groups of students. In this paper we survey the heuristics and provide results for a diverse set of sample cases.

Tarjan [] describes how depth first search can be used to identify Strongly Connected Components (SCC) of a directed graph in linear time. It is standard to study Tarjan’s SCC algorithm in most senior undergraduate or introductory graduate computer science algorithms courses. In this paper we introduce the concept of a (TSCC) of a directed graph. Loosely stated, a TSCC of a directed graph is (i) strongly connected, and (ii) remains strongly connected even if we require the deletion of arcs from the component, so that it does not contain a pair of (twin arcs are a pair of bidirected arcs () and () where the tail of one arc is the head of the other and vice versa). This structure has diverse applications, from the design of telecommunication networks [] to structural stability of buildings []. In this paper, we illustrate the relationship between 2-edge connected components of an undirected graph—obtained from the strongly connected components of a directed graph—and twinless strongly connected components. We use this relationship to develop a linear time algorithm to identify all the twinless strongly connected components of a directed graph. We then consider the augmentation problem, and based on the structural properties developed earlier, derive a linear time algorithm for the augmentation problem.

Despite the criticisms of Woolsey [] and others, the classical “EOQ” model of Inventory Theory remains useful, both pedagogically and as a stepping-stone towards more realistic variants. Prominent among these are: (a) the one in which stock-outs are permitted but penalized, and (b) the one in which deliveries are gradual (i.e., continuous) rather than instantaneous. Here we also deal with a variant containing both features, (a) and (b). (In addition, a less common variant is considered.) In the spirit of Harris’s original (1913) presentation, the use of calculus is avoided entirely. Instead, it is shown explicitly how all the variants can be solved by “reduction” to the basic model, which is in turn treated by using the simply-proved “base case” of the arithmetic-geometric mean inequality.

In this paper, we consider the problem of developing daily and weekly schedules for the employees at a Federal Express local sort facility. We define the key data components in this analysis, describe the work rules, present a mathematical programming formulation of the daily scheduling problem as an extension of a set partitioning problem, and present a simplification of the weekly scheduling problem. Although this paper describes a work in progress, this study has defined the key issues that will have to be considered when implementing the final system. This system has the potential to be used at hundreds of FedEx local sort facilities if the final testing of the final system is successful.

Stochastic activity networks (SANs) such as those arising in Project Evaluation Review Technique (PERT) and Critical Path Method (CPM) are an important classical set of models in operations research. We focus on sensitivity analysis for stochastic activity networks when Monte Carlo simulation is employed. After a brief aside reminiscing on Saul’s influence on the author’s career and on the simulation community, we review previous research for sensitivity analysis of simulated SANs, give a brief summary overview of the main approaches in stochastic gradient estimation, derive estimators using techniques not previously applied to this setting, and address some new problems not previously considered. We conclude with some thoughts on future research directions.