Search

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

This paper introduces an efficient branch and bound algorithm for a special class of mixed integer programming problems called the warehouse location problem. A set of branching decision rules is proposed for selecting warehouses to be constrained open and closed from any node of the branch and bound tree. These rules are tested for their efficiency in reducing computation times and storage requirements to reach optimal solutions. An improved method of solving the linear programming problems at the nodes which substantially reduces the computations is also introduced in this paper. [ABSTRACT FROM AUTHOR]

This paper deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]

This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the problem of partitioning N entities into M disjoint and nonempty subsets (clusters). Except when both N and N--M are very small, a search for the optimal solution by total enumeration of all clustering alternatives is quite impractical. The paper presents a dynamic programming approach that reduces the amount of redundant transitional calculations implicit in a total enumeration approach. A comparison of the number of calculations required under each approach is presented in Appendix A. Unlike most clustering approaches used in practice, the dynamic programming algorithm will always converge on the best clustering solution. The efficiency of the dynamic programming approach depends upon the rapid-access computer memory available. A numerical example is given in Appendix B. [ABSTRACT FROM AUTHOR]

In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]

This paper explores methods for scheduling preventive maintenance by means of mathematical programming. Five integer linear programming models are posed, each based on a different optimality criterion dealing with manpower smoothing. By means of two hypothetical examples the models are tested for their computational properties. In addition to describing the experimental results of applying integer linear programming techniques to this class of problems, the paper also illustrates how effectively rounded linear programming solutions can be used as approximations to optimal solutions. [ABSTRACT FROM AUTHOR]

This paper presents new types of cutting-plane algorithms for integer-constrained optimization problems. The underlying idea of the method of enumerative cuts is to make use of an enumeration procedure in order to construct cutting planes that can be made arbitrarily deep. In recent publications, BALLAS and YOUNG have established in somewhat different contexts that valid cutting planes can be generated from the intersection of (basic) rays with adequately constructed hyperspheres. This paper introduces a family of polyhedra to replace the sphere; these polyhedra are not tangential to the hypersphere and produce cutting planes with particular characteristics that are discussed. Constructive procedures are sketched for generating step-by-step cutting planes that become deeper and deeper at every step, until the deepest cut is obtained. This construction often relies on a partial enumeration scheme of the set of integer solutions. [ABSTRACT FROM AUTHOR]

The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such problems is presented. Two numerical examples are also included. [ABSTRACT FROM AUTHOR]

Integer programs may have constraints which are redundant or else nonbinding. They may also have variables which are extraneous in the sense that there is some optimal program in which they are nonpositive. Thompson, Tonge and Zionts [1] have discussed the topics of redundant constraints and extraneous variables in linear programs. This paper extends their results to integer programs, and provides new proofs of the original results. [ABSTRACT FROM AUTHOR]

The usefulness of integer programming as a tool of capital budgeting hinges on the development of an efficient solution technique. An algorithm based on partial enumeration has been developed by E. L. Lawler and M. D. Bell for solving integer linear programs with 0-1 decision variables; however their algorithm is not general enough to deal with all problems in which the objective function is quadratic. This paper extends Lawler and Bell's method so that it can be generally applied to integer quadratic programs. The new algorithm is illustrated by examples from capital budgeting. [ABSTRACT FROM AUTHOR]

This paper presents an approach to the following problem involving uncertainty: the choice of sample design for the estimation of parameters which are not identified prior to the sample selection. More specificly, the author suggests the use of 'contingency planning' as developed in the realm of military systems analysis, to supplement the use of standard sample survey theory. [ABSTRACT FROM AUTHOR]

This paper investigates the solution by integer programming of reliability optimization problems which are subject to linear and nonlinear separable restraints. In particular, the following problems are solved: (1) maximizing reliability for a parallel redundancy system subject to multiple linear restraints, (2) minimizing cost of a parallel redundancy system subject to multiple nonlinear and separable restraint functions while maintaining an acceptable level of reliability, (3) optimal choice of design for a parallel redundancy system. Also discussed are the necessary alterations to the above formulations for problems involving standby redundant units. [ABSTRACT FROM AUTHOR]

