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.     

A mutual primal-dual linear programming algorithm

A new primal-dual linear programming algorithm is exhibited. A proof is given that optimal solutions to both primal and dual problems (when such solutions exist) are found in a finite number of steps by this algorithm. A numerical example is included to illustrate the method.     

The enumeration of all efficient solutions for a linear multiple-objective transportation problem

An algorithm is presented by which the set of all efficient solutions for a linear multiple-objective transportation problem can be enumerated. First the algorithm determines an initial efficient basic solution. In a second step all efficient basic solutions are enumerated. Finally, the set of all efficient solutions is constructed as a union of a minimal number of convex sets of efficient solutions. The algorithm is illustrated by a numerical example.     

Two-agent scheduling with linear resource-dependent processing times

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is -hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unless ; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.     

The interactive fixed charge linear programming problem

In many decision-making situations, each activity that can be undertaken may have associated with it both a fixed and a variable cost. Recently, we have encountered serveral practical problems in which the fixed cost of undertaking an activity depends upon which other activities are also undertaken. To our knowledge, no existing optimization model can accomodate such a fixed cost structure. To do so, we have therefore developed a new model called the interactive fixed charge linear programming problem (IFCLP). In this paper we present and motivate problem (IFCLP), study some of its characteristics, and present a finite branch and bound algorithm for solving it. We also discuss the main properties of this algorithm.     

A stochastic linear knapsack problem

In this article we consider a stochastic version of the continuous linear knapsack problem, i.e., a model with a random linear constraint, and provide an efficient algorithm for solving it. An original problem P_o is first transformed into a deterministic equivalent problem P_o. Furthermore, by a change of variables, P_o is transformed into P. Then, in order to solve P, a subproblem P(μ.) with positive parameter μ is introduced, and a close relation between P and P(μ) is clarified. Furthermore, an auxiliary problem P^R(μ) of P(μ) with positive parameter R is introduced, and a relation between P^R(μ) and P(μ) is also clarified. From these relations, a direct relation connecting P^R(μ) with P is derived. An efficient algorithm based on this relation for solving P is proposed. It is shown that time complexity of the algorithm is O(n log n), where n is the number of items. Finally, some further research problems are discussed.     

A branch and bound algorithm for allocation problems in which constraint coefficients depend upon decision variables

A branch and bound algorithm is developed for a class of allocation problems in which some constraint coefficients depend on the values of certain of the decision variables. Were it not for these dependencies, the problems could be solved by linear programming. The algorithm is developed in terms of a strategic deployment problem in which it is desired to find a least-cost transportation fleet, subject to constraints on men/materiel requirements in the event of certain hypothesized contingencies. Among the transportation vehicles available for selection are aircraft which exhibit the characteristic that the amount of goods deliverable by an aircraft on a particular route in a given time period (called aircraft productivity and measured in kilotons/aircraft/month) depends on the ratio of type 1 to type 2 aircraft used on that particular route. A model is formulated in which these relationships are first approximated by piecewise linear functions. A branch and bound algorithm for solving the resultant nonlinear problem is then presented; the algorithm solves a sequence of linear programming problems. The algorithm is illustrated by a sample problem and comments concerning its practicality are made.     

Multiperiod capacity expansion and shipment planning with linear costs

In this paper we consider a multiperiod deterministic capacity expansion and shipment planning problem for a single product. The product can be manufactured in several producing regions and is required in a number of markets. The demands for each of the markets are non-decreasing over time and must be met exactly during each time period (i.e., no backlogging or inventorying for future periods is permitted). Each region is assumed to have an initial production capacity, which may be increased at a given cost in any period. The demand in a market can be satisfied by production and shipment from any of the regions. The problem is to find a schedule of capacity expansions for the regions and a schedule of shipments from the regions to the markets so as to minimize the discounted capacity expansion and shipment costs. The problem is formulated as a linear programming model, and solved by an efficient algorithm using the operator theory of parametric programming for the transporation problem. Extensions to the infinite horizon case are also provided.     

A mofified gub algorithm for solving linear minimax problems

This article is concerned with the minimization of the maximal value of a set of linear functions subject to linear constraints. It is well known that this problem can be transformed into a standard linear programming problem by introducing an additional variable. In case index sets of nonzero coefficients of the variables contained in each function are mutually exclusive, the constraints of the associated LP problem exhibit the almost-GUB structure. We devised a technique which reduces the number of arithmetic operations by exploiting this special structure. Computational results are also presented, which indicates that our method is more efficient than the ordinary revised simplex method.     

Nonextreme point solution strategies for linear programs

