# Nelson A. Uhan

Associate Professor

Mathematics Department ■
United States Naval Academy

*at* usna *dot* edu

I am an associate professor in the Mathematics Department at the United States Naval Academy. At USNA, I teach a variety of courses, ranging from calculus to simulation modeling. My research interests include cooperative game theory, mechanism design, combinatorial optimization, and applications of these areas to scheduling, network interdiction, and logistics.

I received a PhD in operations research from MIT in June 2008, and an AB and SM in applied mathematics from Harvard University in June 2002. My mathematical genealogy can be found here. My Erdös number is 3 (P. Erdös → P. Hell → M. Mastrolilli).

## Teaching

### Courses taught

#### At USNA

**Naval Applications of Operations Research (SA475)**

Spring 2014, Spring 2015, Spring 2016

description website

#### At Purdue

**Operations Research - Optimization (IE 335)**

Fall 2008, Fall 2009, Spring 2010, Fall 2010, Spring 2011, Fall 2011, Spring 2012

description

### Students supervised

#### At Purdue

**Kan Fang**, PhD in industrial engineering, December 2013**Jikai Zou**, MS in industrial engineering, May 2013**Sindhura Balireddi**, MS in computer science, August 2010**Mohan Gopaladesikan**, MS in industrial engineering, August 2010

### POET

The POET Project (Purdue Optimization modeling Education Tool) aims to design and evaluate visual interactive educational tools for optimization modeling. The POET project is co-led by Rachael Kenney, Ji Soo Yi and myself. The project web site can be found here.

## Research

### Publications

#### Preprints

**Cost-sharing mechanism design for freight consolidation among small suppliers**

W. Zhang, N. A. Uhan, M. Dessouky, A. Toriello

Submitted, July 2016

abstract paper

*Abstract.*A fair cost allocation scheme is critical for forming and sustaining horizontal cooperation that leads to cost reductions. In order to incentivize suppliers to cooperate in freight consolidation, we design a cost-sharing mechanism to solve a cost allocation problem arising in freight consolidation among small suppliers: that is, suppliers whose total demand fits into one truckload. This cost-sharing mechanism determines the set of suppliers who will participate in the consolidation and their corresponding cost shares. We design this cost-sharing mechanism to ensure that every supplier is willing to reveal their preference truthfully and the total consolidation cost incurred is recovered by the allocated costs. Moreover, our analytical and numerical study shows that our cost-sharing mechanism often yields cost shares that maximize the social welfare of all the suppliers.

**Linear programming models: identifying common errors in college engineering students' work with complex word problems**

R. H. Kenney, T. An, S.-H. Kim, N. A. Uhan, J. S. Yi, A. Shamsul

Submitted, September 2015

abstract

*Abstract.*In linear programming, many students find modeling — translating a verbal description of a problem into a valid mathematical expression — difficult to learn. To better understand this, we examine the existing characteristics of college engineering students' errors across linear programming modeling word problems. We examined textbooks to identify the types of modeling problems typically found in introductory linear programming courses. We then developed a comprehensive set of tasks and analyzed students' work to create a taxonomy of the errors and issues that students exhibited. From our findings, we define four categories of identified error types: (1) decision variable errors, (2) variable relationship errors, (3) notation errors, and (4) form errors. This study contributes to the research by investigating students' work in an area of undergraduate mathematics that has not been heavily explored before. Findings suggest specific areas of focus for future work in helping students develop their understanding of linear programming models, and mathematical modeling in word problems in general.

**Multi-agent decentralized network interdiction games**

H. Sreekumaran, A. R. Hota, A. L. Liu, N. A. Uhan, S. Sundaram

Submitted, June 2015

abstract paper

*Abstract.*In this work, we introduce

*decentralized network interdiction games*, which model the interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on

