This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Luedtke, J. Articles by Nemhauser, G. L.

Strategic Planning with Start-Time Dependent Variable Costs

Department of Industrial and Systems Engineering, University of Wisconsin–Madison, Madison, Wisconsin 53706
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
jrluedt1{at}wisc.edu
gnemhaus{at}isye.gatech.edu

We present a strategic planning model in which the activities to be planned, such as production and distribution in a supply network, require technology to be installed before they can be performed. The technology improves over time, so that a decision maker has incentive to delay starting an activity to take advantage of better technology and lower operational costs. The model captures the fundamental trade-off between delaying the start time of an activity and the need for some activities to be performed now. Models of this type are used in the oil industry to plan the development of oil fields. This problem is naturally formulated as a mixed-integer program with a bilinear objective. We develop a series of progressively more compact mixed-integer linear formulations, along with classes of valid inequalities that make the formulations strong. We also present a specialized branch-and-cut algorithm to solve an extremely compact concave formulation. Computational results indicate that these formulations can be used to solve large-scale instances, whereas a straightforward linearization of the mixed-integer bilinear formulation fails to solve even small instances.

Subject classifications: integer programming; theory and applications; facilities/equipment planning; capacity expansion; technology.
History: Received February 2007; revision received January 2008; accepted June 2008.