This paper gives a description of how to find the 'best' sequence of allocation of resources to projects. The method handles simultaneously a great number of projects. The expression 'best' sequence means here the priority-rating that optimizes some chosen measure for the efficiency of the system. This optimization is done within the limits of the total resources available for allocation to projects. The problem is solved for whatever dependency there may be between resource quantity and system efficiency for the single projects. It works for the 'difficult' case of discontinuous efficiency functions as well. It is shown that in order to handle a great number of projects, one can divide the projects into groups, apply the method within each group of projects, then consider each group as a super project, and finally solve the whole problem by using the same method on groups. The problem is solved by a combination of the dynamic programming method, Lagrange's multiplier method, and numerical calculations on an electronic computer. The main part of the method is shown in a flow-diagram form. In the last sections of this paper practical examples are given, where the method is applied on investment problems. [ABSTRACT FROM AUTHOR]

This paper connects some of the recent developments in concave and integer programming. In particular, it points out parallels between the work of HOANG TUI and R. D. YOUNG. From these methods, a finite algorithm for solving a special class of 0–1 integer programs is developed. Our approach contrasts with an earlier extension of Tui's method due to M. RAGHAVACHARI and general ‘intersection’ or ‘convexity’ cut approaches. [ABSTRACT FROM AUTHOR]

In deriving the well known cuts for cutting-plane methods in 0, 1 integer programming, the integer points outside the 0, 1 space can limit the parallel movement of the hyperplane of the cut toward the solution set. Furthermore it is unnecessarily restrictive to limit the movement of this hyperplane to parallel translations. This paper removes these two limitations in order to derive stronger cuts and reduce the total number of cuts required. Thus, it describes a method based on a special case of the knapsack function that replaces each cut or original constraint by a new inequality whose hyperplane passes through as many integer points in 0, 1 space as possible. [ABSTRACT FROM AUTHOR]

The convex hull of the feasible integer points to a given integer program is a convex polytope I. The feasible set obtained by relaxing the integrality requirements is another convex polytope L. Cutting-plane algorithms essentially try to remove part of L--I. Hence the more complicated the relationship between L and I, the more difficult (in some sense) the integer program. This paper shows one such complexity: specifically, we construct a series of programs such that I has arbitrarily many faces even though L is a triangle. We also indicate the existence of a large class of problems that exhibit the same behavior. [ABSTRACT FROM AUTHOR]

The main result of this paper is a group theoretic algorithm (GTIP2) for the integer programming problem. This algorithm is an extension of an algorithm from an earlier paper (part I). The algorithm in part I solves a group optimization problem derived from a given integer programming problem. The optimal solution to the group problem thereby obtained is an optimal solution to the integer programming problem if it is feasible. Unfortunately, an optimal solution to the group problem may yield an infeasible integer solution. The algorithm GTIP2 of this paper is an extension of the method of part I when it fails. In particular, GTIP2 employs a search procedure to find an optimal solution to the integer programming problem. The extent of the search is bounded by procedures derived from a variety of relevant group problems that are solved by the algorithm of part I. There is a discussion of the class of problems for which GTIP2 is primarily intended and the relation of GTIP2 to other algorithms is indicated. A numerical example and some partial computational results are included. [ABSTRACT FROM AUTHOR]

In this paper a search scheme for finding the maximum of a discrete objective function of several variables is proposed. The scheme is sequential and optimal in the sense that it determines the maximum with minimum number of measurements of the function. Unlike other sequential search techniques with this property the scheme places no condition on the number of possible maxima of the objective function. Instead it requires that some bounds on the rate of change of the function per each variable be known. The points at which measurements of the value of the objective function are to be taken are determined successively by maximization of an auxiliary function updated after each measurement. The algorithm is described in detail, and illustrated by two simple examples. [ABSTRACT FROM AUTHOR]