*decentralized shortest path interdiction*(DSPI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries, who all attempt to traverse a common network. We first establish results regarding the existence of equilibria for DSPI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the DSPI games, which leads to a generalized Nash equilibrium problem (GNEP) with non-shared constraints. While such a problem is computationally challenging in general, we show that under continuous interdiction actions, a DSPI game can be formulated as a linear complementarity problem and solved by Lemke's algorithm. In addition, we present decentralized heuristic algorithms based on best response dynamics for games under both continuous and discrete interdiction strategies. Finally, we establish theoretical bounds on the worst-case efficiency loss of equilibria in DSPI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to empirically study the average-case efficiency loss.

#### Journal articles

**Dynamic linear programming games with risk-averse players**

A. Toriello, N. A. Uhan

*Mathematical Programming*, available online, July 2016

abstract paper

*Abstract.*Motivated by situations in which independent agents wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk measures. For this setting, we study the strong sequential core, a natural extension of the core to dynamic settings. We characterize the strong sequential core as the set of allocations that satisfy a particular finite set of inequalities that depend on an auxiliary optimization model, and then leverage this characterization to establish sufficient conditions for emptiness and non-emptiness. Qualitatively, whereas the strong sequential core is always non-empty when players are risk-neutral, our results indicate that cooperation in the presence of risk aversion is much more difficult. We illustrate this with an application to cooperative newsvendor games, where we find that cooperation is possible when it least benefits players, and may be impossible when it offers more benefit.

**Scheduling on a single machine under time-of-use tariffs**

K. Fang, N. A. Uhan, F. Zhao, J. W. Sutherland

*Annals of Operations Research*238(1): 199-227, 2016

abstract paper

*Abstract.*We consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under time-of-use electricity tariffs. For the uniform-speed case, in which all jobs have arbitrary power demands and must be processed at a single uniform speed, we prove that the non-preemptive version of this problem is inapproximable within a constant factor unless P = NP. On the other hand, when all the jobs have the same workload and the electricity prices follow a so-called pyramidal structure, we show that this problem can be solved in polynomial time. For the speed-scalable case, in which jobs can be processed at an arbitrary speed with a trade-off between speed and power demand, we show that the non-preemptive version of the problem is strongly NP-hard. We also present different approximation algorithms for this case, and test the computational performance of these approximation algorithms on randomly generated instances. In addition, for both the uniform-speed and speed-scaling cases, we show how to compute optimal schedules for the preemptive version of the problem in polynomial time.

**Stochastic linear programming games with concave preferences**

N. A. Uhan

*European Journal of Operational Research*243(2): 637-646, 2015

abstract paper

*Abstract.*We study stochastic linear programming games: a class of stochastic cooperative games whose payoffs under any realization of uncertainty are determined by a specially structured linear program. These games can model a variety of settings, including inventory centralization and cooperative network fortification. We focus on the core of these games under an allocation scheme that determines how payoffs are distributed before the uncertainty is realized, and allows for arbitrarily different distributions for each realization of the uncertainty. Assuming that each player's preferences over random payoffs are represented by a concave monetary utility functional, we prove that these games have a nonempty core. Furthermore, by establishing a connection between stochastic linear programming games, linear programming games and linear semi-infinite programming games, we show that an allocation in the core can be computed efficiently under some circumstances.

**Dynamic cost allocation for economic lot sizing games**

A. Toriello, N. A. Uhan

*Operations Research Letters*42(1) 82-84, 2014

abstract paper

*Abstract.*We consider a cooperative game defined by an economic lot sizing problem with concave ordering costs over a finite time horizon, in which each player faces demand for a single product in each period and coalitions can pool orders. We show how to compute a dynamic cost allocation in the strong sequential core of this game, i.e. an allocation over time that exactly distributes costs and is stable against coalitional defections at every period of the time horizon.

**The complexity of egalitarian mechanisms for linear programming games**

N. A. Uhan

*Operations Research Letters*42(1) 76-81, 2014

abstract paper

*Abstract.*We show that the most cost-efficient subset problem for linear programming games is NP-hard, and in fact inapproximable within a constant factor in polynomial time, unless P = NP. This in turn implies that computing the prices output by an egalitarian mechanism and computing a cost allocation in the equal split-off set for linear programming games is NP-hard.

**POETIC: interactive solutions to alleviate the reversal error in student-professor type problems**

S.-H. Kim, D. Phang, T. An, J. S. Yi, R. H. Kenney, N. A. Uhan

*International Journal of Human-Computer Studies*72(1) 12-22, 2014

abstract paper

*Abstract.*The reversal error — reversing the relationship between two variables in a mathematical word problem — is a long-standing issue in mathematics education, despite its apparent simplicity. In this paper, we describe and study POETIC, an interactive web-based environment we developed to teach users to avoid the reversal error. POETIC uses two types of novel interactive visualization, which we call the Test-Case and Room-Metaphor approaches. To verify the effectiveness of these approaches, we conducted crowdsourcing-based comparison studies with 200 participants and found that both the Test-Case and Room-Metaphor approaches significantly decreased the frequency of reversal errors for certain types of word problems. Our results show that interactive visualization of equations can reduce the occurrence of the reversal error.

**On traveling salesman games with asymmetric costs**

A. Toriello, N. A. Uhan

*Operations Research*61(6) 1429-1434, 2013

abstract paper

*Abstract.*We consider cooperative traveling salesman games with non-negative asymmetric costs satisfying the triangle inequality. We construct a stable cost allocation with budget balance guarantee equal to the Held-Karp integrality gap for the asymmetric traveling salesman problem, using the parsimonious property and a previously unknown connection to linear production games. We also show that our techniques extend to larger classes of network design games. We then provide a simple example showing that our cost allocation does not necessarily achieve the best possible budget balance guarantee, even among cost allocations stable for the game defined by the Held-Karp relaxation, and discuss its implications on future work on traveling salesman games.

**Flow shop scheduling with peak power consumption constraints**

K. Fang, N. A. Uhan, F. Zhao, J. W. Sutherland

*Annals of Operations Research*206(1) 115-145, 2013

abstract paper

*Abstract.*We study scheduling as a means to address the increasing energy concerns in manufacturing enterprises. In particular, we consider a flow shop scheduling problem with a restriction on peak power consumption, in addition to the traditional time-based objectives. We investigate both mathematical programming and combinatorial approaches to this scheduling problem, and test our approaches with instances arising from the manufacturing of cast iron plates.

**Approximating the least core value and least core of cooperative games with supermodular costs**

A. S. Schulz, N. A. Uhan

*Discrete Optimization*10(2) 163-180, 2013

abstract paper

*Abstract.*We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a (3 + \epsilon)-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation.

**A primal-dual algorithm for computing a cost allocation in the core of economic lot-sizing games**

M. Gopaladesikan, N. A. Uhan, J. Zou

*Operations Research Letters*40(6) 453-458, 2012

abstract paper

*Abstract.*We consider the economic lot-sizing game with general concave ordering cost functions. It is well-known that the core of this game is nonempty when the inventory holding costs are linear. The main contribution of this work is a combinatorial, primal-dual algorithm that computes a cost allocation in the core of these games in polynomial time. We also show that this algorithm can be used to compute a cost allocation in the core of economic lot-sizing games with remanufacturing under certain assumptions.

**The impact of group purchasing organizations on healthcare-product supply chains**

Q. Hu, L. B. Schwarz, N. A. Uhan

*Manufacturing & Service Operations Management*14(1) 7-23, 2012

abstract paper

*Abstract.*This paper examines the impact of group purchasing organizations (GPOs) on healthcare-product supply chains. The supply chain we study consists of a profit-maximizing manufacturer with a quantity-discount schedule that is nonincreasing in quantity and ensures nondecreasing revenue, a profit-maximizing GPO, a competitive source selling at a fixed unit price, and n providers (e.g., hospitals) with fixed demands for a single product. Each provider seeks to minimize its total purchasing cost (i.e., the cost of the goods plus the provider's own fixed transaction cost). Buying through the GPO offers providers possible cost reductions, but may involve a membership fee. Selling through the GPO offers the manufacturer possibly higher volumes, but requires that the manufacturer pay the GPO a contract administration fee (CAF); i.e., a percentage of all revenue contracted through it. Using a game-theoretic model, we examine questions about this supply chain, including how the presence of a GPO affects the providers' total purchasing costs. We also address the controversy about whether Congress should amend the Social Security Act, which, under current law, permits CAFs. Among other things, we conclude that although CAFs affect the distribution of profits between manufacturers and GPOs, they do not affect the providers' total purchasing costs.

**Diversification of fuel costs accounting for load variation**

S. Ruangpattana, P. V. Preckel, D. J. Gotham, K. Muthuraman, M. Velástegui, T. L. Morin, N. A. Uhan

*Energy Policy*42 400-408, 2012

abstract paper

*Abstract.*A practical mathematical programming model for the strategic fuel diversification problem is presented. The model is designed to consider the tradeoffs between the expected costs of investments in capacity, operating and maintenance costs, average fuel costs, and the variability of fuel costs. In addition, the model is designed to take the load curve into account at a high degree of resolution, while keeping the computational burden at a practical level. The model is illustrated with a case study for Indiana's power generation system. The model reveals that an effective means of reducing the volatility of the system-level fuel costs is through the reduction of dependence on coal-fired generation with an attendant shift towards nuclear generation. Model results indicate that about a 25% reduction in the standard deviation of the generation costs can be achieved with about a 20%-25% increase in average fuel costs. Scenarios that incorporate costs for carbon dioxide emissions or a moratorium on nuclear capacity additions are also presented.

**Cost sharing mechanisms for scheduling under general demand settings**

S. Balireddi, N. A. Uhan

*European Journal of Operational Research*217(2) 270-277, 2012

abstract paper

*Abstract.*We investigate cost-sharing mechanisms for scheduling cost-sharing games. We assume that the demand is general—that is, each player can be allocated one of several levels of service. We show how to design mechanisms for these games that are weakly group strategyproof, approximately budget-balanced, and approximately efficient, using approximation algorithms for the underlying scheduling problems. We consider scheduling cost-sharing games in single machine, parallel machine, and concurrent open shop environments.

**A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction**

K. Fang, N. A. Uhan, F. Zhao, J. W. Sutherland

*Journal of Manufacturing Systems*30(4) 234-240, 2011

Special issue, "Selected Papers of 39th North American Manufacturing Research Conference"

abstract paper

*Abstract.*Manufacturing scheduling strategies have historically emphasized cycle time; in almost all cases, energy and environmental factors have not been considered in scheduling. This paper presents a new mathematical programming model of the flow shop scheduling problem that considers peak power load, energy consumption, and associated carbon footprint in addition to cycle time. The new model is demonstrated using a simple case study: a flow shop where two machines are employed to produce a variety of parts. In addition to the processing order of the jobs, the proposed scheduling problem considers the operation speed as an independent variable, which can be changed to affect the peak load and energy consumption. Even with a single objective, finding an optimal schedule is notoriously difficult, so directly applying commercial software to this multi-objective scheduling problem requires significant computation time. This paper calls for the development of more specialized algorithms for this new scheduling problem and examines computationally tractable approaches for finding near-optimal schedules.

**Near-optimal solutions and integrality gaps for almost all instances of single-machine precedence-constrained scheduling**

A. S. Schulz, N. A. Uhan

*Mathematics of Operations Research*36(1) 14-23, 2011

abstract paper

*Abstract.*We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints where all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. This NP-hard scheduling problem can be equivalently viewed as a graph orientation problem on a mixed complete bipartite graph. For various probability distributions over these instances—including the uniform distribution—we show several "almost all"-type results, including that for almost all instances, every feasible solution is arbitrarily close to optimal. To the best of our knowledge, our results are the first of their kind for scheduling and graph orientation problems.

**Minimizing the weighted sum of completion times in concurrent open shops**

M. Mastrolilli, M. Queyranne, A. S. Schulz, O. Svensson, N. A. Uhan

*Operations Research Letters*38(5) 390-395, 2010

abstract paper

*Abstract.*We study minimizing the sum of weighted completion times in a concurrent open shop environment. We show several interesting properties of various natural linear programming relaxations for this problem, including that they all have an integrality gap of 2. In addition, we propose a simple combinatorial 2-approximation algorithm that can be viewed as a primal-dual algorithm or a greedy algorithm that starts from the end of the schedule. Finally, we show that this problem is inapproximable within a factor of 6/5 - \epsilon (or within a factor 4/3 - \epsilon if the Unique Games Conjecture is true) for any \epsilon > 0, unless P = NP.

**Sharing supermodular costs**

A. S. Schulz, N. A. Uhan

*Operations Research*58(4) 1051-1056, 2010

abstract paper

*Abstract.*We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations: in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron—a problem that often arises in combinatorial optimization—has supermodular optimal costs. In addition, we examine the computational complexity of the least core and least core value of supermodular cost cooperative games. We show that the problem of computing the least core value of these games is strongly NP-hard, and in fact, is inapproximable within a factor strictly less than 17/16 unless P = NP. For a particular class of supermodular cost cooperative games that arises from a scheduling problem, we show that the Shapley value—which, in this case, is computable in polynomial time—is in the least core, while computing the least core value is NP-hard.

**The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability**

D. S. Altner, Ö. Ergun, N. A. Uhan

*Operations Research Letters*38(1) 33-38, 2010

abstract paper

*Abstract.*We study the Maximum Flow Network Interdiction Problem (MFNIP). We present two classes of polynomially separable valid inequalities for Cardinality MFNIP. We also prove the integrality gap of the LP relaxation of Wood's (1993) integer program is not bounded by a constant factor, even when the LP relaxation is strengthened by our valid inequalities. Finally, we provide an approximation-factor-preserving reduction from the simpler R-Interdiction Covering Problem to MFNIP.

#### PhD Thesis

**Algorithmic and Game-Theoretic Perspectives on Scheduling**

N. A. Uhan

PhD Thesis, Operations Research Center, Massachusetts Institute of Technology, 2008

thesis

### Collaborators and coauthors

Douglas S. Altner, Tuyin An, Sindhura Balireddi, Özlem Ergun, Kan Fang, Douglas J. Gotham, Mohan Gopaladesikan, Ashish R. Hota, Qiaohai Hu, Rachael H. Kenney, Sung-Hee Kim, Andrew L. Liu, Monaldo Mastrolilli, Thomas L. Morin, Kumar Muthuraman, Daniel Phang, Paul V. Preckel, Maurice Queyranne, Suriya Ruangpattana, Andreas S. Schulz, Leroy B. Schwarz, Aiman Shamsul, Harikrishnan Sreekumaran, Shreyas Sundaram, John W. Sutherland, Ola Svensson, Alejandro Toriello, Marco Velástegui, Ji Soo Yi, Fu Zhao, Jikai Zou