Knowledge that Transforms

Rules are given that permit 0-1 polynomial programming problems to be converted to 0-1 linear programming problems in a manner that replaces cross-product terms by continuous rather than integer variables. Since the difficulty of mixed integer programming problems often depends more strongly on the number of integer variables than on the number of continuous variables, such rules are expected to have advantages in practical applications. In addition, the continuous variables automatically receive integer values, and hence our formulation can also be exploited by methods designed to take advantage of a pure integer structure.

Miller and Wagner have shown that a deterministic equivalent of a joint chance-constrained programming model with independent random right-hand-side elements is a concave programming problem. This paper obtains similar equivalents for chance-constrained programming models with coefficient matrices whose elements are normally distributed and with dependent random right-hand-side elements.

This paper introduces and illustrates an efficient algorithm, called the sweep algorithm, for solving medium- as well as large-scale vehicle-dispatch problems with load and distance constraints for each vehicle. The locations that are used to make up each route are determined according to the polar-coordinate angle for each location. An iterative procedure is then used to improve the total distance traveled over all routes. The algorithm has the feature that the amount of computation required increases linearly with the number of locations if the average number of locations for each route remains relatively constant. For example, if the average number of locations per route is 7.5, the algorithm takes approximately 75 seconds to solve a 75-location problem on an IBM 360/67 and approximately 115 seconds to solve a 100-location problem. In contrast, the time to solve a problem with a fixed number of locations increases quadratically with the average number of locations per route. The sweep algorithm generally produces results that are significantly better than those produced by Gaskell's savings approach and are generally slightly better than Christofides and Eilon's results; however, the sweep algorithm is not as computationally efficient as Gaskell's and is slightly less so than Christofides and Eilon's.