Mathematical programming as an aid to R&D project portfolio selection has been suggested by many authors, but few practical applications have been reported. This paper discusses some of the difficulties, associated with the application of the proposed models, and describes procedures for handling these problems. Problem areas considered are: Allowance for future opportunities in multi-period models, Generation of alternative risk-return solutions, Inclusion of projects not completed during the planning period, Comparison of linear and integer programming outputs. In the main, both the problems and methods of solution are clarified by means of numerical examples, and details of a practical case study are given. [ABSTRACT FROM AUTHOR]

In a preceding paper Jacobsen [3] shows that marginal allocation solves a class of discrete, single constraint, min-max allocation problems. A dual approach to this problem is presented, based on a generalization of Jacobsen's P condition, which should prove more efficient when many marginal improvement iterations would be required. A variant of sequential search by bisection is applied, possibly augmented by an accelerated marginal allocation scheme, in which finite convergence to an optimum solution is guaranteed. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of the knapsack problem. The method involves searching the nodes of a tree along a single branch at a time. The algorithm eliminates the computational drawbacks inherent in the usual branch and bound schemes. [ABSTRACT FROM AUTHOR]

In this paper we present an algorithm for solving mathematical programming problems of the form: Find x = (x[sub 1], ..., x[sub n]) to minimize Σφ[sub i] (x[sub i]) subject to x ε G and I ≤ x ≤ L. Each φ[sub i] is assumed to be lower semicontinuous, possibly nonconvex, and G is assumed to be closed. The algorithm is of the branch and bound type and solves a sequence of problems in each of which the objective function is convex. These problems correspond to successive partitions of the feasible set. Two different rules for refining the partitions are considered; these load to convergence of the algorithm under different requirements on the problem functions. Examples are given, and computational considerations are discussed. [ABSTRACT FROM AUTHOR]

One reasonable formulation of stochastic linear programming problem leads to a deterministic nonlinear programming problem where the nonlinearity occurs in the objective function as the sum of square roots of positive semi-definite quadratic forms. It may, however, be difficult to solve this problem directly because of the nondifferentiability of the terms in the objective function. The present paper establishes a dual to the nonlinear programming problem of which a solution may be easily obtained. A solution of the dual then helps to obtain a solution of the original problem. [ABSTRACT FROM AUTHOR]

The optimal coupon schedule for municipal bonds with limits on the number of distinct coupons is formulated in terms of two different dynamic programming models which, in contrast to the companion paper, do guarantee an optimal solution, although at the cost of additional computational difficulty. [ABSTRACT FROM AUTHOR]

The article focuses on models of fleet routing and scheduling problems for transportation systems, which are formulated as integer linear programs with 0-1 variables. The topics discussed in this paper are concerned with important operational problems confronting the management of the competitive air transportation system. Some of these problems are significant for other transportation systems, including those with public-service rather than profit objectives. The problems are those connected with fleet utilization, fleet size, routing, and scheduling. Work that is related to some of these problems has been carried out by operations researchers and has been limited because, when optimal solutions were sought, computation times were excessive. The principal method of attack has been dynamic programming, which usually involves a very large state space for any real-life transportation system. The basic models are of the discrete-time rather than of the continuous-time variety. This property permits the formulation of the optimization problems as integer linear programs. The aim is to formulate a realistic model and to obtain its optimal solution

GOMORY has transformed the integer programming problem into a related group optimization problem which can be more easily solved. An optimal solution to the group problem is optimal for the integer programming problem from which it is derived if the solution is feasible. An algorithm (IP Algorithm I) for solving the group optimization problem is developed, and sufficient conditions on its use are given. The usefulness of IP Algorithm I is extended by amending it to find alternative optima. In a subsequent paper, this algorithm is extended to an algorithm that can solve any integer programming problem. [ABSTRACT FROM AUTHOR]

Group theory is used to integrate a wide variety of integer programming methods into a common computational process. Included are group optimization algorithms, Lagrangian methods, the cutting plane method, and the method of surrogate constraints. These methods are controlled by a supervisor which performs four main functions: set-up, directed search, subproblem analysis, and prognosis. Some computational experience is given. One appendix contains an algorithm for dynamically solving unconstrained group problems. A second appendix gives an algorithm for solving zero-one group problems. [ABSTRACT FROM AUTHOR]

