Aggregating assignment constraints

This article shows how simple systems of linear equations with {0,1} variables can be aggregated into a single linear equation whose {0,1} solutions are identical to the solutions of the original system. Structures of the original systems are exploited to keep the aggregator's integer coefficients from becoming unnecessarily large. The results have potential application in integer programming and information theory, especially for problems that contain assignment-type constraints along with other constraints. Several unresolved questions of a number-theoretic nature are mentioned at the conclusion of the article.     

One-facility location with rectilinear tour distances

This article concerns the location of a facility among n points where the points are serviced by “tours” taken from the facility. Tours include m points at a time and each group of m points may become active (may need a tour) with some known probability. Distances are assumed to be rectilinear. For m ≤ 3, it is proved that the objective function is separable in each dimension and an exact solution method is given that involves finding the median of numbers appropriately generated from the problem data. It is shown that the objective function becomes multimodal when some tours pass through four or more points. A bounded heuristic procedure is suggested for this latter case. This heuristic involves solving an auxiliary three-point tour location problem.     

Geometric programming with multiplicative slack variables

A posynomial geometric programming problem formulated so that the number of objective function terms is equal to the number of primal variables will have a zero degree of difficulty when augmented by multiplying each constraint term by a slack variable and including a surrogate constraint composed of the product of the slack variables, each raised to an undetermined negative exponent or surrogate multiplier. It is assumed that the original problem is canonical. The exponents in the constraint on the product of the slack variables must be estimated so that the associated solution to the augmented problem, obtained immediately, also solves the original problem. An iterative search procedure for finding the required exponents, thus solving the original problem, is described. The search procedure has proven quite efficient, often requiring only two or three iterations per degree of difficulty of the original problem. At each iteration the well-known procedure for solving a geometric programming problem with a zero degree of difficulty is used and so computations are simple. The solution generated at each iteration is optimal for a problem which differs from the original problem only in the values of some of the constraint coefficients, so intermediate solutions provide useful information.     

Time-minimizing transportation problems

A method is given for finding those solutions of a transportation problem which minimize the total time necessary for transporting goods from the suppliers to the consumers. Several extensions of the model are presented.     

On the theory of semi-infinite programming and a generalization of the kuhn-tucker saddle point theorem for arbitrary convex functions

We first present a survey on the theory of semi-infinite programming as a generalization of linear programming and convex duality theory. By the pairing of a finite dimensional vector space over an arbitrarily ordered field with a generalized finite sequence space, the major theorems of linear programming are generalized. When applied to Euclidean spaces, semi-infinite programming theory yields a dual theorem associating as dual problems minimization of an arbitrary convex function over an arbitrary convex set in n-space with maximization of a linear function in non-negative variables of a generalized finite sequence space subject to a finite system of linear equations. We then present a new generalization of the Kuhn-Tucker saddle-point equivalence theorem for arbitrary convex functions in n-space where differentiability is no longer assumed.     

Allocation of resources to randomly occurring opportunities

An allocation problem is considered in lvhich different kinds of resources must be allocated to various activities, within a given time period. The opportunities for allo'cation appear randomly during this period. Certain assumptions about the values of possible allocations and the distribution of occurrences of opportunities lead to a dynamic programming formulation of the problem. This leads to a system of ordinary differential equations which are (in theory) solvable recursively, and can be solved numerically to any desired degree of precision. An example is given for the allocation of aircraft-carried weapons to targets of opportunity.