Nelson A. Uhan

Associate Professor
Mathematics Department ■ United States Naval Academy
uhan 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

Dynamic and Stochastic Models (SA402)
Fall 2013, Fall 2016
description   website
This course provides an introduction to modeling and analyzing systems that evolve dynamically over time and whose behavior is stochastic, or uncertain. is course focuses on models that are amenable to mathematical analysis, while using basic notions from simulation to develop intuition.
Naval Applications of Operations Research (SA475)
Spring 2014, Spring 2015, Spring 2016
description   website
A capstone course focused on applications of operations research techniques to Navy-relevant problems. Midshipmen will work in teams on projects coordinated with the Johns Hopkins University Applied Physics Laboratory.
Linear Programming (SA305)
Spring 2013, Spring 2014, Spring 2015, Spring 2016
description   website
Operations research (OR) is a broad field which, loosely speaking, investigates how mathematical techniques can be used to solve "real-life" decision-making problems. This course provides an introduction to linear programming, a fundamental technique used in OR. In particular, the course focuses on formulating mathematical optimization models (also called mathematical programs), and understanding the mathematical underpinnings of linear programming algorithms.
Mathematics for Economics (SM286A)
Fall 2015
description   website
A brief introduction to linear algebra, differential and difference equations, and nonlinear optimization for economics majors.
Simulation Modeling (SA421)
Spring 2013, Fall 2014, Fall 2015
description   website
This course focuses on the use of simulation as a decision-making tool, including explorations into what simulation is, how to use it, and when its use is appropriate. These topics are studied using SimPy, a discrete-event simulation language based on Python.
Calculus III with Optimization (SM223)
Fall 2012
description   website
Differential and integral calculus of several real variables. Vector analysis. Optimization techniques for functions of several variables.

At Purdue

Operations Research - Optimization (IE 335)
Fall 2008, Fall 2009, Spring 2010, Fall 2010, Spring 2011, Fall 2011, Spring 2012
description
An introduction to optimization for undergraduate engineering students, primarily juniors majoring in industrial engineering. Linear, network, and discrete optimization models and algorithms.
Integer Programming (IE 634)
Fall 2011
description
A graduate-level course in integer programming. Review of linear progamming and polyhedral theory. Valid inequalities, facet-defining inequalities, ideal formulations. Integer programming duality. Branch and bound, cutting plane methods, column generation methods.
Combinatorial Optimization (IE 639)
Fall 2010
description
A graduate-level course in combinatorial optimization. Minimum spanning trees, shortest paths, maximum flows and minimum cuts. Polyhedral theory and linear programming duality. Matroids and submodularity. Matchings.

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