Problem-solving procedures based on the methods of combinatorial programming are presented for solving a class of integer programming problems in which all elements are zero or one. All of the procedures seek first a feasible solution and then successively better and better feasible solutions until ultimately one is discovered which is shown to be optimal. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problemsolving process, a number of problems involving several hundred integer variables have been solved in a matter of seconds. [ABSTRACT FROM AUTHOR]

A number of packaging problems involve optimization of costs subject to constraints imposed by the geometry of the alternatives. One such problem arises in those consumer goods warehousing systems which pack a large number of similar products, differing in size, into individual boxes for warehousing and subsequent shipment to the ultimate consumer. Box cardboard costs and warehouse space costs are minimized if boxes exactly fit each product size; on the other hand, box inventory, handling, and purchase costs are minimized if only one box size is used for all product sizes. The problem is to select the optimum number and sizes of boxes which minimize the total system costs. An integer programming formulation of the problem is given, and the results obtained from the application of a heuristic procedure to a specific problem are described. [ABSTRACT FROM AUTHOR]

This article discusses two linear programming models used in capital budgeting. Many real-world optimization problems have the property that optimal decisions must be stated in terms of integers or whole numbers. This is the case, for example, in capital budgeting models where the integer 0 means that one does not undertake a project and the integer 1 indicates that one does. A model for many such problems is that of integer programming. The two models include a linear programming model without integer restrictions and the other the same linear programming model but with integer restrictions on the decision variables. The former, which is an approximation, is referred as the LP model, and the latter is referred as the IP model. There is no way to round an LP optimal solution to get an optimal solution to the IP model.

The article presents the author's response to a commentary on his paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," from the January, 1970 edition of the journal "Management Science." The author presents his assessment of the job shop sequencing problem and a counterexample. He contends that his results will stand up relative to a comprehensive, detailed analysis of the dilemma. The author presented an integer programming formulation for a one-machine job shop problem.

Many practical operations-research problems have the form in which the objective is to select an optimal production schedule, rental policy, distribution pattern, etc., from among a variety of alternatives, each of which has an associated set of constraints that must all be satisfied if a particular alternative is chosen. The disjunctive-facet problem provides a 'direct' formulation for such problems, circumventing the need to resort to artifices involving the creation of discrete variables and supporting constraints to model these problems as mixed integer programs. We provide special cutting planes that are designed to take particular advantage of the disjunctive-facet problem structure. Thus, our results not only give a more compact representation of certain classes of discrete optimization problems, but provide more powerful methods for solving these problems as well. [ABSTRACT FROM AUTHOR]

The early work done on the assortment problem assumed known demands and additive and proportional substitution cost functions for single period problems. The extension of this problem (to consider probabilistic demands and multiple periods) complicates the problem considerably. By making some assumptions about the pattern of demands and the form of a reasonable solution, the problem can be approached by using dynamic programming thus finding the shortest route through a network. [ABSTRACT FROM AUTHOR]

In the knapsack problem, given the desirability of each of a number of items, one seeks to find that subset which satisfies a constraint on total weight. The multidimensional variant imposes constraints on additional variables of the items; the 0/1 specification means that an item is either taken or not, i.e., multiples of the same item are not considered, except possibly indirectly. Traditionally the one-dimensional knapsack problem is solved by means of dynamic programming. The multidimensional problem is usually reduced to a one-dimensional one by use of Lagrangian Multipliers that, however, do not generally yield the exact solution to the problem posed. Here some new algorithms are developed that are applied within a dynamic programming framework. Additionally, the methods make integral use of an interactive computer system in which the heuristics of the problem solver are applied and changed as the character of the solution process evolves. The problem arises in the context of capital budgeting, but has obvious applications in a variety of other areas. The methods have been employed for solving numerical problems with as many as 105 items, the parameters having been obtained from industrial applications. [ABSTRACT FROM AUTHOR]

