| |
The basic idea, as with other mathematical programming models, is to
provide a specific set of mathematical constructs for representing a
class of problems, and a set of algorithms that generate solutions by
exploiting the nature of those constructs.
The central characteristic of the model is the use of piecewise
linearly defined objective functions that may represent only an
approximation of an underlying objective function. The solution method
searches through the combination space of pieces, one from each
function, rather than through the actual decision space. By performing
search using the piecewise linear functions rather than the actual
underlying function, the search algorithm is freed from function form
assumptions, and global optimality (modulo the error between the two
function representations) can be guaranteed. The problem of producing
a piecewise linear function that adequately represents the underlying
function is indeed a significant part of the overall solution process,
and the notion of adequacy may be subjective. However, the piecewise
approximation may be produced either off-line and outside the critical
decision window, or it may be done in real-time by a module that knows
about the particular kind of function it is tasked with approximating
and uses this insight to create sufficiently accurate piecewise
approximations sufficiently fast. The distinct separation of these
two aspects of the solution process, the construction of the piecewise
functions, and searching through the combination of pieces, is a
central design decision that was made not only in the interest of
balancing speed and accuracy tradeoffs, but also in the interest of
providing a flexible model without function form assumptions to
accommodate an eclectic collection of objective function producing
modules.
|