Some Uses of Mathematical Programming Systems to Solve Problems that are not Linear

Abstract

There are three main reasons why a purely linear programming model may not represent a constrained optimization problem adequately: economies of scale, other non-linearities that do not invalidate a local optimum, random data. These reasons lead respectively to integer programming, non-linear programming and stochastic programming.

Examples of each type of model are discussed. These have all been solved using a standard mathematical programming system to exploit sparseness efficiently.

Economies of scale arise when selecting a set of new pipelines to expand the capacity of a given network. This problem involves non-linear functions, but is essentially an integer programming problem because we must use branch and bound methods to find the best combinations of pipelines, and pipeline diameters. An unsuccessful and a subsequent successful formulation for this problem are discussed.

A non-linear programming model for allocating resources in health care is outlined.

A model for multi-time-period production scheduling with stochastic demands is also outlined. The model requires data defining the uncertainties in demand forecasts, and the extent to which these are correlated with each other and with past sales. The existence of software for this model may encourage more people to quantify these data.