We develop in this paper two types of heuristic methods for solving the positive 0-1 polynomial programming (PP) problem of finding a 0-1 vector x that maximizes c^Tx subject to f(x) \le b where c, b \ge 0 and f is an m-vector of polynomials with non-negative coefficients. The various heuristics...

A specially-structured integer programming model, called the multiple-choice nested knapsack model, is developed in this paper. The model is characterized by variables which are partitioned into multiple-choice sets and resource constraints which are nested across the multiple-choice sets. The...

Lagrangean techniques have had wide application to the optimization of discrete optimization problems. Inverse optimization refers to the fact that each time a Lagrangean calculation is made for a specific problem with a given resources vector, an optimal solution is obtained for a related...

We present a greedy heuristic for the n job/1 machine scheduling problem with precedence constraints. This method is useful whenever the manager's optimization criteria is the sum of weighted or unweighted completion times, the sum of weighted or unweighted flow times, (with or without release...

This paper describes a branch and bound approach for optimizing a media selection problem, namely, to choose the best set of mailing lists to maximize audience reach. Prompted by a national retailer's interest in more effective and efficient direct mail catalogue distribution, the algorithm...

New lock box solution techniques have recently been suggested by Stone and Nauss-Markland. This paper briefly discusses these new methodologies and shows how the algorithms can be combined into a third solution procedure which exploits the computational efficiency of the Stone heuristic and...

The objective of the one-center model (single facility minimax location in the plane) is changed to be the maximum weighted number of demand points within a given weighted distance from the facility. The paper presents an O(n² log n) algorithm for the model along with some computational experience.

One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as easy problems complicated by a relatively small set of side constraints. Dualizing the side constraints produces a Lagrangian problem that is easy to solve...

In this note, a node elimination procedure has been suggested in case the two sequences obtained by using Townsend's (Townsend, W. 1978. The single machine problem with quadratic penalty function of completion times: A branch and bound solution. Management Sci. 24 (5) 530--534.) sufficient...

The increased focus on heuristics for the approximate solution of integer programs has led to more sophisticated analysis methods for studying their performance. This paper is concerned with the worst-case approach to the analysis of heuristic performance. A worst-case study establishes the...