Abstract. Implementing management practices in a cost-efficient manner is critical for regional efforts to reduce the amount of pollutants entering the Chesapeake Bay. We study the problem of selecting a subset of practices that minimizes pollutant load—subject to budgetary and environmental constraints—as simulated in a widely used regulatory watershed model. Mimicking the computation of pollutant load in the regulatory model, we formulate this problem as a continuous optimization model with a linear multiplicative objective function and linear constraints. To lay the groundwork for incorporating additional stakeholder requirements in the future, especially those that would require integer variables, we present and study a continuous linear optimization model that approximates the nonlinear model. The linear model, which requires an exponential number of variables, arises naturally as an alternative model for the same underlying physical process. We examine the theoretical behavior of these optimization models and investigate restrictions of the linear model to handle its large number of variables. Through extensive computational tests on real and randomly generated instances, we demonstrate that the linear model and its restrictions provide optimal solutions close to those of the nonlinear model in practice, despite poor approximation properties in the worst case. We conclude that the linear modeltogether with our approach to handling its large number of variablesprovides a viable framework from which to extend the optimization model to better meet the needs of the Chesapeake Bay watershed management stakeholders.

Abstract. Freight consolidation is a logistics practice that improves the cost-effectiveness and efficiency of transportation operations, and also reduces energy consumption and carbon footprint. A "fair" shipping cost sharing scheme is indispensable to help establish and sustain the cooperation of a group of suppliers in freight consolidation. In this paper, we design a truthful acyclic mechanism to solve the cost-sharing problem in a freight consolidation system with one consolidation center and one common destination. Applying the acyclic mechanism, the consolidation center decides which suppliers' demands ship via the consolidation center and their corresponding cost shares based on their willingness to pay for the service. The proposed acyclic mechanism is designed based on bin packing solutions that are also strong Nash equilibria for a related non-cooperative game. We study the budget-balance of the mechanism both theoretically and numerically. We prove a 2-budget-balance guarantee for the mechanism in general and better budget-balance guarantees under specific problem settings. Empirical tests on budget-balance show that the mechanism only charges slightly more than the minimum shipping cost in practice. We also study the economic efficiency of our mechanism numerically to investigate its impact on social welfare under different conditions.

Abstract. We investigate privacy-preserving ways of allocating payoffs among players participating in a joint venture, using tools from cooperative game theory and differential privacy. In particular, we examine linear programming games, an important class of cooperative games that model a myriad of payoff sharing problems, including those from logistics and network design. We show that we can compute a payoff allocation in the approximate core of these games in a way that satisfies joint differential privacy.

Abstract. In this paper, we focus on the cost-sharing problem for ride-sharing: determining how to allocate the total ride cost between the driver and the passengers. In particular, we focus on the scenario where drivers are also commuters with the goal of cost recovery. We identify the properties that a desirable cost-sharing mechanism should have and develop a general framework that can be used to create specific cost-sharing mechanisms. We propose specific mechanisms and analyze their relative advantages and disadvantages so that service providers can select a mechanism according to their different needs. In addition, we incorporate the value of time by allowing passengers to have inconvenience costs due to extra travel time caused by detours for picking up the passengers, and provide discount methods to compensate for these costs. We evaluate our approach using real traffic data from the downtown Los Angeles area. Our results show that each proposed mechanism has its unique advantages and that the discount methods can successfully reduce the number of no-passenger vehicles for a large ride-sharing system.

Abstract. In this work, we introduce multi-interdictor games, which model interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on shortest path multi-interdictor (SPMI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries attempting to traverse a common network. We first establish results regarding the existence of equilibria for SPMI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the SPMI game, 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 SPMI 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 lower bounds on the worst-case efficiency loss of equilibria in SPMI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to numerically study the average-case efficiency loss.

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.

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.

Abstract. In this work, we study the problem of scheduling courses and instructors in the Mathematics Department at the United States Naval Academy (USNA) in a resilient manner. Every semester, the department needs to schedule around 70 instructors and 150-180 course sections into 30 class periods and 30 rooms. We formulate a stochastic integer linear program that schedules these courses, instructors, and rooms. In addition to maximizing instructor preferences and room stability, this stochastic integer linear program minimizes the expected number of changes required in the schedule if a disruption were to occur, given a subjective probability distribution over a finite set of possible disruption scenarios. We run our model on a number of instances derived from actual data from the past three years, and investigate the effect of emphasizing different parts of the objective function on the running time and resulting schedules.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.