A quadratic assignment problem without column constraints

We convert a quadratic assignment problem [1] with a nonconvex objective function into an integer linear program. We then solve the equivalent integer program by a simple enumeration that produces global minima.     

An algorithm (GIPC2) for solving integer programming problems with separable nonlinear objective functions

This paper presents an algorithm for solving the integer programming problem possessing a separable nonlinear objective function subject to linear constraints. The method is based on a generalization of the Balas implicit enumeration scheme. Computational experience is given for a set of seventeen linear and seventeen nonlinear test problems. The results indicate that the algorithm can solve the nonlinear integer programming problem in roughly the equivalent time required to solve the linear integer programming problem of similar size with existing algorithms. Although the algorithm is specifically designed to solve the nonlinear problem, the results indicate that the algorithm compares favorably with the Branch and Bound algorithm in the solution of linear integer programming problems.     

Concave minimization over a convex polyhedron

A general algorithm is developed for minimizing a well defined concave function over a convex polyhedron. The algorithm is basically a branch and bound technique which utilizes a special cutting plane procedure to' identify the global minimum extreme point of the convex polyhedron. The indicated cutting plane method is based on Glover's general theory for constructing legitimate cuts to identify certain points in a given convex polyhedron. It is shown that the crux of the algorithm is the development of a linear undrestimator for the constrained concave objective function. Applications of the algorithm to the fixed-charge problem, the separable concave programming problem, the quadratic problem, and the 0-1 mixed integer problem are discussed. Computer results for the fixed-charge problem are also presented.     

A decomposition procedure for convex quadratic programs

This article deals with the solution of convex quadratic programs by iteratively solving a master problem and a subproblem as proposed previously by Sacher. The approach has the advantage that the subproblems are linear programs so that advantage can be taken of existing schemes for solving large linear problems. At each step in solving the master problem, a closed-form solution can be specified so that the procedure is well suited for solving large quadratic programs and can take advantage of the constraint structure.     

A network isolation algorithm

A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound.     

The formulation of some allocation and connection problems as integer programs

In this paper a component placement problem and a digital computer backboard wiring problem are formulated as integer linear programs. The component placement problem consists of making a unique assignment of components to column positions such that wireability is maximized. The backboard wiring problem consists of three interrelated subproblems, namely, the placement, the connection, and the routing problems. The placement and connection problems are combined and solved as one, thereby giving the optimal circuit connections as well as minimizing the total lead length. It is shown that under certain assumptions, the number of inequalities and variables in the problem can be greatly reduced. Further simplifying assumptions lead to a near optimal solution. Examples of other allocation problems to which the models presented here are applicable are given. The following concepts are formulated as linear inequalities: (1) the absolute magnitude of the difference between two variables; (2) minimize the minimum function of a set of functions; and (3) counting the number of (0, 1) adjacent component pairs in a vector.     

Equivalent knapsack-type formulations of bounded integer linear programs: An alternative approach

In this paper we show that every bounded integer linear program can be transformed into an integer program involving one single linear constraint and upper and lower bounds on the variables, such that the solution space of the original problem coincides with that one of the equivalent knapsack-type problem.     

Setting military reenlistment bonuses

The United States military frequently has difficulty retaining enlisted personnel beyond their initial enlistment. A bonus program within each service, called a Selective Reenlistment Bonus (SRB) program, seeks to enhance reenlistments and thus reduce personnel shortages in critical military occupational specialties (MOSs). The amount of bonus is set by assigning “SRB multipliers” to each MOS. We develop a nonlinear integer program to select multipliers which minimize a function of deviations from desired reenlistment targets. A Lagrangian relaxation of a linearized version of the integer program is used to obtain lower bounds and feasible solutions. The best feasible solution, discovered in a coordinate search of the Lagrangian function, is heuristically improved by apportioning unexpended funds. For large problems a heuristic variable reduction is employed to speed model solution. U.S. Army data and requirements for FY87 yield a 0-1 integer program with 12,992 binary variables and 273 constraints, which is solved within 0.00002% of optimality on an IBM 3033AP in less than 1.7 seconds. More general models with up to 463,000 binary variables are solved, on average, to within 0.009% of optimality in less than 1.8 minutes. The U.S. Marine Corps has used a simpler version of this model since 1986. © 1993 John Wiley & Sons, Inc.     

Response surface analysis of two‐stage stochastic linear programming with recourse

We apply the techniques of response surface methodology (RSM) to approximate the objective function of a two‐stage stochastic linear program with recourse. In particular, the objective function is estimated, in the region of optimality, by a quadratic function of the first‐stage decision variables. The resulting response surface can provide valuable modeling insight, such as directions of minimum and maximum sensitivity to changes in the first‐stage variables. Latin hypercube (LH) sampling is applied to reduce the variance of the recourse function point estimates that are used to construct the response surface. Empirical results show the value of the LH method by comparing it with strategies based on independent random numbers, common random numbers, and the Schruben‐Margolin assignment rule. In addition, variance reduction with LH sampling can be guaranteed for an important class of two‐stage problems which includes the classical capacity expansion model. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 753–776, 1999     

The parallel replacement problem with demand and capital budgeting constraints

