We study a generic minimization problem with separable nonconvex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed-integer programming formulations each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.
In this paper, we analyze demand postponement as a strategy to handle potential demand surges. Under demand postponement, a fraction of the demands from the “regular” period are postponed and satisfied during a “postponement” period. This permits capacity to be procured to satisfy the postponed demands. A reimbursement per unit is paid to customers whose demands are postponed. The basic idea is that by preempting stockouts through demand postponement, we can reduce overall stockout costs. We formulate and solve a two-stage capacity planning problem under demand postponement. We propose a power range class of distributions to capture the nature of demand surges. We establish the scalability and conjugate properties of the power range distributions under demand postponement, which leads to a tractable analysis of the problem. We analytically solve the problem of determining the optimal regular and postponement period capacities, and the demand splitting rule to minimize the supplier's expected cost. We show that (a) the value of postponement may be significant depending on cost and demand parameters, (b) a postponement strategy may lead to reduced investment in initial capacity, and (c) it may be optimal to do no demand postponement over a range of demands even after observing a higher demand signal. We then relax several model assumptions and provide results for these extensions. We conclude with managerial insights.
In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several notoriously hard test sets, including practical problem instances from chemical production planning.
This paper presents evidence that the willingness to punish an unfair action is sensitive to whether this action was preceded by a deceptive message. One player first sends a message indicating an intended play, which is either favorable or unfavorable to the other player in the game. After the message, the sender and the receiver play a simultaneous 2×2 game, in which the sender may or may not play according to his message. Outcome cells may, hence, be reached following true or false messages. In the third stage, the receiver may (at a cost) punish or reward, depending on which cell of the simultaneous game has been reached. We test whether receivers' rates of monetary sacrifice depend on the process by which an outcome is reached. We study two decision-elicitation methods: the strategy and the direct response methods. For each method, deception more than doubles the punishment rate as a response to an action that is unfavorable to the receiver. We also find evidence that 17–25% of all participants choose to reward a favorable action choice made by the sender, even though doing so leaves one at a payoff disadvantage. Our results reflect on current economic models of utility and have implications for organizational decision-making behavior.
This paper examines the conditions under which exploration of a new, incompatible technologyis conducive to firm growth in the presence of network externalities. In particular, this study is motivated by the divergent evolutions of the PC and the workstation markets in response to a new technology: reduced instruction set computing (RISC). In the PC market, Intel has developed new microprocessors by maintaining compatibility with the established architecture, whereas it was radically replaced by RISC in the workstation market. History indicates that unlike the PC market, the workstation market consisted of a large number of power users, who are less sensitive to compatibility than ordinary users. Our numerical analysis indicates that the exploration of a new, incompatible technology is more likely to increase the chance of firm growth when there are a substantial number of power users or when a new technology is introduced before an established technology takes off.
Internet-enabled markets are becoming viable venues for procurement of professional services. We investigate bidding behavior within the most active area of these early knowledge markets—the market for software development. These markets are important both because they provide an early view of the effectiveness of online service markets and because they have a potentially large impact on how software development services are procured and provided. Using auction theory, we develop a theoretical model that relates market characteristics to bidding and transaction behavior, taking into account costly bidding. We then test our model using data from an active online market for software development services, which yields contracts for 30%–40% of posted projects. In its current format, however, the studied market may induce excessive bidding by vendors. Consistent with our theoretical predictions and those of Carr (2003), higher-value projects attract significantly more bids, with lower average quality. Greater numbers of bids raise the cost to all participants, due to costly bidding and bid evaluation. Perhaps as a consequence, higher-value projects are also much less likely to be awarded.