2005 JFIG Paper Competition

First Place

Compound Poisson Disorder Problem
Savas Dayanik and Semih Sezer, Princeton University

In a compound Poisson disorder problem, arrival rate and/or jump distribution of some compound Poisson process change suddenly at some unknown and unobservable time. The problem is to detect the change (or disorder) time as quickly as possible. A sudden regime-shift may require some counter-measures be taken promptly, and a quickest detection rule can help with those efforts. We describe complete solution of compound Poisson disorder problem with several standard Bayesian risk measures. Solution methods are feasible for numerical implementation and are illustrated on examples.

Second Place

Semi Continuous Cuts for Mixed Integer Programming
Ismael de Farias, University at Buffalo, SUNY

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integer programming. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for mixed-integer programming and problems with semi-continuous variables. We present computational results that demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts. Our computational experience also shows that dealing with semi-continuous constraints directly in the branch-and-cut algorithm through a specialized branching scheme and semi-continuous cuts is considerably more practical than the "textbook" approach of modeling semi-continuous constraints through the introduction of auxiliary binary variables in the model.

HONORABLE MENTION

Inspection and Replenishment Policies for Systems with Inventory Record Inaccuracy
Gurhan Kok and Kevin Shang, Fuqua School of Business, Duke University

For many companies, inventory record inaccuracy is a major obstacle to achieving operational excellence. In this paper, we consider an inventory system in which inventory records are inaccurate. The manager makes inventory inspection and replenishment decisions at the beginning of each period. There is a fixed cost associated with each inspection. If an inspection is performed, inventory records are aligned with physical inventory. The objective is to develop a joint inspection and replenishment policy that minimizes total costs in a finite horizon. We show that an inspection adjusted base-stock (IABS) policy is near-optimal. Under this policy, the manager performs an inspection if the recorded inventory level is less than a threshold level and orders up to a base-stock level that depends on the inspection decision. In addition to this structural result, our study (1) provides guidelines for managers to design effective inspection schedules, (2) shows that the commonly-practiced cycle count policy can be effective if the right inspection cycle is chosen, and (3) quantifies the true value of RFID systems.

Minimizing Flow Disruption due to Network Maintenance
Yanjun Li and Mohit Tawarmalani, Purdue University

This paper introduces a network maintenance scheduling problem under maintenance capacity restrictions and studies the effect of maintenance operations on productivity loss. The objective is to minimize the flow disruption, a measure of the loss of productivity, during maintenance activities. Unfortunately, this maintenance scheduling problem is intractable even when the underlying network is linear and the flows are allowed to take two different values. Our study first targets linear networks with a special flow structure which includes the uniform flow case. We devise a polynomial-time combinatorial algorithm for solving the minimum disruption network maintenance problem, characterize the structure of the set of all optimal schedules, discuss the impact of maintenance capacities on flow disruption and identify specific types of flow changes that retain optimality of a maintenance schedule. As shown here, the optimal maintenance schedules have a peculiar structure and this structure yields many insights into general maintenance scheduling. Then, with a general flow structure, we develop an integer programming formulation for the acyclic network maintenance problem and a specialized formulation for linear network maintenance problem. We derive valid inequalities, use reformulation-linearization technique to tighten formulation, and conduct polyhedral study of formulations using network flow and primal-dual methods. We computationally demonstrate that our formulations are capable of solving reasonably large instances of the problems. Finally, we extend our model and analysis to the maintenance problems on directed networks and network nodes.

Finalists

Stochastic Revenue Management Models for Media Broadcasting
Victor Araman and Ioana Popescu, NYU Stern School of Business and INSEAD

An important challenge faced by media broadcasting companies is how to allocate the limited advertising capacity between upfront contracts and the scatter market in order to maximize profits. We develop stylized optimization models of inventory allocation for one client and one media channel, in the presence of audience uncertainty. Closed form solutions for upfront contract allocation are obtained. Dynamic make-goods allocation are investigated under reversible and irreversible commitment strategies. We provide structural properties and sensitivity analysis for the value function and optimal solution with respect to contract parameters, audience and time. Our results hold under very general performance metrics, and bring out interesting parallels with standard inventory and revenue management frameworks.

The Optimal Time to Disclose Software Vulnerability
Jeevan Jaisingh and Qing Li, Hong Kong University of Science and Technology

Software vulnerability disclosure has been a critical area of concern for social planners. It is well known that while early disclosure may push vendors to create patches sooner, late disclosure reduces the risk of making the vulnerabilities known to malicious users. This paper provides a new view of the problem. We argue that to set an optimal disclosure policy, the social planners must trade off an incentive effect for an information effect. On one hand, because vendors typically have different objectives than the social planners have, social planners need to use disclosure as an incentive scheme for coordination. That is, the incentive effect favors early disclosure. On the other hand, social planners must decide on a disclosure policy before they know when the vulnerabilities would be discovered by benign users, but vendors can postpone their patching decisions until that information is known. Since the vendors are endowed with more accurate information and hence are able to make more informed choices, they should be left unregulated. That is, the information effect favors late disclosure. As a result of this tradeoff, social planners should disclose the vulnerabilities after a finite and non-zero grace period or keep them secret, depending on which effect dominates, but they should never disclose them instantly. Two factors may affect the tradeoff: the vendors’ liability for their customers’ losses resulting from attacks and the experience that hackers can accumulate on the vulnerabilities over time. We show how these two factors affect the incentive conflict and information asymmetry and hence the optimal disclosure policy.