A method is presented for test construction and scoring which utilizes the knapsack model of mathematical programming. The method applies to examinations of the type in which a choice exists in the number of questions the examinee is required to answer. The method has been utilized with respect to a mathematics examination and computer generated results of this test are provided. [ABSTRACT FROM AUTHOR]

A unifying framework is developed to facilitate the understanding of most known computational approaches to integer programming. A number of currently operational algorithms are related to this framework, and prospects for future progress are assessed. [ABSTRACT FROM AUTHOR]

The usefulness of group theoretic methods in solving integer programming (IP) problems is extended by procedures for controlling the size of the groups. The main procedure given shows how an optimal linear programming basis can be altered to reduce the magnitude of its determinant thereby reducing the size of the group induced by the basis. An adaption of Benders' mixed IP algorithm is given which uses these methods. Some limited computational experience is given. [ABSTRACT FROM AUTHOR]

Some new properties associated with the special class of integer programs known as weighted set covering problems are derived. While it is well known that an optimal integer solution to the set covering problem is a basic feasible solution to the corresponding linear program, we show that there exists an optimal basis which is involutory (i.e., B = B[sup -l]). This property and others are used to develop a new algorithm which uses strong cutting planes. The cutting planes are strong in the sense that they exclude both integer and noninteger solutions. Computational experience is presented. [ABSTRACT FROM AUTHOR]

In this report, twenty-nine integer linear programming problems, ranging from very simple to apparently rather difficult, are introduced. The results of running these problems on four different computer codes, involving five distinct algorithms, are presented as both time and iteration data. A brief description of the codes used is also included. [ABSTRACT FROM AUTHOR]

We treat a dynamic programming problem concerned with an application of tailoring programmed instruction to the individual student. We use a model of learning based on stimulus-sampling theory in which a subject is to be taught n items in the course of N trials. The problem is to determine a strategy of trial-by-trial item selection to maximize the expected terminal level of achievement of the subject; a trial consists of a test on a selected item followed by a reinforcement or teaching action relative to the item. A subject is either in the "conditioned" or "unconditioned" state with respect to an item. His response to a test is either correct or incorrect, and the probability of a correct response depends upon his state; thus, the state is not in exact correspondence with the response. The reinforcement action permits a probabilistic transition from the unconditioned to the conditioned state during a trial. States are not observable; a strategy is based upon the history of responses to items presented up to the current trial. Associated with a subject is a current state probability vector (λ[sub 1], λ[sub 2], …, λ[sub n]), λ[sub i] = probability of conditioned state relative to item i, given the subject's history to date. We prove that the following (locally optimal) strategy is (globally) optimal: In each trial, present any item for which the current probability of the conditioned state is least. [ABSTRACT FROM AUTHOR]

Discrete optimization subject to one constraint is attacked by Lagrangian analysis. Incremental allocation schemes are given that generate undominated allocations. In an important special case, the complete family of undominated allocations is generated. [ABSTRACT FROM AUTHOR]

We present a method for approximating the solution of mixed integer nonconcave programming problems in bounded variables. We present computational results for 39 test problems which suggest that the procedure offers a practical useful way of approximating solutions of programming problems of the type tested. We have also discovered an apparent regularity in the distribution of local optima generated by the method; the method seems to generate Beta distributions in all problems for which results are available. This suggests interesting opportunities for further exploration. [ABSTRACT FROM AUTHOR]

As capital budgeting decision procedures become more complex, they must allow for more aspects of the real world. The present article surveys the techniques available to handle the important and generally neglected problem of project interrelationships such as mutual exclusion and interdependencies. The techniques utilized are linear and integer programming, dynamic programming, and the discrete optimizing procedure of Reiter. Project interrelationships arising from randomness of outcomes and nonlinear utility functions are also subjected to scrutiny by application of these procedures, and additional interrelationships, arising in the context of research and development budgets, are analyzed. A dynamic programming code for the multidimensional 0-1 knapsack problem is also presented. [ABSTRACT FROM AUTHOR]