This exposition presents two algorithms for linear programs which allow a value change in more than one nonbasic variable at each iteration. The computational formulae are developed and errors which have appeared in the literature are noted. One algorithm is a multiple basis exchange procedure while the second is a feasible direction method. There remain many computational challenges in the area of linear programming and we hope that this investigation will encourage additional work in the directions indicated in this exposition.     

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     

An assumption-free convergence analysis for a perturbation of the scaling algorithm for linear programs,with application to the L1 estimation problem

This article is concerned with the scaling variant of Karmarkar's algorithm for linear programming problems. Several researchers have presented convergence analyses for this algorithm under various nondegeneracy types of assumptions, or under assumptions regarding the nature of the sequence of iterates generated by the algorithm. By employing a slight perturbation of the algorithm, which is computationally imperceptible, we are able to prove without using any special assumptions that the algorithm converges finitely to an ε-optimal solution for any chosen ε > 0, from which it can be (polynomically) rounded to an optimum, for ε > 0 small enough. The logarithmic barrier function is used as a construct for this analysis. A rounding scheme which produces an optimal extreme point solution is also suggested. Besides the non-negatively constrained case, we also present a convergence analysis for the case of bounded variables. An application in statistics to the L₁ estimation problem and related computational results are presented.     

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.     

An exact ceiling point algorithm for general integer linear programming

We present an algorithm called the exact ceiling point algorithm (XCPA) for solving the pure, general integer linear programming problem (P). A recent report by the authors demonstrates that, if the set of feasible integer solutions for (P) is nonempty and bounded, all optimal solutions for (P) are “feasible 1-ceiling points,” roughly, feasible integer solutions lying on or near the boundary of the feasible region for the LP-relaxation associated with (P). Consequently, the XCPA solves (P) by implicitly enumerating only feasible 1-ceiling points, making use of conditional bounds and “double backtracking.” We discuss the results of computational testing on a set of 48 problems taken from the literature.     

Scheduling with parallel processors and linear delay costs

This paper deals with the sequencing problem of minimizing linear delay costs with parallel identical processors. The theoretical properties of this m-machine problem are explored, and the problem of determining an optimum scheduling procedure is examined. Properties of the optimum schedule are given as well as the corresponding reductions in the number of schedules that must be evaluated in the search for an optimum. An experimental comparison of scheduling rules is reported; this indicates that although a class of effective heuristics can be identified, their relative behavior is difficult to characterize.     

具有模糊系数约束的多目标线性规划

研究了一类具有模糊系数约束的多目标线性规划问题.根据各目标函数的梯度方向来量化目标之间的冲突程度,以此提出了一种确定目标权重的新方法,然后基于惩罚函数运用梯度上升算法求问题的有效解.最后给出了一个数值例子.     

An algorithm for solving general fractional interval programming problems

A Linear Fractional Interval Programming problem (FIP) is the problem of extremizing a linear fractional function subject to two-sided linear inequality constraints. In this paper we develop an algorithm for solving (FIP) problems. We first apply the Charnes and Cooper transformation on (FIP) and then, by exploiting the special structure of the pair of (LP) problems derived, the algorithm produces an optimal solution to (FIP) in a finite number of iterations.     

Programming with linear fractional functionals

Charnes and Cooper [1] showed that a linear programming problem with a linear fractional objective function could be solved by solving at most two ordinary linear programming problems. In addition, they showed that where it is known a priori that the denominator of the objective function has a unique sign in the feasible region, only one problem need be solved. In the present note it is shown that if a finite solution to the problem exists, only one linear programming problem must be solved. This is because the denominator cannot have two different signs in the feasible region, except in ways which are not of practical importance.     

一类多目标模糊系数线性规划问题

讨论了一类所有系数均为模糊数的多目标线性规划问题 .通过对模糊数的比较 ,将模糊多目标线性规划模型转化为清晰的多目标模型 ,并应用一种基于线性隶属函数的模糊规划算法求其协调解 .最后给出了一个数值例子 .     

Variations on a cutting plane method for solving concave minimization problems with linear constraints

A cutting plane method for solving concave minimization problems with linear constraints has been advanced by Tui. The principle behind this cutting plane has been applied to integer programming by Balas, Young, Glover, and others under the name of convexity cuts. This paper relates the question of finiteness of Tui's method to the so-called generalized lattice point problem of mathematical programming and gives a sufficient condition for terminating Tui's method. The paper then presents several branch-and-bound algorithms for solving concave minimization problems with linear constraints with the Tui cut as the basis for the algorithm. Finally, some computational experience is reported for the fixed-charge transportation problem.