A generalized parallel replacement problem is considered with both fixed and variable replacement costs, capital budgeting, and demand constraints. The demand constraints specify that a number of assets, which may vary over time, are required each period over a finite horizon. A deterministic, integer programming formulation is presented as replacement decisions must be integer. However, the linear programming relaxation is shown to have integer extreme points if the economies of scale binary variables are fixed. This allows for the efficient computation of large parallel replacement problems as only a limited number of 0–1 variables are required. Examples are presented to provide insight into replacement rules, such as the “no‐splitting‐rule” from previous research, under various demand scenarios. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 40–56, 2000     

A specially structured nonlinear integer resource allocation problem

We present an algorithm for solving a specially structured nonlinear integer resource allocation problem. This problem was motivated by a capacity planning study done at a large Health Maintenance Organization in Texas. Specifically, we focus on a class of nonlinear resource allocation problems that involve the minimization of a convex function over one general convex constraint, a set of block diagonal convex constraints, and bounds on the integer variables. The continuous variable problem is also considered. The continuous problem is solved by taking advantage of the structure of the Karush‐Kuhn‐Tucker (KKT) conditions. This method for solving the continuous problem is then incorporated in a branch and bound algorithm to solve the integer problem. Various reoptimization results, multiplier bounding results, and heuristics are used to improve the efficiency of the algorithms. We show how the algorithms can be extended to obtain a globally optimal solution to the nonconvex version of the problem. We further show that the methods can be applied to problems in production planning and financial optimization. Extensive computational testing of the algorithms is reported for a variety of applications on continuous problems with up to 1,000,000 variables and integer problems with up to 1000 variables. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 770–792, 2003.     

Hyperbolic integer programming

The hyperbolic integer program is treated as a special case of a hyperbolic program with a finite number of feasible points. The continuous hyperbolic program also belongs to this class since its solution can be obtained by considering only the extreme points of the feasible set. A general algorithm for solving the hyperbolic integer program which reduces to solving a sequence of linear integer problems is proposed. When the integer restriction is removed, this algorithm is similar to the Isbell-Marlow procedure. The geometrical aspects of the hyperbolic problem are also discussed and several cutting plane algorithms are given.     

A note on duality in homogeneous fractional programming

For a linear fractional programming problem, Sharma and Swarup have constructed a dual problem, also a linear fractional program, in which the objective functions of both primal and dual problems are the same. Craven and Mond have extended this result to a nonlinear fractional programming problem with linear constraints, and a dual problem for which the objective function is the same as that of the primal. This theorem is now further extended from linear to differentiable convex constraints.     

Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine

This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed‐integer linear programming formulation. By relaxing some constraints, a Lagrangean relaxation algorithm is designed which gives both lower and upper bounds. The special case where jobs have equal weights is analyzed. Computational results are presented and, although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 50: 2003     

The use of dynamic programming methodology for the solution of a class of nonlinear programming problems

This paper presents an application of a method for finding the global solution to a problem in integers with a separable objective function of a very general form. This report shows that there is a relationship between an integer problem with a separable nonlinear objective function and many constraints and a series of nonlinear problems with only a single constraint, each of which can be solved sequentially using dynamic programming. The first solution to any of the individual smaller problems that satisfies the original constraints in addition, will be the optimal solution to the multiply-constrained problem.     

A generalized euclidean procedure for integer linear programs

This paper investigates a new procedure for solving the general-variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier-Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all-integer algorithm.     

Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

The reformulation‐linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of “product factors” of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others. We examine the usefulness of subsets of constraints for a family of 0–1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0–1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Cyclic preference scheduling for nurses using branch and price

This paper presents a new methodology to solve the cyclic preference scheduling problem for hourly workers. The focus is on nurse rostering but is applicable to any organization in which the midterm scheduling decision must take into account a complex of legal, institutional, and preferential constraints. The objective is to strike a balance between satisfying individual preferences and minimizing personnel costs. The common practice is to consider each planning period independently and to generate new rosters at the beginning of each. To reduce some of the instability in the process, there is a growing trend toward cyclic schedules, which are easier to manage and are generally perceived to be more equitable. To address this problem, a new integer programming model is presented that combines the elements of both cyclic and preference scheduling. To find solutions, a branch‐and‐price algorithm is developed that makes use of several branching rules and an extremely effective rounding heuristic. A unique feature of the formulation is that the master problem contains integer rather than binary variables. Computational results are reported for problem instances with up to 200 nurses. Most were solved within 10 minutes and many within 3 minutes when a double aggregation approach was applicable. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

The frequency assignment problem: A solution via nonlinear programming

This paper gives a mathematical programming model for the problem of assigning frequencies to nodes in a communications network. The objective is to select a frequency assignment which minimizes both cochannel and adjacent-channel interference. In addition, a design engineer has the option to designate key links in which the avoidance of jamming due to self interference is given a higher priority. The model has a nonconvex quadratic objective function, generalized upper-bounding constraints, and binary decision variables. We developed a special heuristic algorithm and software for this model and tested it on five test problems which were modifications of a real-world problem. Even though most of the test problems had over 600 binary variables, we were able to obtain a near optimum in less than 12 seconds of CPU time on a CDC Cyber-875.