The interval programming model (IvP) is a mathematical programming model for representing and solving multi-objective optimization problems. The central characteristic of the model is the use of piecewise linearly defined objective functions and a solution method that searches through the combination space of pieces rather than through the actual decision space. The piecewise functions typically represent an approximation of some underlying function, but this concession is balanced on the positive side by relative freedom from function form assumptions as well as the assurance of global optimality. In this paper the model and solution algorithms are described, and the applicability of IvP to certain applications are discussed.

Interval programming (IvP) is a model and set of algorithms for representing and solving multi-objective optimization problems. 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 useful results by exploiting the nature of those constructs. The aim of this paper is to describe the constructs used in interval programming, along with the algorithms, and describe why this particular arrangement is uniquely useful for a certain class of applications. A common thread in the applications motivating the development of IvP is the need to fully automate a decision (as in a robot or autonomous vehicle), or provide a decision to a human in a critical window of time with little or no room for human interaction. Furthermore, the environment is typically composed of distinct components, or “sub-situations” that, in isolation, are fairly familiar and easy to handle. Their combination however typically creates a completely unique and unfamiliar overall situation where the decision-making challenge is in finding the right balance between the concerns of each sub-situation.

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.

Download
PDF Ebook The Interval Programming Model for Multi-objective Decision Making