|
Article Excerpt
(Piecewise Linear; Integer Programming; Linear Relaxation; Lagrangian Relaxation)
1. Introduction
Optimization problems with piecewise linear costs arise in many application domains, including transportation, telecommunications, and production planning. Specific applications include variants of the minimum cost network flow problem with nonconvex piecewise linear costs (Aghezzaf and Wolsey 1994, Balakrishnan and Graves 1989, Chan et al. 1997, Cominetti and Ortega 1997, Croxton 1999, Croxton et al. 2002b), such as the network loading problem (Bienstock and Gunluk 1996, Gabrel et al. 1999, Gunluk 1999, Magnanti et al. 1995), the facility location problem with staircase costs (Holmberg 1994, Holmberg and Ling 1997), and the merge-in-transit problem (Croxton et al. 2002a). Each of these studies introduces integer variables to model the costs, though the choice of the basic formulation varies and includes three textbook models--the so-called incremental, multiple choice, and convex combination models. The objective of this note is to show that the linear programming (LP) relaxations of these mixed-integer programming (MIP) models are equivalent and that they all approximate the cost function by its lower convex envelope. To the best of our knowledge, although this result might appear to be intuitive, no one has formally established it. We also discuss the relationship between this result and classical Lagrangian duality theory.
The general problem, P, is to minimize the separable sum of piecewise linear functions, subject to linear constraints, which we write as min{g(x): Ax [greater than or equal to] b, [less than or equal to] x [less than or equal to] u}, with g(x) = [[SIGMA].sub.j]/[g.sub.j]([x.sub.j]), b and u as vectors, and A as a matrix. Because the formulations we consider model each function [g.sub.j]([x.sub.j]) separately, for notational simplicity we will drop the subscript j. We then let x denote a single variable, called the load, and focus on a single piecewise linear function g(x). This simplification is justified by the fact that the lower convex envelope of a separable sum of functions (defined over a bounded polyhedron) equals the sum of the lower convex envelopes of these functions (Falk 1969).
The function g(x) need not be continuous; it can have positive or negative jumps, though we do assume that the function is lower semicontinuous, that is, g(x) [less than or equal to] lim [inf.sub.x'[right arrow]x] g(x'). Without loss of generality, we also assume, through a simple translation of the costs if necessary, that g(0) = 0. Each piecewise linear segment S [member of] {1, 2,...,S} of the function g(x) has a variable cost, [c.sup.s] (the slope), a fixed cost, [f.sup.s] (the cost-intercept), and upper and lower bounds, [b.sup.s-1] and [b.sup.s] (the breakpoints), on the load corresponding to that segment. We assume [b.sup.0] = 0. Figure 1 illustrates the notation.
[FIGURE 1 OMITTED]
Using this notation, in [section]2 we present three well-known valid MIP models for the problem. In [section]3, we show that the LP relaxations of the three formulations are equivalent and that they each approximate the cost function by its lower convex envelope. In [section]4, we discuss the relationship between this result and classical Lagrangian duality theory.
2. Three Models for Piecewise Linear Costs
Incremental Model
Dantzig (1960) and Vajda (1964) both attribute the...
|
